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

问题描述

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

问题出在排序直方图，以不同的组合覆盖它们。

这里是我想要的属性映射的功能：

1. 能够以任何顺序循环属性;


2. 能够为每个属性返回具有唯一值的容器;


3. 按照它们到达的顺序累计属性值，但在填充地图后可以使用自定义比较运算符对属性进行排序;

我有一个工作实施 C ++ 11使用 std :: unordered_map 和 std :: tuple as key_type 。我积累的财产价值，当他们到达一个tuple的forward_lists。目的用途是迭代列表以组成键。

我想介绍的优化是只在列表中存储属性的值，而不是将它们存储在地图中用作键的元组中。我想保持能力让函数返回const引用的属性值列表，而不是一些包装器的列表。

我知道 boost :: multi_index 具有类似的功能，但我不需要当密钥到达时分类的开销。我想有新的属性值顺序存储，只有可排序postfactum。我还查看了 boost :: flyweight ，但是在最简单的方法中，列表将是 flyweight< T> 而不是 T 不喜欢不这样做。 （如果这是最好的解决方案，我肯定可以用它。）

我知道列表是稳定的，即一旦元素被创建，其指针和迭代器保持即使在调用 list :: sort（）后也是有效的。知道了，可以对地图做些什么，以消除元组元素的冗余副本？

解决方案

p>

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

用哈希和内容的第一顺序替换正向列表prop容器。

首先在set中查找，然后查找

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

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. Be able to loop over properties in any order;
2. Be able to return container with unique values for each property;
3. Accumulate properties' values in the order they arrive, but to be able to sort properties using a custom comparison operator after the map is filled;

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.

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.

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.)

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?

Thanks for suggestions.

解决方案

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屋！