Do Stl Iterators Guarantee Validity After Collection Was Changed

Do STL iterators guarantee validity after collection was changed?

Depends on the container. e.g. if it's a vector, after modifying the container all iterators can be invalidated. However, if it's a list, the iterators irrelevant to the modified place will remain valid.

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. [1]
The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element. [2]
Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. [3]
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. [4] (same for set, multiset and multimap)

Confused use of c++ STL iterator

Since you called begin() when the container was empty, you got an iterator that was equal to end() (§23.1/7: "If the container is empty, then begin() == end()").

Inserting items into the container didn't change that, so you still have pos == intIntMap.end().

You then execute zero iterations of your loop, since pos==end(), and you'r executing the loop only as long as pos != end().

In the second example, you set pos() after you've inserted the data, so you get the first items in the collection, and iterate to the last.

Edit: As far as printing out the contents of the map goes, I'd probably do it more like this:

std::ostream &operator<<(std::ostream &os, std::pair<int, int> const &d) { 
    return os << d.first << " <---> " << d.second;
}

// ...

std::copy(intIntMap.begin(), intIntMap.end(), 
          std::ostream_iterator<std::pair<int, int> >(std::cout, "\n"));

Are iterators still valid when the underlying elements have been moved?

Yes, you've modified the object in the container. You've not modified the container itself so the iterator is still valid

Iterator invalidation rules for C++ containers

C++17 (All references are from the final working draft of CPP17 - n4659)

Insertion

Sequence Containers

vector: The functions insert, emplace_back, emplace, push_back cause reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation
happens, all the iterators and references before the insertion point remain valid. [26.3.11.5/1]

With respect to the reserve function, reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity(). [26.3.11.3/6]
deque: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. [26.3.8.4/1]
list: Does not affect the validity of iterators and references. If an exception is thrown there are no effects. [26.3.10.4/1].

The insert, emplace_front, emplace_back, emplace, push_front, push_back functions are covered under this rule.
forward_list: None of the overloads of insert_after shall affect the validity of iterators and references [26.3.9.5/1]
array: As a rule, iterators to an array are never invalidated throughout the lifetime of the array. One should take note, however, that during swap, the iterator will continue to point to the same array element, and will thus change its value.

Associative Containers

All Associative Containers: The insert and emplace members shall not affect the validity of iterators and references to the container [26.2.6/9]

Unordered Associative Containers

All Unordered Associative Containers: Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. [26.2.7/9]

The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. [26.2.7/14]

The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor. [26.2.7/15]
All Unordered Associative Containers: In case of a merge operation (e.g., a.merge(a2)), iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid. (Table 91 — Unordered associative container requirements)

Container Adaptors

stack: inherited from underlying container
queue: inherited from underlying container
priority_queue: inherited from underlying container

Erasure

Sequence Containers

vector: The functions erase and pop_back invalidate iterators and references at or after the point of the erase. [26.3.11.5/3]
deque: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.
[ Note: pop_front and pop_back are erase operations. —end note ] [26.3.8.4/4]
list: Invalidates only the iterators and references to the erased elements. [26.3.10.4/3]. This applies to erase, pop_front, pop_back, clear functions.

remove and remove_if member functions: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements [26.3.10.5/15].

unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.10.5/19]
forward_list: erase_after shall invalidate only iterators and references to the erased elements. [26.3.9.5/1].

remove and remove_if member functions - Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). Invalidates only the iterators and references to the erased elements. [26.3.9.6/12].

unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.9.6/16]
All Sequence Containers: clear invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator (Table 87 — Sequence container requirements). But for forward_list, clear does not invalidate past-the-end iterators. [26.3.9.5/32]
All Sequence Containers: assign invalidates all references, pointers and
iterators referring to the elements of the container. For vector and deque, also invalidates the past-the-end iterator. (Table 87 — Sequence container requirements)

Associative Containers

All Associative Containers: The erase members shall invalidate only iterators and references to the erased elements [26.2.6/9]
All Associative Containers: The extract members invalidate only iterators to the removed element; pointers and references to the removed element remain valid [26.2.6/10]

Container Adaptors

stack: inherited from underlying container
queue: inherited from underlying container
priority_queue: inherited from underlying container

General container requirements relating to iterator invalidation:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [26.2.1/12]
no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ] [26.2.1/(11.6)]

As examples of the above requirements:

transform algorithm: The op and binary_op functions shall not invalidate iterators or subranges, or modify elements in the ranges [28.6.4/1]
accumulate algorithm: In the range [first, last], binary_op shall neither modify elements nor invalidate iterators or subranges [29.8.2/1]
reduce algorithm: binary_op shall neither invalidate iterators or subranges, nor modify elements in the range [first, last]. [29.8.3/5]

and so on...

Keeping std::list iterators valid through insertion

if (readpos == buf.begin())
{
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    readpos = buf.begin();
}
else
{
    --readpos;
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    ++readpos;
}

Not elegant, but it should work.

Are references / pointers guaranteed to be valid after moving std::deque?

Pointers to elements would remain valid. After move construction:

After container move construction (overload (8)), references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this. The current standard makes this guarantee via the blanket statement in [container.requirements.general]/12, and a more direct guarantee is under consideration via LWG 2321.

How does std::vector::end() iterator work in memory?

you asked about "the underlying mechanic of vector.end()". Well here is (a snippet of) an oversimplified vector that is easy to digest:

template <class T>
class Simplified_vector
{
public:
    using interator = T*;
    using const_interator = const T*;

private:
   T* buffer_;
   std::size_t size_;
   std::size_t capacity_;

public:

   auto push_back(const T& val) -> void
   {
       if (size_ + 1 > capacity_)
       {
           // buffer increase logic
           //
           // this usually means allocation a new larger buffer
           // followed by coping/moving elements from the old to the new buffer
           // deleting the old buffer
           // and make `buffer_` point to the new buffer
           // (along with modifying `capacity_` to reflect the new buffer size)
           //
           // strong exception guarantee makes things a bit more complicated,
           // but this is the gist of it
       }

       buffer_[size_] = val;
       ++size_;
   }

   auto begin() const -> const_iterator
   {
       return buffer_;
   }

   auto begin() -> iterator
   {
       return buffer_;
   }

   auto end() const -> const_iterator
   {
       return buffer_ + size_;
   }

   auto end() -> iterator
   {
       return  buffer_ + size_;
   }
};

Also see this question Can std::vector<T>::iterator simply be T*? for why T* is a perfectly valid iterator for std::vector<T>

Now with this implementation in mind let's answer a few of your ~~misconceptions~~ questions:

I was trying to point the vector.end() to the N+1'th position.

This is not possible. The end iterator is not something that is stored directly in the class. As you can see it's a computation of the begging of the buffer plus the size (number of elements) of the container. Moreover you cannot directly manipulate it. The internal workings of the class make sure end() will return an iterator pointing to 1 past the last element in the buffer. You cannot change this. What you can do is insert/remove elements from the container and the end() will reflect these new changes, but you cannot manipulate it directly.

and I believe (correct me if i'm wrong) this would be an example of a
memory leak.

you are wrong. Even if you somehow make end point to something else that what is supposed to point, that wouldn't be a memory leak. A memory leak would be if you would lost any reference to the dynamically allocated internal buffer.

Arithmetic on invalidated iterators

Is behavior of std::distance undefined when called on a pair of std::vector iterators that have been invalidated by moving the vector?

If the iterators are valid before the move, they will remain valid after the move - so you don't need to recalculate them using std::distance.

(emphasis mine below)

std::vector::vector

After container move construction, references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this.

The current standard makes this guarantee via the blanket statement in [container.requirements.general/12], and a more direct guarantee is under consideration via LWG 2321.

[container.requirements.general/12] states that

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

The same blanket statement goes for the move assignment operator and this means that, in accordance with the standard, the iterators will stay valid after the move.

The current wording in LWG 2321 gives a hint of what a new paragraph in the standard could look like if the library working group finalize this - which seems to be hard. LWG 2321 was opened back in 2013.

no move constructor (or move assignment operator when allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true) of a container (except for array) invalidates any references, pointers, or iterators referring to the elements of the source container. [Note: The end() iterator does not refer to any element, so it may be invalidated. — end note]

If that's too vague, you can use

[container.requirements.general/11.6]

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. — end note ]

If the iterators are valid before you swap, they are valid after the swap.

Here's an example class using the guarantee given for swap:

#include <vector>

class Foo {
    std::vector<int> data{};
    std::vector<decltype(data)::iterator> dits{};

public:
    Foo() = default;

    Foo(const Foo&) = delete;    // here, dits would need to be calculated

    // A move constructor guaranteed to preserve iterator validity.
    Foo(Foo&& rhs) noexcept {
        data.swap(rhs.data);
        dits.swap(rhs.dits);
    }

    Foo& operator=(const Foo&) = delete;

    // A move assignment operator guaranteed to preserve iterator validity.
    Foo& operator=(Foo&& rhs) noexcept {
        data.swap(rhs.data);
        dits.swap(rhs.dits);
        return *this;
    }

    ~Foo() = default;
};

Am I guaranteed that pointers to std::vector elements are valid after the vector is moved?

This is LWG open issue 2321 [emphasis mine]

Moving containers should (usually) be required to preserve iterators

[...]

[by Stephan T. Lavavej]

23.2.1 [container.requirements.general]/10 says that unless otherwise specified, "no swap() function invalidates any references, pointers,
or iterators referring to the elements of the containers being
swapped. [Note: The end() iterator does not refer to any element, so
it may be invalidated. — end note]". However, move constructors and
move assignment operators aren't given similar invalidation
guarantees. The guarantees need several exceptions, so I do not
believe that blanket language like /11 "Unless otherwise specified
(either explicitly or by defining a function in terms of other
functions), invoking a container member function or passing a
container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container."
is applicable.

[2014-02-13 Issaquah]

General agreeement on intent, several wording nits and additional paragraphs to hit.

STL to provide updated wording. Move to Open.

Proposed resolution:

[...]

no move constructor [...] of a container (except for array) invalidates any references, pointers, or iterators referring to the elements of the source container. [Note: The end() iterator does not refer to any element, so it may be invalidated. — end note]

So, this is an open issue, with general agreement on its basic solution (pointer shall not be invalidated by moving). However, it isn't officially accepted (yet?) as a defect. As far as I know, all major implementations do not invalidate pointers when move-constructing, and it seems to be a generally (implicitly) provided guarantee.

c++ is there any possibility that `map.end()` can change during the life time of a `std::map`

std::map::insert guarantees:

No iterators or references are invalidated.

std::map::erase guarantees:

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Therefore the end iterator should stay valid. If you use any other operation, you should check whether it might invalidate the iterators.

Do Stl Iterators Guarantee Validity After Collection Was Changed