C++ 多索引映射实现 [英] C++ multi-index map implementation

问题描述

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

I'm implementing a multi-index map in C++11, which I want to be optimized for specific features. The problem I'm currently trying to solve, is to not store key elements more then once. But let me explain.

问题源于对直方图进行排序以将它们叠加在不同的组合中.直方图有名称，可以拆分为标记(属性).

The problem arose from sorting histograms to overlay them in different combinations. The histograms had names, which could be split into tokens (properties).

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

Here are the features I want my property map to have:

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

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

I have a working implementation in C++11 using std::unordered_map with std::tuple as key_type. I'm accumulating property values as they arrive into a tuple of forward_lists. The intended use, is to iterate over the lists to compose keys.

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

The optimization I would like to introduce, is to only store properties' value in the lists, and not store them in tuples used as keys in the map. I'd like to maintain ability to have functions returning const references to lists of property values, instead of lists of some wrappers.

我知道 boost::multi_index 具有类似的功能，但我不需要在密钥到达时进行排序的开销.我希望按顺序存储新的属性值，并且只能在事后进行排序.我也看过 boost::flyweight，但在最简单的方法中，列表将是 flyweight<T> 而不是 T，我不想这样做.(如果这是最好的解决方案，我绝对可以接受.)

I know that 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, but in the simplest approach, the lists will then be of flyweight<T> instead of T, and I'd like to not do that. (If that IS the best solution, I could definitely live with it.)

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

I know that lists are stable, i.e. once an element is created, its pointer and iterator remain valid, even after invoking list::sort(). Knowing that, can something be done to the map, to eliminate redundant copies of tuple elements? Could a custom map allocator help here?

感谢您的建议.

推荐答案

让你的地图从迭代器元组到你的道具容器.

Have your map be from tuples of iterators to your prop containers.

写一个散列来解引用迭代器并组合结果.

Write a hash the dereferences the iterators and combines the result.

将转发列表道具容器替换为先按哈希排序，然后按内容排序的集合.

Replace the forward list prop containers with sets that first order on hash, then contents.

首先在集合中查找，然后在哈希中查找.

Do lookup by first finding in set, then doing lookup in hash.

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

If you need a different order for props, have another container of set iterators.

这篇关于C++ 多索引映射实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！