C++ Cookbook

6.8. 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 <set>, 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 <iostream>
#include <set>
#include <string>

using namespace std;

int main() {

   set<string> setStr;
   string s = "Bill";

   setStr.insert(s);
   s = "Steve";
   setStr.insert(s);
   s = "Randy";
   setStr.insert(s);
   s = "Howard";
   setStr.insert(s);

   for (set<string>::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 ...