Vector insertion may cause all or part of iterators to fail, and deletion will only affect the deletion position and subsequent iterators; 2. Deque insertion or deletion will cause all iterators to fail; 3. List and forward_list insertion will not fail, and deletion will only delete the iterators to fail; 4. Array will never fail; 5. Set and map insertion will not fail, and deletion will only delete the elements to fail; 6. Unordered_set and unordered_map insertion will all fail, and deletion will only delete the elements to fail; 7. Clear operation will invalidate all its iterators for all containers; 8. Safety practices include using the erase return value to update the iterator, avoid modifying the container during traversal, and prioritizing the use of reserve and scope for loops, and ultimately the standard document shall prevail.

C Iterator Invalidation is an important issue that must be paid attention to when using STL containers. When an iterator fails, continuing to use it will result in undefined behavior. Different containers have different effects on the iterator under different operations. The following is a summary of iterator failure rules for common containers, based on C 11 and later standards.

1. Iterator failure rules for sequence containers

std::vector

• Insert operation :
  • If size() > capacity() after insertion (that is, reassignment occurs), all iterators will fail .
  • Otherwise, only the insertion position and subsequent iterators fail .
• Delete operation :
  • erase() : The deleted element and all iterators after it are invalid.
  • pop_back() : Only the end iterator is invalid.
• clear() / resize() / assign() / swap() :
  • All iterators fail.

?? Note: The memory of vector is continuous, and insertion may cause reallocation, so using reserve() can avoid unexpected failure.

std::deque

• Insert operation :
  • Insert in the middle or both ends: All iterators fail (As of C 11, all iterators fail as long as memory redistribution occurs).
  • But usually front-end/back-end inserts won't fail immediately unless the internal buffer is full.
• Delete operation :
  • Delete any element: All iterators are invalid .
• clear() / pop_front() / pop_back() : All iterators are invalid.

? deque is more prone to failure than vector , especially when inserting/deleting in the middle.

std::list / std::forward_list

• Insert operation : No iterators are invalidated .
• Delete operation :
  • Only the iterator of the deleted elements is invalid, others are still valid.
• clear() : All iterators are invalid.
• splice() : The iterator is still valid (elements move, not rebuild).

? list is one of the safest containers for frequent insertion/deletion.

std::array

• Fixed size, no insertion/deletion is supported.
• Iterator failure never occurs (unless the container itself is destroyed).
• Operations such as fill() , assign() do not change the iterator's validity.

2. Iterator failure rules for associated containers ( set , map , multiset , multimap )

• Insert operation : No iterators are invalidated .
• Delete operation :
  • Only the iterators of the deleted elements are invalid.
  • It is safe to use erase() to return the next valid iterator.
• clear() : All iterators are invalid.

? Associated containers are implemented using red and black trees, and node deletion does not affect other node pointers.

std::unordered_set / unordered_map (hash container)

• Insert operation :
  • If rehash is not triggered: only the iterators of the bucket that is inserted at the position may be affected, and other iterators are still valid .
  • If rehash occurs: all iterators fail , but the reference is still valid.
• Delete operation :
  • Only the iterators of the deleted elements are invalid.
• clear() / rehash() / reserve() / bucket_count() adjustment: All iterators are invalid.
• erase() does not affect the iterator of other elements.

?? Hash container will rebuild the bucket structure when rehashing, causing the iterator to fail.

3. Iterator failure summary table for common operations

4. Suggestions for safe use of iterators

• Avoid saving iterators that may fail , especially when modifying containers in loops.

• Update the iterator with the return value of erase() :

   for (auto it = vec.begin(); it != vec.end(); ) {
      if (should_remove(*it)) {
          it = vec.erase(it); // erase returns the next valid iterator} else {
            it;
      }
  }

• Use reserve() on vector to reduce redistribution.

• Avoid traversing and deleting without updating iterators in non- list or associated containers during traversal.

• Note when using a scope for loop: If the container is modified, the behavior is undefined.

Basically that's it. The key is to remember: vector and deque are the easiest to fail, list and associated containers are the safest, and hash containers are dangerous when rehashing . It is safest to check standard or authoritative documents (such as cppreference) when writing code.

The above is the detailed content of C iterator invalidation rules. For more information, please follow other related articles on the PHP Chinese website!