C++多索引图实现

Question

我正在用 C++11 实现多索引映射，我想针对特定功能对其进行优化。我目前正在尝试解决的问题是不要多次存储关键元素。但是让我解释一下。

问题源于排序直方图以不同组合叠加它们。直方图有名称，可以拆分为标记（属性）。

以下是我希望我的 属性 地图具有的功能：

1. 能够以任何顺序遍历属性；
2. 能够 return 容器具有每个 属性;
的唯一值
3. 按属性值到达的顺序累积属性值，但能够在填充地图后使用自定义比较运算符对属性进行排序；

我在 C++11 中有一个 working implementation，使用 std::unordered_map，std::tuple 作为 key_type。当它们到达 forward_lists 的元组时，我正在累积 属性 个值。预期用途是遍历列表以组成键。

我想介绍的优化是只将属性的值存储在列表中，而不将它们存储在用作映射键的元组中。我想保持函数 returning 对 属性 值列表的 const 引用的能力，而不是某些包装器列表的能力。

我知道 boost::multi_index has similar functionality, but I don't need the overhead of sorting as the keys arrive. I'd like to have new property values stored sequentially, and only be sortable postfactum. I've also looked at boost::flyweight，但在最简单的方法中，列表将是 flyweight<T> 而不是 T，我不想那样做。 （如果这是最好的解决方案，我绝对可以接受。）

我知道列表是稳定的，即一旦创建了一个元素，它的指针和迭代器仍然有效，即使在调用 list::sort() 之后也是如此。知道这一点后，是否可以对地图做些什么来消除元组元素的冗余副本？自定义地图分配器可以提供帮助吗？

感谢您的建议。

Answer 1

让你的映射从迭代器的元组到你的道具容器。

写一个散列来取消对迭代器的引用并合并结果。

将前向列表 prop 容器替换为首先在哈希上排序的集合，然后是内容。

首先在集合中查找，然后在散列中查找。

如果您需要不同的道具顺序，请使用另一个集合迭代器容器。