c++ unordered_set/unordered_multiset的迭代器失效

kh212irz  于 2023-11-19  发布在  其他
关注(0)|答案(2)|浏览(135)

我知道unordered_set在插入元素时可能会使迭代器无效:
如果(由于插入操作)发生重排序,则所有迭代器都将无效。
很明显,因为我们有哈希表和桶,但是为什么unordered_multiset使迭代器无效?
我认为unordered_set的实现与unordered_multiset(带桶的哈希表)的实现几乎相同。

bvjveswy

bvjveswy1#

实际上std::unordered_setstd::unordered_multiset在这方面没有**区别。
正如您在unordered_multiset::insert ducumentation中看到的,它包含与unordered_set::insert完全相同的注解:
如果发生了反汇编(由于插入),所有迭代器都将失效。
顺便说一句-在没有重复的情况下,它们也是相同的:
否则(不进行重排序),迭代器不会失效。
请注意,这并不意味着两个容器在迭代器失效时的行为总是相同的--因为控制是否发生重排序的策略可以不同。

aydmsdu9

aydmsdu92#

在C标准库中,unordered_set和unordered_multiset在插入期间关于迭代器无效的行为可能看起来相似,但在如何处理重复方面存在关键差异。
unordered_set:
在unordered_set中,每个元素都是唯一的,如果超过加载因子阈值,则插入操作可能会导致重新哈希。重新哈希涉及更改哈希表中的桶数,这可能会使迭代器无效,因为元素可能会移动到新的位置。unordered_multiset:
In an unordered_multiset, duplicate elements are allowed. When you insert an element, the insert operation adds it to the appropriate bucket without considering rehashing due to load factors. Since the number of buckets doesn't change during regular insertions (only when the container is resized), iterators are generally not invalidated during insertions. bucket中的现有元素不受新元素插入的影响,迭代器仍然可以指向正确的bucket。总之,关键的区别在于重复的处理。在unordered_multiset中,新元素的插入不会像unordered_set那样触发重复,因此,迭代器在常规插入过程中不太可能失效。检查您正在使用的C
实现的特定文档或标准总是很重要的,因为不同标准库实现之间的细节可能会有所不同。
是的,有区别,它可能不是那么多,但它仍然是一个相当有效的@沃尔斯塔德

相关问题