std :: unordered_set是否连续（例如std :: vector）？ [英] Is std::unordered_set contiguous (like std::vector)?

问题描述

我将指针存储在std :: unordered_set中。之所以这样做，是因为我不希望有任何重复项（我删除了集合中的指针，因此，如果有重复项，我将尝试删除一个已经删除的指针）。我遍历了这些集合，并且由于我知道std :: vector是最快的循环容器（连续内存），所以我想知道std :: unordered_set是否也能做到这一点。

I'm storing pointers in std::unordered_set. I do this because I don't want any duplicates (I delete the pointers in the collection, so if there is a duplicate, I will attempt to delete an already deleted pointer). I loop heavily through these sets, and since I know std::vector is the fastest container for looping (contiguous memory), I wondered if std::unordered_set does the same.

如果不会，使用std :: vector并检查指针是否已被删除会更快吗？

If it doesn't, would using a std::vector and checking if the pointer has already been deleted be faster?

推荐答案

std :: unordered_set 是连续的吗？

确切该标准并未详细介绍容器的实现... 但是该标准确实规定了一些限制实际表示的行为。

The exact implementation of containers is not detailed by the standard... however the standard does prescribes a number of behaviors which constrains the actual representation.

例如， std :: unordered_set 必须是内存稳定的：对元素的引用/地址即使在添加/删除 other 元素时也有效

For example, std::unordered_set is required to be memory stable: a reference to/address of an element is valid even when adding/removing other elements.

实现此目标的唯一方法是或多或少地独立分配元素。使用连续的内存分配无法实现此目的，因为这样的分配必然会受到限制，因此可能会变得过于庞大，无法在更大的块中重新分配元素。

The only way to achieve this is by allocating elements more or less independently. It cannot be achieved with a contiguous memory allocation as such an allocation would necessarily be bounded, and thus could be overgrown with no possibility of re-allocating the elements in a bigger chunk.

这篇关于std :: unordered_set是否连续（例如std :: vector）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！