2

std::unordered_map<K,T>提供类似findwhich return a 的方法std::unordered_map<K,T>::iterator。据我所知，除非发生重新散列，否则迭代器仍然有效。

但我的怀疑是往返::iterator-> T *->没有保证的方式::iterator，类似于在 Linux 链表中完成的“hack”。我认为这是因为迭代器只需要通过 取消引用->second，但我看不出容器内需要在哪里具有持久存储类型。

那么，我说的对吗？我是否需要保留迭代器或T *ptr = &myiterator->second稍后可回溯到->second成员地址为的迭代器指针ptr？

这个问题自然也适用于其他容器的迭代器。

4

2 回答 2

2

第一个问题很简单：一般来说，没有直接的方法可以从指向元素的指针或值中获取迭代器。也就是说，要从一个值中获取迭代器，您通常需要搜索容器。由于std::vector<T>需要是连续的，因此您可以使用简单的计算从指针中获取迭代器（这需要v非空）：

std::vector<T> v(...);
T* ptr = ...;
std::vector<T>::iterator it(v.begin() + (ptr - &v[0]));

跟踪迭代器和值是否保持稳定并不是一件容易的事，因为相关的保证分布在多个子句中，例如：

  1. 23.2.1 [container.requirements.general] 第 11 段：

    除非另有规定（明确地或通过根据其他函数定义函数），调用容器成员函数或将容器作为参数传递给库函数不应使该容器内对象的迭代器无效或更改其值.

  2. 23.2.4 [associative.reqmts] 第 9 段：

    insert 和 emplace 成员不应影响迭代器和对容器的引用的有效性，而擦除成员应仅使迭代器和对被擦除元素的引用无效。

  3. 23.2.5 [unord.req] 第 9 段：

    ...重新散列使迭代器无效，更改元素之间的顺序，并更改出现在哪个桶中的元素，但不会使指针或对元素的引用无效。...

  4. 23.2.5 [unord.req] 第 14 段：

    insert 和 emplace 成员不应影响对容器元素的引用的有效性，但可能会使容器的所有迭代器无效。...

  5. 23.2.5 [unord.req] 第 15 段：

    如果 (N+n) < z * B，insert 和 emplace 成员不会影响迭代器的有效性，其中 N 是插入操作之前容器中的元素数，n 是插入的元素数，B 是容器的桶数，z 是容器的最大负载因子。

上述条款应该是关于关联容器的迭代器有效性的重要条款。无序关联容器中的迭代器有效性完全取决于容器是否被重新散列。似乎可以控制重新散列以避免意外发生。

然而，无序容器的整个想法是使用find(). 永远不需要将迭代器存储到元素，因为您可以找到它们。当然，如果您有 astd::unordered_multimap<K, V>或 astd::unordered_multiset<V>您可能需要知道您正在查看哪些等效元素。

于 2013-08-25T12:16:54.903 回答
1

当您向容器添加元素时，关联容器（set、multi_set、map、multi_map和它们的unordered_兄弟）不会使指针或引用无效；他们可以使迭代器无效。此外，当您删除元素时，只有迭代器、指针和对这些元素的引用无效。这样做的一个后果是，如果您获取一个元素的地址，只要该元素保留在容器中，该地址就会保持有效。

没有可移植的方法可以直接将元素的地址转换为指向该元素的迭代器。如果你需要这样做，你必须搜索元素。

于 2013-08-25T12:04:51.537 回答