是否有大小为N的c ++标准库容器，该容器具有log（N）插入和搜索，但是具有N次迭代，而不是N * log（N）？ [英] Is there a c++ standard library container of size N that has log(N) insertion and search yet has N iteration instead N*log(N)?

问题描述

我看了这个问题： boost :: flat_map及其与map和unordered_map 相比的性能，发现v.oddou的答案显示了std :: map与其他容器的迭代器图，而我发现std :: map在遍历所有对象时非常慢元素。令我感到困惑的是，我认为std :: map迭代缓慢的原因是因为它按键顺序显示所有元素。我相信，如果将std :: map构造为一个数组，并使用特殊的索引公式（我不记得其引用位置）来跟踪二叉树结构，则可以按顺序快速遍历该数组，但是可以使用键将无序显示。但是，我一直找不到在c ++中执行此操作的标准容器。像map这样的数组的唯一瓶颈是动态调整大小将是昂贵的，但是，如果您只想在每次达到大小限制时才将数组大小加倍，则可以长时间获得N * log（N）的平均插入时间计算。我查看了伪代码，该伪代码解释了具有树关联方向（父代，左子代，右子代）的节点指针的构造，但是我无法确定是否可以修改此节点结构以添加一维无序关联性。

I looked at this question: boost::flat_map and its performance compared to map and unordered_map and discovered that v.oddou's answer shows iterator plots for std::map versus other containers and I discovered that std::map is very slow at iterating over all the elements. What puzzled me about this is I assume the reason std::map is slow at iterating is because it presents all elements in key order. I believe that if std::map was constructed as an array and using the special index formula (I do not remember where its referenced) for keeping track of the binary tree structure, then you could iterate quick through the array sequentially, but the keys will be presented unordered. However, I have been unable to find a standard container that does this in c++. The only bottleneck for an array like map is that dynamic resizing will be expensive, however if you are only interested in doubling the array size each time you hit the size limit, you can achieve N*log(N) average insertion time over a long computation. I looked at the pseudo code that explains the construction of nodal pointers that have tree association directions (parent, left child, right child) and I was unable to determine if this nodal structure can be modified to add a one-dimensional unordered associativity.

是否存在大小为N的c ++标准库容器，该容器具有log（N）插入和搜索功能，但具有N次迭代而不是N * log（N）？

Is there a c++ standard library container of size N that has log(N) insertion and search yet has N iteration instead N*log(N)?

编辑：

在插入复杂度方面似乎有些混乱，有些人建议插入为N而不是N * log（N）用于有序地图。在我的OP中，我没有说清楚，但是我正在考虑在您不知道下一个元素是什么的时候插入一个元素。我相信，如果您一次拥有所有要素，则可能可以在N次执行。我的来源是 map ::插入。

There appears to be confusion regarding insertion complexity, where some have suggested its N and not N*log(N) for ordered maps. In my OP I did not make it clear, but I was thinking of insertion of one element at a time where you do not know what the next element will be. I believe that if you have all of the elements at once you could probably do it N time. My source is map::insert.

推荐答案

我相信，如果std :: map被构造为数组并使用特殊的索引公式（我不记得在哪里它的引用）以跟踪二叉树结构，然后您可以顺序地快速遍历数组，但是键将无序显示。

I believe that if std::map was constructed as an array and using the special index formula (I do not remember where its referenced) for keeping track of the binary tree structure, then you could iterate quick through the array sequentially, but the keys will be presented unordered.

当数组需要增长时，由于重新分配，这会使迭代器和指针无效，而代价是。

This would come at a price of invalidating iterators and pointers due to re-allocation when array needs growth. Also iterators and pointers may invalidate on any insertion due to re-balancing.

迭代器和指针的无效性使得不可能在 std中使用这种结构： ：map 。

Iterators and pointers invalidation makes it impossible to use such structure for std::map.

像map这样的数组的唯一瓶颈是动态调整
的大小。昂贵的

The only bottleneck for an array like map is that dynamic resizing will be expensive

在插入/删除操作上进行重新平衡还比较复杂，您必须四处移动元素数据（大概在乎异常安全）。但是，这样的容器可能有用。

Also re-balancing on insertion/deletion is somewhat more complex, you'll have to move elements data around (probably caring about exception safety). Yet, such a container may be useful.

如果您想进行线性迭代，则可以始终使用侵入式双向链表用于 std :: map 的元素。参见 boost :: intrusive :: list 。尽管这种线性并不会像遍历数组那样快，但是由于连续数组对缓存更友好。

If you want linear iteration, you can always use intrusive double-linked list for elements of your std::map. See boost::intrusive::list. Though this "linear" will not be as fast as iterating over an array, since continuous array is more cache-friendly.

这篇关于是否有大小为N的c ++标准库容器，该容器具有log（N）插入和搜索，但是具有N次迭代，而不是N * log（N）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！