Thinking Outside the Map Std::map's value_type--pair--protects users from accidently modifying a key after inserting an item, but it also hinders the development of efficient applications. This article will look at the red-black tree class that underpins map as an alternative to map. We'll consider how these two classes differ by looking at parallel examples--some with map and some with the red-black tree class. Underlying std::map (in most implementations) is a red-black tree class. Like map it is a class template. I'll call the red-black tree class rb_tree. template , class Alloc = __STL_DEFAULT_ALLOCATOR(Value) > class rb_tree { ....... }; rb_tree declarations are similar to those with map, but there's an additional parameter, the KeyOfValue, that is needed. The KeyOfValue is a function object that takes an instance of type Value and returns a reference to the member of Value that is being used as a key. (map is able to supply this parameter for you because it knows that the first member of the pair is the key.) Here is an example of an rb_tree declaration: We'll use the following type: struct Account { Account(Name name, string ssn) : clientName_(name), ssn_(ssn) { ... } Name const clientName_; string const ssn_; double balance_; // I know Date openDate_; }; rb_tree accountsBySSN; GetSSN is implemented as follows: struct GetSSN { string const& operator() (Account const* inst) { return inst->ssn_; } }; Now let's look at the same example using map: map accountsBySSN; This provides the same ordering as we considered above, but it is less efficient. You wind up having two copies of the key field with this implementation--one is the first member of the pair and the other is tucked away in Account. The extra copy of the key takes up space and takes time to build and tear down. As the number of accounts grows so does the amount of memory that is wasted. Inserts are also more arduous for the map than the rb_tree-- map makes a copy of the value_type--pair-- but rb_tree just copies the Account pointer. Another approach would be to take the ssn field out of Account: struct AccountMinusSSN { AccountMinusSSN(Name name) : name_(name) { ... } Name const name_; double balance_; // For lack of something better Date openDate_; }; And then write: map accountsBySSN; This avoids the superfluous copy of the key field, but it has weaknesses. Again, the inserts are slower than in the rb_tree implementation because more data is being copied. This approach also imposes on how you would design your classes. If an AccountMinusSSN method needs the ssn, you have to pass it in. This is extra work in terms of the coding and there is a small price in time for getting the stack set up correctly. We could minimize the amount of copying that is needed for this approach by making the key field be a pointer: map accountsBySSN; This also has its weaknesses. You have to make twice as many calls to new/delete as the rb_tree implementation, there's still the forced splitting up of data that you would otherwise probably not split up, and you have to write a comparison function object to get the compares working. And after all of that, map will have to make room for two pointers and rb_tree just one. Sometimes the harder you try the worse it gets. Perhaps the best implementation we can get with map would look like this: map accountsBySSN; We would build a pair by taking the address of Account's key field: Name aname = "Penelope Perkins"; string ssn = "123456789"; Account* acct = new Account(aname, ssn); pair pr(&acct->ssn_, acct); accountsBySSN.insert(pr); This approach doesn't split up the class and doesn't require extra calls to new/delete. But it requires some superfluous memory--the pointer to the key field. And again map has to make room for two pointers whereas rb_tree gets away with just one. Also, this approach requires a comparison function object be written, so there is no basis for complaining about rb_tree's need for a function object. I believe that summarizes the different ways you could approach a problem like this with map. All of the approaches are less efficient than using rb_tree--they use more memory and time than rb_tree does. If you think rb_tree seems like an interesting alternative to map, the rest of the article goes into more detail on using rb_tree and how it differs from map. Let's look some more at how to use rb_tree. I'll admit that having to supply the KeyOfValue function objects is a pain. But its worth it. First as we've already seen, rb_tree can use resources more efficiently than map. And second, part of rb_tree's interface is simpler than map's because you write the function object. Here's an example: Name aname = "Penelope Perkins"; string ssn = "123456789"; Account* acct = new Account(aname, ssn); accountsBySSN.insert_unique(acct); rb_tree's insert operation is simpler than map's--you don't have to set up a pair. It is basically like std::set's insert, except you have two functions to pick from--insert_unique and insert_equal. (map's insert is based on insert_unique and multimap uses insert_equal.) If you are going to use rb_tree, you have to decide which of these two functions you should use. Another thing about using rb_tree that I think is helpful is the elimination of references to .first and .second that map brings. If you're working with a function that uses 3 or 4 different maps, its easy to get confused by the proliferation of "first" and "second" references. rb_tree offers custom names and a somewhat more compact form. For example, with a map::iterator, I could change the balance field of an Account object with (*iter).second->balance += 324.25; with rb_tree its (*iter)->balance += 324.25; // Pleasing to poets The rest of map's familiar interface--begin, end, find, erase, clear, size, operator=, swap, etc. remains the same except there's no operator[]. Given its tricky semantics, I think that's a good thing and have not missed it. (rb_tree and multimap are alike in this respect.) I think it is worth noting that rb_tree still uses std::pair in its interface--just not as heavily as map. Warning: Before going any further there is another difference between map and rb_tree that must be noted. Map's pair protects you from doing something stupid that rb_tree doesn't. The const in map's value_type prevents you from modifying a key after you've inserted an item. With rb_tree it is up to you to make key fields const. If you don't and you inadvertently modify a key field after insertion, you will no longer have a true rb_tree. All of the finds, inserts, and erases are suspect after making such a mistake. I think the thing to note in this regard though, is that rb_tree allows you to craft both a better and a worse solution than map does. If you make the key fields const, you have the same protection as with map and better performance. If you don't make the key fields const and you inadvertently modify one of the keys after an object has been inserted, you will cause someone--probably you--grief. Speaking of std:set, you can make a few small changes to rb_tree's interface and use it instead of std::set. That way you have one less class to learn and use. You have to change the order of the Key and Value template arguments in rb_tree and add some default values: template , class Compare = less, class Alloc = __STL_DEFAULT_ALLOCATOR(Value) > class rb_tree { ....... }; The rb_tree declarations above would have to be changed accordingly: rb_tree accountsBySSN; would have to be rb_tree accountsBySSN; And instead of set We can write rb_tree. Conclusion Applications that use rb_tree are more efficient than those that use map. However, rb_tree does not take the same measures to prevent you from messing everything up the way map does. The map class reminds me of a bike with training wheels: those wheels slow you down and help keep you from getting hurt badly, but if you really want to fly, you have to get your dad to take them off. This article was written in 2002 with some updates since.