Boost.Multiindex composite_key密钥存储

Question

假设我为一个boost::multi_index_container形成了一个由三个整数成员组成的composite_key。键将跨越某个范围({0，0，0}，{0，0，1}，{0，0，2}等)中三个整数的每个组合。在内部，boost将这些整数组合中的每一个存储为键，这样键的总数将是N x N x N，其中N是范围内的元素数，其中散列的键可以是字节数的3倍。或者，它是否试图通过内部使用哈希表树来节省内存，这将减少总索引字节大小？

我在尝试自己创建哈希表的树是否会减少总的索引字节大小。

Answer 1

散列索引的大小/开销是每个元素2+1/LF个指针，其中LF是索引负载因子。LF通常在MLF/2和MLF之间，其中MLF是允许的最大负载因子，默认情况下为1，因此开销范围在每个元素的2+2=4和2+1=3指针之间，平均为每个元素3.5个指针。

请注意，这种开销与用于索引的键(提取器)完全无关：composite_key和Boost.MultiIndex提供的任何其他键提取器都不会存储/缓存任何类型的键信息。在您的场景中，每次需要时都会动态计算来自三个整数数据成员的组合哈希。

Answer 2

索引表示的结果取决于索引的类型。对于hashed_unique/unordered_unique，您可以假定底层索引被组织为树。

然而，主存储不一定是最优的。所有多重索引容器都是基于节点的，这意味着不能保证元素在内存中是连续的(但在删除之前总是保持引用/迭代器的稳定性)。这并不意味着所有节点都必须单独分配:这可以通过库进行优化，也可以通过使用自定义分配器来影响。

长话短说，我可能会考虑

• boost::flat_map >或类似的
• boost struct R { int a,b,c; }多索引容器(或实际上相同的元组)，使用合适的池分配器。

为了便于比较，您实际上可以同时使用flat_map或向量，并使用多索引容器与T*__、T&或reference_wrapper<T>一起使用，而不是T__。我不确定存储空间的减少会是多少(可能是每个元素2个指针大小？)但至少它让您可以独立于存储来测量索引大小--

平面映射具有优势，因为它为迭代器/引用无效而牺牲了引用的局部性。

要测量实际的内存占用，请使用堆分析器(例如valgrind --tool=massif)。