Summary of STL's erase of trap iterator failure problem

The material below is collated from Internet& works.

Containers in STL are divided into two categories according to the way they are stored. The first category is containers that are stored in an array (e.g. vector, deque). The other is containers that are stored as discrete nodes (e.g., list, set, map). There are a few issues to be aware of when using the erase method to delete elements.

1. list set, map container

When using list, set, or map to traverse the removal of certain elements:

1.1 correct writing 1

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
      itList = List.erase( itList);
    }
    else
      itList++;
}

1.2 correct writing 2

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
     List.erase( itList++);
   }
   else
     itList++;
}

1.3 incorrect writing 1

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); itList++)
{
  if( WillDelete( *itList) )
  {
     List.erase( itList);
  }
}

1.4 error 2

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
     itList = List.erase( ++itList);
   }
   else
     itList++;
}

1.5 analysis

Method 1: get the location of the next element by the return value of the erase method

Use method 2 correctly: use "++" to get the location of the next element before calling the erase method

Error using method 1: after calling the erase method, use "++" to get the location of the next element, since the location of the element is already there after calling the erase method

Is deleted. If the next location is retrieved from the old location, an exception will occur.

Wrong use method 2: ibid.

2. vector, deque container

When deleting elements through vector and deque, the position of the next element can also be obtained through the return value of erase:

2.1 correct writing

std::vector< int> Vec;
std::vector< int>::iterator itVec;
for( itVec = Vec.begin(); itVec != Vec.end(); )
{
 if( WillDelete( *itVec) )
 {
   itVec = Vec.erase( itVec);
  }
 else
   itList++;
}

2.2 pay attention to

Note: vector and deque cannot traverse deletions like the "use method 2 correctly" method above. Please refer to Effective STL clause 9 for the reason. Excerpt below:

1)   for associating containers (such as map, set, multimap,multiset), deleting the current iterator will only invalidate the current iterator, as long as the current iterator is increments at erase. This is because containers such as map are implemented using red-black trees, and the insertion and deletion of one node will not affect other nodes.

for (iter = cont.begin(); it != cont.end();)
{
(*iter)->doSomething();
if (shouldDelete(*iter))
 cont.erase(iter++);
else
 ++iter;
}

Since iter passes one copy to the erase method, iter++ will point to the next element.

2) for sequential containers (such as vector,deque), deleting the current iterator will invalidate the iterator of all subsequent elements. This is because vetor,deque USES continuously allocated memory, and removing one element causes all subsequent elements to move forward one location. Fortunately, the erase method returns the next valid iterator.

for (iter = cont.begin(); iter != cont.end();)
{
(*it)->doSomething();
if (shouldDelete(*iter))
 iter = cont.erase(iter); 
else
 ++iter;
}

3) for list, it USES discontinuous allocated memory, and its erase method will also return the next valid iterator, so the above two methods can be used.

3. Failure of the iterator

3.1 vector

Internal data structure: array.

The time required to access each element at random is constant.

The time required to add or remove elements at the end is independent of the number of elements, and the time required to add or remove elements at the middle or beginning varies linearly with the number of elements.

You can dynamically add or subtract elements, and memory management is done automatically, but programmers can use the reserve() member function to manage memory.

The iterator of vector fails when memory is reallocated (the elements it points to are no longer the same before and after the operation). When more than capacity() -size () elements are inserted into vector, memory is reallocated and all iterators fail. Otherwise, the iterator that points to any element after the current element will fail. When an element is deleted, the iterator that points to any element after the deleted element is invalidated.

3.2 deque

Internal data structure: array.

The time required to access each element at random is constant.

The time required to add elements at the beginning and end is independent of the number of elements, while the time required to add or remove elements in the middle varies linearly with the number of elements.

You can add or subtract elements dynamically, memory management is done automatically, and no member functions are provided for memory management.

Adding any element will invalidate the iterator of deque. Deleting an element in the middle of deque will invalidate the iterator. When an element is deleted from the head or tail of deque, only the iterator pointing to that element fails.

3.3 list

Internal data structure: bidirectional circular linked list.

You cannot access an element at random.

Can be bidirectional traversal.

The time required to add or remove elements at the beginning, end, and anywhere in between is constant.

You can add or subtract elements dynamically, and memory management is done automatically.

Adding any element does not invalidate the iterator. When an element is deleted, no iterator fails except the iterator that points to the currently deleted element.

3.4 slist

Internal data structure: unidirectional linked list.

Not bidirectional traversal, can only traverse from the front to the back.

Other features are similar to list.

3.5 stack

Adapter, which can convert any type of sequence container into a stack, generally using deque as the supported sequence container.

Elements can only be last in, first out (LIFO).

You cannot traverse the entire stack.

3.6 queue

Adapter, which can convert any type of sequence container to a queue, generally using deque as the supported sequence container.

Elements can only be first in first out (FIFO).

You cannot traverse the entire queue.

3.7 priority_queue

Adapter, which can convert any type of sequence container into a priority queue using vector as the underlying storage.

Only the first element can be accessed, and the entire priority_queue cannot be traversed.

The first element is always the one with the highest priority.

3.8 set

The keys are the same as the values.

Key only 1.

Elements are sorted in ascending order by default.

If the element pointed to by the iterator is deleted, the iterator fails. Anything else that adds or removes elements does not invalidate the iterator.

3.9 multiset

Keys can be more than 1.

Other features are the same as set.

3.10 hash_set

In comparison with set, the elements in it are not necessarily sorted, but assigned according to the hash function used, which provides a faster search speed (related to hash, of course).

Other features are the same as set.

3.11 hash_multiset

Keys can be more than 1.

Other features are the same as hash_set.

3.12 map

Key only 1.

Element default keys are arranged in ascending order.

If the element pointed to by the iterator is deleted, the iterator fails. Anything else that adds or removes elements does not invalidate the iterator.

3.13 multimap

Keys can be more than 1.

Other features are the same as map.

3.14 hash_map

In comparison with map, the elements in map are not sorted by key value, but assigned by the hash function used, which can provide faster search speed (also related to hash function, of course).

Other features are the same as map.

3.15 hash_multimap

Keys can be more than 1.

Other features are the same as hash_map.