Click here to Skip to main content
15,172,953 members
Articles / Programming Languages / Visual C++ 9.0
Posted 15 Jul 2008

Tagged as


34 bookmarked

Stree - A fast std::map and std::set replacement

Rate me:
Please Sign up or sign in to vote.
4.54/5 (23 votes)
6 Aug 2008LGPL37 min read
An implementation of an (almost) std::map compatible data structure which offers better performance and memory utilization.


std::map is a one of the most useful containers in the standard template library (STL). It allows the implementation of sorted dictionaries. It is usually implemented using a red-black tree data-structure which guarantees a good (O(log n)) performance, and is the container-of-choice for most tasks (unless you are using a new Standard Library implementation - e.g., Visual Studio 2008 with Feature Pack 1 or GCC 4.2 - in which case, you can use the new TR1 unordered_map and unordered_set).

Although std::map and std::set are good enough for most tasks, the red-black tree implementation is no speed-demon. The provided code implements a "drop-in" replacement for std::map and std::set (we haven't implemented the multi- variants), which benchmarks show is two times faster.

Note that the implementation imposes restrictions on the Key type for the map: a special "infinity" value is required.

Boost and a modern C++ compiler are required.

Using the Code

smap and sset are drop-in replacements for std::map and std::set, respectively. Here is an example of using smap:

#include <iostream>
#include "sti/smap"
using namespace sti;
int main()
    // Create a map
    typedef smap<char, int> Map;
    Map my_map;
    // Insert some values  
    my_map.insert(std::make_pair('a', 1));
    my_map.insert(std::make_pair('A', 1));
    my_map.insert(std::make_pair('b', 2));
    my_map.insert(std::make_pair('B', 2));
    // find an item
    Map::const_iterator it = my_map.find('a');
    std::cout << "my_map[" << it->first << "]= " << it->second << std::endl;

    // Use operator []:
    my_map['a'] = 10;

    // Iterate over map:
    for (it = my_map.begin(); it != my_map.end(); ++it)
       std::cout << "my_map[" << it->first << "]= " 
                 << it->second << std::endl; 

    // Erase an item

    // or we can use an iterator:
    it = my_map.find('b');

    // Find out how many items are left in map:
    std::cout << "Items: " << my_map.size() << std::endl;

    return 0;

Similarly, for sset:

#include <iostream>
#include "sti/sset.h"
using namespace sti;

int main()
   typedef sset<int> Set;
   Set my_set;
   if (my_set.find(1) != my_set.end())
      std::cout << "Found 1 in set" << std::endl;
      std::cout << "Couldn't find 1 in set" << std::endl;
   return 0;

sset and smap are defined in sset.h and smap.h respectively, and defined as follows:

namespace sti
   // from smap.h
         class Key,
         class Type,
         class Traits = std::less<key>,
         class Allocator = std::allocator<std::pair <const Key, Type> >,
         int BN = 48,
         class key_policy   = default_stree_key_policy<Key>,
         class value_policy = default_smap_value_policy<Key, Type>,
         class gist_traits  = default_gist_traits<Key>
   > class smap;

   // from sset.h:
         class Key,
         class Traits = std::less<Key>,
         class Allocator = std::allocator<Key>,
         int BN = 48,
         </key>class key_policy   = default_stree_key_policy<Key>,
         class gist_traits  = default_gist_traits<Key>
<key />   > class sset;

Template parameters

Choosing BN

Except for the last (BN) template parameter, this definition is identical to std::map and std::set. BN is similar to the "order" of a B-Tree - it defines how many elements should be kept in a single node. Playing with this value can have significant impact on performance. BN values of 32 to 128 seem to perform well (see Implementation below for more details).


key_policy controls how keys are stored in internal nodes (see implementation below). key_policy can be either std::tr1::true_type or std::tr1::false_type. If key_policy is true_type, keys are stored "as-is" and are copied around as needed (when splitting/merging) using memmove(). Otherwise, only pointers to keys are stored in the node itself, along with a "gist" (size_t) value which is calculated from the key (using gist_traits).

By default, for small, simple types (POD types - int, char, etc.), key_policy is true_type, while for other types, it is false_type.

We don't want to store more complex types as part of the node, since moving them (for split/merge operations) will be expensive (and wrong, as we then must call the copy constructor).

It is therefore recommended to use the default key_policy, and in any case, do not use true_type for types that require a non-trivial copy constructor.


The gist_traits parameter is only valid when key_policy is true_type.

When key_policy is true_type, we only keep pointers to the keys in the inner nodes. Comparing these pointers will cost us in performance (see below - Memory as a Bottleneck). Keep a "cheap" value in the node itself that can be used to compare values quickly (comparing two integral values is virtually "free").

Here's a code that explains the idea:

struct KeyWrapper
   KeyType* _key;
   size_t   _gist;

bool less(KeyWrapper l, KeyWrapper r)
   if (l._gist < r._gist)
     return true;
   else if (l._gist > r._gist)
     return false;
       retrurn less(l->_key, r->_key);

If gist<sub>1</sub> is the gist of key<sub>1</sub>, and gist2 is the gist of key<sub>2</sub>, then the following must hold:

  • if key<sub>1</sub> < key<sub>2</sub>, then gist<sub>1</sub> <= gist <sub>2</sub>
  • If key<sub>1</sub> == key<sub>2</sub>, then gist<sub>1</sub> == gist<sub>2</sub>
  • if key<sub>1</sub> > key<sub>2</sub>, then gist<sub>1</sub> >= gist<sub>2</sub>

A default gist_traits is provided that simply returns 0 for all keys.

For strings, a specialization is provided that implements the following (sizeof(char)==1 for simplicity):

struct string_gist
   const static size_t chars_per_size_t = sizeof(size_t);
   size_t operator()(const std::string& s) const
      sz = std::min(sz, chars_per_size_t);
      size_t r = 0;
      for (size_t i = 0; i < sz; ++i)
         r = (r<<8) + (size_t)c[i];
      return r;


The value_policy parameter controls how an item is stored in the map. If value_policy is false_type, then each item inserted into the map is allocated separately, and a reference to the item is guaranteed to be valid (unless the item is erase()d, of course). If value_policy is true_type on the other hand, the items are stored as part of the stree nodes - and therefore can be reallocated when these nodes are split or merged.

By default, value_policy is true_type if both key and value are simple, small types, and false_type otherwise.


A simple benchmark is provided with the source. The benchmark creates a large container, then erase(), find(), and insert() are called repeatedly with random values. The same benchmark is performed for a std::map<int, int> and smap<int, int>.

Here are the results when compiling with Visual Studio 2008 with standard "Release" optimizations (Core 2 6400, 2GB memory running on WinXP):

STL map time: 1548678032
smap time:     740111472

smap therefore shows x2.09 performance improvement vs. std::map.


To simplify implementation, all iterators are invalidated if the container is modified, so the following code which (should) work with std::map will throw an exception:

smap<int, int> m;
smap<int, int>::iteraor it;

for (it = m.begin(); it != m.end(); ++it)
  if (it->second == 1)
    erase(++it); // <-- delete element at iterator
                 //     and advance iterator

As a workaround, erase(iterator) returns an iterator to the next element after the element deleted, so we can write instead (this will also work with Visual Studio's STL implementation which extends erase() in the same way):

smap<int, int> m;
smap<int, int>::iteraor it;

for (it = m.begin(); it != m.end(); ++it)
  if (it->second == 1)
    it = erase(it); // <-- delete element at iterator 
                    //  and advance iterator}

In addition, there is a limitation on the Key type: a special infinite() value is required which must be larger than any key.


Memory as bottleneck

The basic idea of stree is that in modern architectures, memory has become the main performance bottleneck: accessing a random main-memory location requires tens (and in some cases, hundreds) of clock cycles. New memory architectures mainly improve the transfer rate: once you get to a memory location, reading 1 or 100 bytes takes about the same time. Cache memory reduces memory-access latency by storing a low-latency copy of frequently used memory - accessing random (or wide-spread) memory locations will result in cache misses.

Disk-based data structures face the same issues - e.g., caching; high cost of accessing the first bit vs. accessing the next one, etc. The solution - using "flatter" trees (B-Trees) and keeping multiple items together, is now appropriate for memory-based data structures.

A bit on skip lists

A skip-list is basically a sorted linked-list with "shortcuts" which allow a fast (O(n) on average) find operation.

To construct a skip-list, start with a sorted linked list (let's call this the 0-level list). Now, choose (randomly) half of the nodes and connect them by another linked-list (the 1-level list). Now, choose randomly half the nodes in the 1-level list and create a 2-level list, and so-on until no elements are chosen for some level.

To search a linked-list, start by progressing along the highest-level list, "dropping" to the next level, if progressing to the next node will get us past the desired element. On average, no more than 3 elements need to be examined in each level.

The 1-2-3 Top-Down skip-lists

Munro, Papadakis, and Sedgewick have proposed an alternative version of the skip-list which is deterministic. In addition, they described a simpler implementation of the skip-list - the 1-2-3 Top-Down skip-list.

Here is an example of a 1-2-3 skip list:

Image 1

This structure is similar to a binary tree with the node leafs connected in a linked-list. Search starts with the head node at the top left (48), and goes right as long as the searched key is greater than the node's key, in which case, we drop to the next level and continue our search. Similar to a B+ Tree, items are stored only in the leafs.

Unlike a skip-list, this is a deterministic data structure: the "gap" between two nodes is always between 2 and 3. For example, there is a 3-node gap between the head node (48) and the node to its right. That gap includes the nodes 13, 30, and 48 at the middle level. Similarly, there is a 2-node gap between nodes 13 and 30 at the middle level, which includes the nodes 9 and 13 at the bottom. Whenever the gap goes outside the allowed range (2-3), the structure is fixed by adding (or removing) nodes.


The 1-2-3 skip list allows only gaps of size of at most 3. However, there is nothing to prevent us from allowing larger gaps. This will somewhat reduce the memory requirements (less inner nodes), but will increase the search time (need to check more items per level).

Another possible modification would be to store all nodes of a single gap in an array, which we call an stree. Here is the stree version of the same skip-list:

Image 2

By allowing larger gaps (up to BN) and replacing the link-list of items in a gap by an array, we get a data-structure quite similar to a B+ Tree.


  • July 15, 2008: Published.
  • July 17, 2008: Added more details on the implementation. memmove() only used for simple types.
  • Aug 06, 2008: Removed the need for infinite(). Supports all key and data types. Template parameters control whether to allow "movement" of value_type.


This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)


About the Author

United States United States
No Biography provided

Comments and Discussions

GeneralDoesn't compile on gcc 4.4.1 Pin
JohnBaronReid11-Feb-10 6:21
MemberJohnBaronReid11-Feb-10 6:21 
GeneralRe: Doesn't compile on gcc 4.4.1 Pin
Talal Bin Ghizal26-Apr-10 5:31
MemberTalal Bin Ghizal26-Apr-10 5:31 
GeneralRe: Doesn't compile on gcc 4.4.1 Pin
Morthrall11-Sep-10 3:51
MemberMorthrall11-Sep-10 3:51 
GeneralRe: Doesn't compile on gcc 4.4.1 Pin
cmeli26-Oct-11 4:23
Membercmeli26-Oct-11 4:23 
GeneralRe: Doesn't compile on gcc 4.4.1 Pin
spraetor5-Sep-13 2:51
Memberspraetor5-Sep-13 2:51 
GeneralRe: Doesn't compile on gcc 4.4.1 Pin
Member 1122406911-Nov-14 0:57
MemberMember 1122406911-Nov-14 0:57 
QuestionCompiling time Pin
Andrew Hain31-Aug-08 5:02
MemberAndrew Hain31-Aug-08 5:02 
AnswerRe: Compiling time Pin
curlog2-Sep-08 0:26
Membercurlog2-Sep-08 0:26 
QuestionIs this dormant now? Pin
amit_jain4-Aug-08 7:33
Memberamit_jain4-Aug-08 7:33 
AnswerRe: Is this dormant now? Pin
cppnow6-Aug-08 12:33
Membercppnow6-Aug-08 12:33 
GeneralSyntax Question Pin
Jonas Hammarberg25-Jul-08 1:03
professionalJonas Hammarberg25-Jul-08 1:03 
QuestionGreat, but why it's Boost dependent? PinPopular
Tage Lejon21-Jul-08 23:58
MemberTage Lejon21-Jul-08 23:58 
QuestionWhat about memory use? Pin
Lowell Boggs21-Jul-08 13:14
MemberLowell Boggs21-Jul-08 13:14 
GeneralGreat, but some questions Pin
amit_jain16-Jul-08 6:47
Memberamit_jain16-Jul-08 6:47 
AnswerRe: Great, but some questions Pin
cppnow16-Jul-08 22:26
Membercppnow16-Jul-08 22:26 
GeneralRe: Great, but some questions Pin
amit_jain17-Jul-08 3:04
Memberamit_jain17-Jul-08 3:04 
GeneralRe: Great, but some questions Pin
cppnow17-Jul-08 3:31
Membercppnow17-Jul-08 3:31 
AnswerRe: Great, but some questions Pin
cppnow20-Jul-08 2:37
Membercppnow20-Jul-08 2:37 
GeneralRe: Great, but some questions Pin
amit_jain20-Jul-08 12:03
Memberamit_jain20-Jul-08 12:03 
GeneralRe: Great, but some questions Pin
cppnow21-Jul-08 4:57
Membercppnow21-Jul-08 4:57 
Generalinteresting but... Pin
juggler15-Jul-08 5:58
Memberjuggler15-Jul-08 5:58 
Answerthanks for your replies Pin
cppnow15-Jul-08 4:30
Membercppnow15-Jul-08 4:30 
GeneralWill approve. Pin
Matthew Faithfull15-Jul-08 3:21
MemberMatthew Faithfull15-Jul-08 3:21 
GeneralQuestions PinPopular
peterchen15-Jul-08 3:17
Memberpeterchen15-Jul-08 3:17 
AnswerRe: Questions Pin
cppnow15-Jul-08 7:29
Membercppnow15-Jul-08 7:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.