Subject: Re: [boost] std::map<> - like structure for other than std::pair<>?
From: Francisco JosÃ© Tapia (fjtapia_at_[hidden])
Date: 2015-04-14 17:35:57
In my library Countertree ( set, multiset, map multimap concurrent and with
access by position like the vectors ) I implemented the map as a data
structure and a filter. Applying the filter you obtain the key. With the
same nodes of the tree you can build a different maps, only changing the
Imagine you have a map and each node have a code and a name, The map is
sorted by the code. Extracting the nodes of the map, putting in a vector
and inserting in map sorted by name,(the filter provide the name as key) it
a easy operation.
The access by positionof the trees , permit you new fast algorithms for
create a map from a vector ( a 30000000 nodes need 6 seconds with 1 thread
for to create a map, with 4 threads you can do in less than 3 seconds) The
STL map need 35 seconds for to do it.
All the implementations I know (GCC, VC++, Intel...) use a pair, and don't
permit the change of the key
The true problem is not to access to other element as use as second key,
the problem is the sorting. If you need the data sorted by several keys
simultaneously, you need multiindex. If when you sort by a second key,
unsort the data by the first key, the procedure described could be good
*The library countertree is pending of the final approval . You can find
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk