<pre><code>std::vector&lt;int&gt; ints;

// ... fill ints with random values

for(std::vector&lt;int&gt;::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it &lt; 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}
</code></pre>

<p>This code is not working because when <code>pop_back()</code> is called, <code>it</code> is invalidated. But I don't find any doc talking about invalidation of iterators in <code>std::vector::pop_back()</code>.</p>

<p>Do you have some links about that?</p>

[{'answer_id': 62368, 'author': 'David Joyner', 'author_id': 1146, 'author_profile': 'https://Stackoverflow.com/users/1146', 'pm_score': 1, 'selected': False, 'text': '<p>Iterators are only invalidated on reallocation of storage.  Google is your friend: <a href="http://www.sgi.com/tech/stl/Vector.html" rel="nofollow noreferrer">see footnote 5</a>.</p>\n\n<p>Your code is not working for other reasons.</p>\n'}, {'answer_id': 62417, 'author': 'jvasak', 'author_id': 5840, 'author_profile': 'https://Stackoverflow.com/users/5840', 'pm_score': -1, 'selected': False, 'text': '<p>Check out the information <a href="http://www.cplusplus.com/reference/stl/vector/pop_back.html" rel="nofollow noreferrer">here (cplusplus.com)</a>:</p>\n\n<blockquote>\n  <p><strong>Delete last element</strong></p>\n  \n  <p>Removes the last element in the vector, effectively reducing the vector size by one and invalidating all iterators and references to it.</p>\n</blockquote>\n'}, {'answer_id': 62485, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Error is that when "it" points to the last element of vector and if this element is less than 10, this last element is removed. And now "it" points to ints.end(), next "it++" moves pointer to ints.end()+1, so now "it" running away from ints.end(), and you got infinite loop scanning all your memory :).</p>\n'}, {'answer_id': 62522, 'author': 'Ben', 'author_id': 6930, 'author_profile': 'https://Stackoverflow.com/users/6930', 'pm_score': 5, 'selected': True, 'text': '<p>The call to <a href="http://en.cppreference.com/w/cpp/container/vector/pop_back" rel="noreferrer"><code>pop_back()</code></a> removes the last element in the vector and so the iterator to that element is invalidated.  The <code>pop_back()</code> call does <em>not</em> invalidate iterators to items before the last element, only reallocation will do that.  From Josuttis\' "C++ Standard Library Reference":</p>\n\n<blockquote>\n  <p>Inserting or removing elements\n  invalidates references, pointers, and\n  iterators that refer to the following\n  element.  If an insertion causes\n  reallocation, it invalidates all\n  references, iterators, and pointers.</p>\n</blockquote>\n'}, {'answer_id': 62730, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': '<p>Here is a quote from SGI\'s STL documentation (<a href="http://www.sgi.com/tech/stl/Vector.html" rel="nofollow noreferrer">http://www.sgi.com/tech/stl/Vector.html</a>):</p>\n\n<p>[5] A vector\'s iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector\'s iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector\'s end. </p>\n\n<p>I think it follows that pop_back only invalidates the iterator pointing at the last element and the end() iterator. We really need to see the data for which the code fails, as well as the manner in which it fails to decide what\'s going on.  As far as I can tell, the code should work - the usual problem in such code is that removal of element and ++ on iterator happen in the same iteration, the way @mikhaild points out. However, in this code it\'s not the case: it++ does not happen when pop_back is called.</p>\n\n<p>Something bad may still happen when it is pointing to the last element, and the last element is less than 10. We\'re now comparing an <em>invalidated</em> it and end(). It may still work, but no guarantees can be made.</p>\n'}, {'answer_id': 62799, 'author': 'swmc', 'author_id': 7016, 'author_profile': 'https://Stackoverflow.com/users/7016', 'pm_score': 0, 'selected': False, 'text': '<p>The "official specification" is the C++ Standard.  If you don\'t have access to a copy of C++03, you can get the latest draft of C++0x from the Committee\'s website: <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf" rel="nofollow noreferrer">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf</a></p>\n\n<p>The "Operational Semantics" section of container requirements specifies that pop_back() is equivalent to { iterator i = end(); --i; erase(i); }.  the [vector.modifiers] section for erase says "Effects: Invalidates iterators and references at or after the point of the erase."</p>\n\n<p>If you want the intuition argument, pop_back is no-fail (since destruction of value_types in standard containers are not allowed to throw exceptions), so it cannot do any copy or allocation (since they can throw), which means that you can guess that the iterator to the erased element and the end iterator are invalidated, but the remainder are not.</p>\n'}, {'answer_id': 62840, 'author': 'jlehrer', 'author_id': 7013, 'author_profile': 'https://Stackoverflow.com/users/7013', 'pm_score': 4, 'selected': False, 'text': "<p>Here is your answer, directly from The Holy Standard:</p>\n\n<blockquote>\n23.2.4.2 A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1).\n</blockquote>\n\n<blockquote>\n23.1.1.12 Table 68\n\n\nexpressiona.pop_back()\nreturn typevoid\noperational semantics<strong>a.erase(--a.end())</strong>\ncontainervector, list, deque\n\n</blockquote>\n\n<p>Notice that a.pop_back is equivalent to a.erase(--a.end()).  Looking at vector's specifics on erase:</p>\n\n<blockquote>\n23.2.4.3.3 - iterator erase(iterator position) - effects - <strong>Invalidates all the iterators and references after the point of the erase</strong>\n</blockquote>\n\n<p>Therefore, once you call pop_back, any iterators to the previously final element (which now no longer exists) are invalidated.</p>\n\n<p>Looking at your code, the problem is that when you remove the final element and the list becomes empty, you still increment it and walk off the end of the list.</p>\n"}, {'answer_id': 62878, 'author': 'Pieter', 'author_id': 5822, 'author_profile': 'https://Stackoverflow.com/users/5822', 'pm_score': 3, 'selected': False, 'text': '<p>(I use the numbering scheme as used in the C++0x working draft, <a href="http://www.justsoftwaresolutions.co.uk/cplusplus/new-cplusplus-draft-and-concurrency-papers.html" rel="noreferrer">obtainable here</a></p>\n\n<p>Table 94 at page 732 says that pop_back (if it exists in a sequence container) has the following effect:</p>\n\n<pre><code>{ iterator tmp = a.end(); \n--tmp; \na.erase(tmp); } \n</code></pre>\n\n<p>23.1.1, point 12 states that:</p>\n\n<blockquote>\n  <p>Unless otherwise speciﬁed (either explicitly or by deﬁning a function in terms of other functions), invoking a container \n  member function or passing a container as an argument to a library function shall not invalidate iterators to, or change \n  the values of, objects within that container.</p>\n</blockquote>\n\n<p>Both accessing end() as applying prefix-- have no such effect, erase() however:</p>\n\n<p>23.2.6.4 (concerning vector.erase() point 4):</p>\n\n<blockquote>\n  <p>Effects: Invalidates iterators and references at or after the point of the erase. </p>\n</blockquote>\n\n<p>So in conclusion: pop_back() will only invalidate an iterator to the last element, per the standard.</p>\n'}, {'answer_id': 62988, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>pop_back() will only invalidate <strong>it</strong> if <strong>it</strong> was pointing to the last item in the vector. Your code will therefore fail whenever the last int in the vector is less than 10, as follows:</p>\n\n<p>*it = ints.back(); // Set *it to the value it already has<br>\n   ints.pop_back(); // Invalidate the iterator<br>\n   continue; // Loop round and access the invalid iterator  </p>\n'}, {'answer_id': 63135, 'author': 'NeARAZ', 'author_id': 6799, 'author_profile': 'https://Stackoverflow.com/users/6799', 'pm_score': 1, 'selected': False, 'text': '<p><code>pop_back()</code> invalidates only iterators that point to the last element. From C++ Standard Library Reference:</p>\n\n<blockquote>\n  <p>Inserting or removing elements\n  invalidates references, pointers, and\n  iterators that refer to the following\n  element. If an insertion causes\n  reallocation, it invalidates all\n  references, iterators, and pointers.</p>\n</blockquote>\n\n<p>So to answer your question, no it does not invalidate <em>all</em> iterators.</p>\n\n<p>However, in your code example, it can invalidate <strong><code>it</code></strong> when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.</p>\n\n<p>If iterators are implemented as pure pointers (as they would in probably all non-debug STL vector cases), your code should just work. If iterators are more than pointers, then your code does not handle this case of removing the last element correctly.</p>\n'}, {'answer_id': 415847, 'author': 'CB Bailey', 'author_id': 19563, 'author_profile': 'https://Stackoverflow.com/users/19563', 'pm_score': 0, 'selected': False, 'text': '<p>You might want to consider using the return value of erase instead of swapping the back element to the deleted position an popping back. For sequences erase returns an iterator pointing the the element one beyond the element being deleted. Note that this method may cause more copying than your original algorithm.</p>\n\n<pre><code>for(std::vector&lt;int&gt;::iterator it = ints.begin(); it != ints.end(); )\n{\n    if(*it &lt; 10)\n        it = ints.erase( it );\n    else\n        ++it;\n}\n</code></pre>\n\n<p><code>std::remove_if</code> could also be an alternative solution.</p>\n\n<pre><code>struct LessThanTen { bool operator()( int n ) { return n &lt; 10; } };\n\nints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );\n</code></pre>\n\n<p><code>std::remove_if</code> is (like my first algorithm) stable, so it may not be the most efficient way of doing this, but it is succinct.</p>\n'}]
['https://Stackoverflow.com/questions/62340', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/6605/']