关于STL容器在C ++中的问题 [英] Questions about STL containers in C++

问题描述

1. std :: multimap和std :: unordered_multimap多久修改一次条目？我问，因为我的代码传递引用以区分具有相同的散列的条目，我想知道什么时候对它们运行参考重定向功能。




2. 如果我这样做会发生什么：

     std :: multimap atable; // Type specification stuff left out 
    //在两个条目中使用相同键值的代码，调用该键foo 
    int bar = atable [foo]; 
     




3. 如果结果是unordered_multimap，结果是否不同？

   
   

4. 回到传递引用以区分具有相同散列的条目。有更安全的方法吗？




5. 如果我删除了一个条目，这些条目移动（这是阅读文档的建议std :: vector）？

解决方案

否，任何操作都不会损害任何元素。 p>

如 这个着名的Q& A ，对于关联容器，在插入/擦除时不存在迭代器无效（除了当然被删除的元素）。对于无序的关联容器，在重新散列期间存在迭代器无效，标准称之为（强调我的）

23.2.5无序关联容器[unord.req]

9无序关联容器的元素组织为
桶。具有相同散列码的密钥出现在同一个存储桶中。随着元素被添加到
无序关联容器中，
桶的数量自动增加，使得每桶的
元素的平均数量保持在边界以下。 重新散列无效的
迭代器，更改元素之间的顺序以及
buckets元素出现的更改，但不会使指针无效或
引用元素<强>。对于unordered_multiset和unordered_multimap，
rehashing保留等效元素的相对排序。

同样，这不需要reshuflling在 unordered_map< Key，Value>中键入实际存储的元素（ Key 和 Value / code>），因为无序映射具有被组织为链表的桶，并且对存储的元素（键 - 值对）的迭代器具有元素指针和桶指针。重新散列洗牌桶，使迭代器无效（因为它们的桶指针无效），而不是指向元素本身的指针或引用。有关详情，请参阅 另一个问答

1. How often do std::multimap and std::unordered_multimap shuffle entries around? I'm asking because my code passes around references to distinguish between entries with the same hash, and I want to know when to run the reference redirection function on them.

2. What happens if I do this:

   std::multimap atable; //Type specification stuff left out
   //Code that pus in two entries with the same key, call that key foo
   int bar = atable[foo];
   

3. Is the result different if it's an unordered_multimap instead?

4. Back to passing references around to distinguish entries with the same hash. Is there a safer way to do that?

5. Do the entries move around if I remove one of the entries (That's what's suggested by a reading of the documentation for std::vector)?

解决方案

NO, no elements will be harmed during any operation.

As is explained in this famous Q&A, for associative containers, there is no iterator invalidation upon insertions / erasure (except for the element being erased of course). For unordered associative containers, there is iterator invalidation during rehashing, about which the Standard says (emphasize mine)

23.2.5 Unordered associative containers [unord.req]

9 The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements.

Again, this does not entail the reshuflling of the actually stored elements (the Key and Value types in unordered_map<Key, Value>), because unordered maps have buckets that are organized as linked lists, and iterators to stored elements (key-value pairs) have both an element pointer and a bucket pointer. The rehashing shuffles buckets, which invalidates the iterators (because their bucket pointer is invalidated) but not pointers or references to the elements itself. This is explained in detail in another Q&A

这篇关于关于STL容器在C ++中的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！