Question

Is a back_insert_iterator valid for the lifetime of the container?

I think I know the answer to this, but I'd appreciate a sanity check.

Does iterator invalidation apply to std::back_insert_iterators?

#include <cassert>
#include <iterator>
#include <vector>

int main() {
    auto v = std::vector<int>{ 0, 1, 2 };
    auto iter = std::back_inserter(v);
    *iter++ = 3;
    v.clear();    // invalidates iterators, but
    *iter++ = 4;  //  back_insert_iterator is special?
    assert(v.size() == 1 && v[0] == 4);
    return 0;
}

This code works for me because the std::back_insert_iterator implementation from my vendor doesn't hold an iterator (or pointer or reference). It simply calls the container's push_back method.

But does the standard require that implementation? Could another vendor's back_insert_iterator hold and maintain a one-past-the-end iterator to use with a call to the container's insert method? It seems that would meet the requirements. This difference, of course, is that it would be vulnerable to invalidation.


I know cppreference.com is not authoritative, but it's more accessible than the standard.

[A vector's clear method] [i]nvalidates any ... iterators referring to contained elements. Any past-the-end iterators are also invalidated. [cppreference.com, emphasis added]

A std::back_insert_iterator could be the poster child of a past-the-end iterator.

 4  63  4
1 Jan 1970

Solution

 1

Per [back.insert.iterator]

namespace std {
  template<class Container>
  class back_insert_iterator {
  protected:
    Container* container;

  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

    constexpr explicit back_insert_iterator(Container& x);
    constexpr back_insert_iterator& operator=(const typename Container::value_type& value);
    constexpr back_insert_iterator& operator=(typename Container::value_type&& value);

    constexpr back_insert_iterator& operator*();
    constexpr back_insert_iterator& operator++();
    constexpr back_insert_iterator  operator++(int);
  };
}

constexpr explicit back_insert_iterator(Container& x);

1 Effects: Initializes container with addressof(x).

constexpr back_insert_iterator& operator=(const typename Container::value_type& value);

2 Effects: As if by: container->push_back(value);

3 Returns: *this.

constexpr back_insert_iterator& operator=(typename Container::value_type&& value);

4 Effects: As if by: container->push_back(std​::​move(value));

5 Returns: *this.

[...]

As we can see the iterator gets a pointer to the container and then push_back is called directly on the container, so no chance of UB.

2024-07-06
NathanOliver