https://github.com/snaewe/loki-lib/blob/master/include/loki/AssocVector.h
Apparently this code was written by Andrei Alexandrescu.
There is a popular answer for benchmarking flat_map, but few details on how it works under the hood.
I can read the code, but I don't really understand everything, and I wish I could find some layman's.
flat_map might? will? be part of C++23, so I was curious about understanding its advantages and disadvantages, but I'm also curious to understand how it's implemented. Apparently is uses a map and a vector? What about an unordered version?
Is that somehow similar to an object pool, where an item removed in the middle of a vector is replaced with the last item of the vector to maintain contiguity? Is a flat_map somehow works like this with additional index tracking?
The first clue is in the declaration of the class:
class AssocVector
: private std::vector< std::pair<K, V>, A >
This tells us that an AssocVector is just a vector of key-value pairs.
The second clue is right there in the constructor and a bit more implicit in the various operations:
AssocVector(InputIterator first, InputIterator last, ...) {
typedef ::std::map< K, V, C, A > TempMap;
...
TempMap temp( first, last, me, tempAlloc );
Base::reserve( temp.size() );
BaseType & target = static_cast< BaseType & >( *this );
MyInserter myInserter = ::std::back_inserter( target );
::std::copy( temp.begin(), temp.end(), myInserter );
}
This first constructs an std::map from the input and copies it ordered by key to the underlying vector.
Similarly, many operations use std::lower_bound, which requires the following:
The range [first, last) must be partitioned with respect to the expression element < value (or comp(element, value)), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.
Thus, an AssocVector is a vector of key-value pairs that are always sorted by key and cannot contain duplicate values for a given key, much like std::map.