How to Efficiently Remove Elements from a std::vector During Iteration?

Efficiently Removing Elements from a std::vector During Iteration

When iterating over a std::vector and performing actions that require modifying the vector's size, such as deleting elements, you may encounter the issue of invalidating iterators. This is because the erase() method used for removing elements changes the vector's size and invalidates all existing iterators.

Avoiding Invalid Iterators

To overcome this, an efficient solution is to use the return value of the erase() method, which provides a new, valid iterator pointing to the element immediately following the deleted one. This allows you to continue the iteration without having to worry about invalidated iterators.

The following code demonstrates this approach:

<code class="cpp">std::vector<std::string>::iterator iter;
for (iter = m_vPaths.begin(); iter != m_vPaths.end(); ) {
    if (::DeleteFile(iter->c_str())) {
        iter = m_vPaths.erase(iter);  // Returns a new valid iterator
    } else {
        ++iter;  // Advance iterator if file deletion failed
    }
}</code>

In this code, the iter iterator is updated to point to the next element after each successful file deletion, allowing the iteration to proceed smoothly.

Alternative Data Structures

While using the iterator approach is efficient, it still modifies the original m_vPaths vector, which may have performance implications if you need to make multiple deletions. In such cases, it may be better to consider using an alternative data structure that is optimized for deleting elements efficiently, such as:

• std::list: A doubly-linked list that allows for efficient removal of elements in O(1) time complexity.
• std::set: An ordered set that automatically removes duplicate elements and supports efficient removal operations.
• std::unordered_set: An unordered set that also supports efficient element removal, but it's important to note that iteration order is not guaranteed.

The above is the detailed content of How to Efficiently Remove Elements from a std::vector During Iteration?. For more information, please follow other related articles on the PHP Chinese website!