Iterator safety guarantees for C++ container libraries

C++ container library provides the following mechanisms to ensure the safety of iterators: 1. Container immutability guarantee; 2. Copy iterator; 3. Range for loop; 4. Const iterator; 5. Exception safety.

Guarantees of iterator safety in C++ container library

In C++, the container library provides iterators that allow us to traverse the elements in the container. To prevent accidental modification of the container during iteration, the C++ container library provides several mechanisms to ensure the safety of iterators.

1. Container immutability guarantee

When a container is in a valid state, its content, size and element order are determined. The container library ensures that this invariance is maintained during iteration. The iterator becomes invalid when trying to add or remove elements from the iterated container. For example:

std::vector<int> v{1, 2, 3};
for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
  v.push_back(4); // 迭代器无效，引用不再有效
}

2. Copying an Iterator

In C++, an iterator can be copied, creating a new iterator pointing to the same element. This allows us to create copies of the iterators and continue to use them if the container is unexpectedly modified. Copy iterators are not affected by modifications to the original container, even if the original container has changed or expired.

3. Range for loop

Range for loop implicitly uses a copy iterator, allowing us to traverse the elements in the container without worrying that modifications to the container will affect the iteration .

for (int& elem : v) {
  // 使用 elem...
  v.push_back(4); // 不会影响范围 for 循环
}

4. Const iterator

const iterator refers to the read-only elements in the container. Attempting to modify a container via a const iterator will result in a compile-time error. This ensures data integrity when traversing the container.

5. Exception safety

The container library detects exceptions during iteration and automatically invalidates the iterator when the exception is thrown. This prevents access to corrupted containers.

Practical Case: Safely Remove Elements from a Map

std::map is an ordered associative container that allows us to search based on keys value. When iterating over a map, if we try to delete an element of the current iteration, the iterator will become invalid because the underlying map has changed. To safely delete elements, we can use the erase method, which returns a new valid iterator pointing to the successor of the deleted element.

std::map<int, int> m{{1, 10}, {2, 20}, {3, 30}};
for (auto it = m.begin(); it != m.end(); ) {
  if (it->second % 2 == 0) {
    it = m.erase(it); // 返回新的有效迭代器
  } else {
    ++it;
  }
}

The above is the detailed content of Iterator safety guarantees for C++ container libraries. For more information, please follow other related articles on the PHP Chinese website!