Dr. Dobb's Journal December 1997

The STL Set Class

The STL Set class is a container that is optimized for fast lookup. Set takes two template parameters: a Key, which is the object type to be stored, and a Compare function object, which is used to sort the Keys (typically less<Key>). Set can contain only one copy of a given Key value.

The Compare object is a struct that overrides the () operator to take two references of type Key, and returns True if the first Key should appear before the second Key.

The Set class sorts its members into an ordered tree using the STL's red-black tree class, rb_tree. This structure allows fast (order logn) key searches. For an excellent explanation of red-black trees, see Mark Nelson's Programmer's Guide to the Standard Template Library (IDG Books Worldwide, 1995).

As with all STL containers, access to member objects is provided with iterators. The begin/end sequence provides access to all objects in the order defined by the Compare object.

Example 1 declares a set of integers, inserts 0-9 into the set, and streams the members out. Searching a set for a particular member is accomplished with the find method, which returns an iterator that points to the object. If a set does not contain the object, find returns the end iterator; see Example 2.

In this article, the Abstract Factory class uses set<I*, less<I*> >, where I is the template parameter to the Abstract Factory class. Since the set contains pointers and it uses the less function object on those pointers, the set is sorted in arbitrary order, based on the numerical values of the pointers the factory allocates.

If object order is important, you may want to replace the compare function in the set container from less<I*> with something that sorts appropriately for your application.

-- J.S.