C++: Containers of pointers

One of the things C++ provides to programmers is that pointers can be avoided in much situations, and IMHO, they should be (specially in public class interfaces). However, there are some times in which pointers must be used.

Consider an abstract base class and multiple specializations of it; if you want to define a container of all these objects, no matter which derived class they belong to, the container must hold the parent's type. But you can't use an object (nor a reference) of this type, basically for two reasons: you can't instantiate one and, even if you could (no abstract members), the derived object could loose all of its specific properties when converted to the parent one.

In the above scenario, you are required to use pointers. And, when doing so, you hit a problem: the operations that are applied to containers will work at the pointer level, not at the object level, so all comparisons will be wrong. Let's clarify this with an example.

Suppose we have a set of pointers to strings and we add several objects to it:

std::set<std::string*> s;
s.insert(new std::string("String 1"));
s.insert(new std::string("String 2"));
s.insert(new std::string("String 3"));

We are now asked to check whether "String 2" is part of the set (in this example we are checking for equality). You can't use the s.find operation, because it will compare pointers rather than strings; so unless you know the address of the object you are looking for, you won't be able to find it. A solution could be to manually iterate all over the set and check each element against the string we want. Ugly, isn't it?

Fortunately, we can use the standard algorithms, but we will have to construct a custom predicate that, given two pointers, compares their contents. Our predicate could look like the following (requires the functional header):

template <class T>
struct unref_equal_to : public std::binary_function<T, T, bool>
{
   bool operator()(const T& x, const T& y) const { return *x == *y; }
};

Despite the operator taking two references, it must take pointers (because T will have to be a pointer type); otherwise, nasty things will happen. Then, all it does is apply the == (equality) operator on the unreferenced objects and return the result, which will do what we want (in this case, compare the string contents).

Now, how do we apply this predicate to look for a specific string in our previous set? Easy; we need the std::find_if standard algorithm, which takes a predicate as an argument. Let's see what we'd do:

std::string what("String 2");
std::set<std::string*>::const_iterator i =
   std::find_if(s.begin(), s.end(),
                std::bind2nd(unref_equal_to<std::string*>(),
                &what));
if (i != s.end())
   std::cout << "String 2 is part of s!" << std::endl;

Don't let this scare you, specially the std::bind2nd part. This function is used to set the second argument of the binary function we created above (which has some special properties). OTOH, the std::find_if algorithm will take care to fill in the first argument on each iteration it does over the set, so we will get the expected comparisons.