loki“Assoc Vector”是什么，它是如何工作的，它与 flat_map 有何关系？

Question

https://github.com/snaewe/loki-lib/blob/master/include/loki/AssocVector.h

显然这段代码是由 Andrei Alexandrescu 编写的。

对 flat_map 进行基准测试有一个流行的答案，但关于它在幕后如何工作的细节很少。

我可以阅读代码，但我并不真正理解所有内容，我希望我能找到一些外行人的代码。

flat_map 可能吗？将要？作为 C++23 的一部分，所以我很想了解它的优点和缺点，但我也很想了解它是如何实现的。显然是使用地图和矢量？无序版本怎么样？

这是否类似于对象池，其中在向量中间删除的项目被向量的最后一个项目替换以保持连续性？ flat_map 是否可以通过附加索引跟踪以某种方式工作？

Answer 1

第一个线索在类的声明中：

class AssocVector
    : private std::vector< std::pair<K, V>, A >

这告诉我们 AssocVector 只是一个键值对向量。

第二条线索就在构造函数中，并且在各种操作中更加隐含：

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 );
}

这首先从输入构造一个

std::map

并将其按 ordered by key 复制到底层向量。 同样，许多操作都使用

std::lower_bound

，这需要以下内容：

范围 [first, last) 必须相对于表达式元素进行分区 < 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. 完全排序的范围满足此标准。

因此，AssocVector 是一个键值对向量，它始终按键排序，并且不能包含给定键的重复值，就像

std::map

一样。