Storing Objects in Sorted Order

Problem

You have to store a set of objects in order, perhaps because you frequently need to access ordered ranges of these objects and you don't want to pay for resorting them each time you do this.

Solution

Use the associative container set, declared in , which stores items in sorted order. It uses the standard less class template, (which invokes operator< on its arguments) by default, or you can supply your own sorting predicate. Example 6-10 shows how to store strings in a set.

Example 6-10. Storing strings in a set

#include #include #include using namespace std; int main( ) { set setStr; string s = "Bill"; setStr.insert(s); s = "Steve"; setStr.insert(s); s = "Randy"; setStr.insert(s); s = "Howard"; setStr.insert(s); for (set::const_iterator p = setStr.begin( ); p != setStr.end( ); ++p) cout << *p << endl; }

Since the values are stored in sorted order, the output will look like this:

Bill Howard Randy Steve

Discussion

A set is an associative container that provides logarithmic complexity insertion and find, and constant-time deletion of elements (once you have found the element you want to delete). sets are unique associative containers, which means that no two elements can be equivalent, though you can use a multiset if you need to store multiple instances of equivalent elements. You can think of a set as a set in the mathematical sense, that is, a collection of items, with the added bonus that order is maintained among the elements.

You can insert and find elements, but, like a list, a set does not allow random access to elements. If you want something in a set, you have to look for it with the find member function, or iterate through the elements using set::iterator or set::const_iterator.

The declaration of a set should look familiar:

set, // The function/functor // used for sorting typename Alloc = std::allocator > // Memory allocator

You always have to specify the Key, you sometimes should supply your own LessThanFun, and you should rarely need to supply your own allocator (so I won't discuss how to write an allocator here).

The Key template parameter is, as is usually the case with the other standard containers, the type of the element that will be stored. It is typedef'd on the set as set::key_type, so you have access to the type at runtime. The Key class has to support copy construction and assignment, and you're all set.

Example 6-10 shows how to use a set with strings. Using a set to store objects of any other class works the same way; declare the set with the class name as the template parameter:

std::set setMyObjs;

This is all you have to do to use a set in the simplest way possible. But most of the time, life won't be so simple. For example, if you are storing pointers in the set, you can't rely on the default sorting predicate because it's just going to sort the objects by their address. To make sure elements are sorted properly, you will have to supply your own predicate for making less-than comparisons. Example 6-11 shows how.

Example 6-11. Storing pointers in a set

#include #include #include #include #include using namespace std; // Class for comparing strings given two string pointers struct strPtrLess { bool operator( )(const string* p1, const string* p2) { assert(p1 && p2); return(*p1 < *p2); } }; int main( ) { setstrPtrLess> setStrPtr; // Give it my special // less-than functor string s1 = "Tom"; string s2 = "Dick"; string s3 = "Harry"; setStrPtr.insert(&s1); setStrPtr.insert(&s2); setStrPtr.insert(&s3); for (set::const_iterator p = setStrPtr.begin( ); p != setStrPtr.end( ); ++p) cout << **p << endl; // Dereference the iterator and what // it points to }

strPtrLess returns true if the string pointed to by p1 is less than the one pointed to by p2. This makes it a binary predicate, because it takes two arguments and returns a bool. Since operator< is defined for strings, I can just use that to make the comparison. In fact, if you want to take a more generic approach, use a class template for your comparison predicate:

template class ptrLess { public: bool operator( )(const T* p1, const T* p2) { assert(p1 && p2); return(*p1 < *p2); } };

This will work for pointers to anything that has operator< defined. You can declare a set with it like this:

setptrLess > setStrPtr;

sets support many of the same functions as the standard sequence containers (e.g., begin, end, size, max_size), and other associative containers (e.g., insert, erase, clear, find).

When you are using a set, remember that you pay for the sorting every time you modify the state of the set. When the number of elements is large, the logarithmic complexity of adding or deleting elements can add updo you really need the objects to be sorted all the time? If not, you may get better performance by storing items in a vector or a list and sorting them only when you have to, which can usually be done in n*log(n) complexity.