My Project
|
This page introduces into the stxxl::map (for further information on the structure you may have a look at Map (B+-tree)).
stxxl::map is an external associative container that stores elements formed by a combination of a unique key value and a data value, following a specific order. The map's key values are generally used to sort and uniquely identify the data values, while the data values store the content associated to this key.
To create a stxxl::map object, several template parameters are required. The first two parameters KeyType and DataType which is an std::pair<int, char> in this example are self-explanatory, the third parameter has to be a comparator class which is used to determine whether a key is smaller than another one, the fourth and fifth parameter define the node- and leaf block size.
The comparator class has to be defined by hand (and before the map definition above) and looks like:
If CompareGreater()(a,b) is true, then a is smaller than b. CompareType must also provide a static max_value method, that returns a value of type KeyType that is larger than any key stored in map, i.e. for all x in map holds CompareType()(x,CompareType::max_value())
Naturally, we can define a comparator class which returns true if b is smaller than a as follows:
Note that CompareType must define a strict weak ordering.
Insertion of elements is possible in three different ways:
Random access is possible by using the []-operator:
Scanning a stxxl::map by an iterator works like
Hint: To enable leaf prefetching during scanning, call my_map.enable_prefetching() before.
In addition, the operations lower_bound() and upper_bound() are available. The function lower_bound(key) returns an iterator which initially points to the first element in the container whose key is not considered to go before key. upper_bound(key) works similar as it returns an iterator which initially points to the first element in the container whose key is considered to go after key.
Note: lower_bound() works nearly equal to upper_bound(), except in the case that the map contains an element with a key equivalent lower_bound(x): In this case lower_bound(x) returns an iterator pointing to that element, whereas upper_bound(x) returns an iterator pointing to the next element.
Removing elements out of the map is possible in three different ways:
To determine the size (i.e. the number of elements) of an instance, call size():
To check if the priority queue is empty, call empty() which returns true in case:
(See examples/containers/map1.cpp for the sourcecode of the following example).