2014.04.04

Variadic C++ functions for packing and unpacking bits

Shall you need variadic C++11 functions for packing and unpacking (a few) bits, here is what I have done for myself.

In most cases it's probably better to use std::bitset or any other container, but these two functions may provide a quick and easy way to pack some bits into an integer and the other way around, without using any specific class or container. Read more...

Tags: cpp, cpp11
2013.12.19

Avoiding code duplication between const and non-const methods

Sometimes const and non-const methods in C++ classes share the same name, body, and return type (except for the const keyword), thus causing code duplication.

The problem is described in this StackOverflow topic, and somewhere else on the Internet. The obvious solution is to refactor the code in order to avoid duplication while preserving const-correctness and semantics, but sometimes this is not possible or not convenient. A popular (and effective) solution requires a const_cast and a static_cast. In this post, I suggest an alternative (and I think safer) solution. Read more...

Tags: cpp, cpp11
2013.11.17

A generic approach for Constraint Satisfaction Problems (CSPs)

Constraint Satisfaction Problems (CSPs) are a family of problems in which a set of variables is given, and values must be assigned to the variables so that a set of constraints is satisfied.

Simple CSPs are often proposed as programming exercises. Some examples are the famous eight queens puzzle, sudoku and futoshiki. The most straightforward way to solve this class of problems is to use a backtracking algorithm. For an in-depth explanation, please see the relevant Wikipedia article.

Read more...
Tags: algorithms, cpp
2013.07.05

Another (iterative) technique for enumerating permutations

The idea of writing this post came up by reading Programming Interview Questions 11: All Permutations of String by Arden Dertat. The author proposes a simple and elegant recursive algorithm that finds all the permutations of a given string.

If any of you is interested in an alternative (iterative) solution, here is one. I think it has a couple of features you may find interesting.

The starting point is to define an order among all the permutations and then write a procedure that, given a permutation, returns the following one. The order is simply the lexicographic order and the procedure is the following. Read more...

Tags: algorithms, cpp
2013.06.17

C++11 “smart” pointers need “careful” programmers

I’m taking a deeper look into the new C++11 features. One of the most useful features turned out to be shared_ptr, a smart pointer that, along with unique_ptr and weak_ptr, superseded the almost useless auto_ptr, which is now deprecated.

Informally speaking, shared_ptr wraps a pointer to an object, and has an internal counter taking track of how many copies of this shared_ptr are currently managing that object. When the counter eventually reaches 0, the object is deleted.

This can be very convenient, especially when memory management is an issue since the ownership relationships between objects are not clearly evident — and it’s hard to find out when and how an object should be deleted.

Still, there is a subtle issue that one should take care of when using shared_ptr. I bet it is quite obvious for most experienced C++ programmers, but I think everyone can do a mistake, and this post may actually save you from a big headache, sometime in the future. Read more...

Tags: cpp, cpp11
Fork me on GitHub