Associative containers, pointers, comparison

When we put strings in an associative container like set, we expect them to be stored by default by ascending alphabetical order. And that is exactely what happens, if we are working with a set of string.

The issue is if our set is of pointer to strings, since the default comparison keeps the elements ordered by address, and not by the string content.

If we want it being meaningful, we have to override the default with a more sensible choice.

Actually, it is not a good idea to put pointers in a container - if we do that, we have to remember to delete the pointers "manually" when their are not in use anymore - it is better to use smart pointers instead. Not the auto_ptr, obviously, since they are not designed to be used in standard containers, but a copy-supporting one, like shared_ptr, that are going to be available in C++0x. If your compiler does not provide it, you can use the boost implementation.

First thing, let's reduce the typing introducing a typdef for the shared pointer to string:

typedef std::shared_ptr<std::string> SS;

Now, we write a functor that we are going to use for comparing correctly the strings in our container:

struct SmartStringLess : public std::binary_function<const SS&, const SS&, bool>
{
    bool operator()(const SS& ps1, const SS& ps2)
    {
        return *ps1 < *ps2;
    }
};

We'll need also a function that prints the string in the passed smart pointer:

void printSS(const SS& ss)
{
    std::cout << *ss << std::endl;
}

And, again to reduce typing, another couple of typedefs for the set of smart pointers and for the iterator on the set:

typedef std::set<SS, SmartStringLess> SSS;
typedef SSS::const_iterator SIT;

Notice that the definition for the set refers to the functor we created above.

After all this setup, we are ready to creating our set and putting some data in it:

SSS sss;
sss.insert(new std::string("Alpha"));
sss.insert(new std::string("Delta"));
sss.insert(new std::string("Tango"));
sss.insert(new std::string("Foxtrot"));

Given that we specified the SmartStringLess functor, the strings are stored alphabetically oredered. But we still have an issue, we can't use the standard copy algorithm to the ostream_iterator for printing the content of the container:

std::copy(sss.begin(), sss.end(), std::ostream_iterator<SS>(std::cout, " ")); // !!!

The result of this call is printing, again, the pointers and not the strings.

We should fall back to a classic for loop with a double-dereferenced iteratator (quite ugly, actually):

for(SIT it = sss.begin(); it != sss.end(); ++it)
{
    std::string s = **it;
    std::cout << s << std::endl;
}

Or we can use instead the standard for_each algorithm, using the printSS() function that we written above:

std::for_each(sss.begin(), sss.end(), printSS);

Many more details on this argument in Item 20 of Effective STL, one of the Effective C++ books by Scott Meyers.