Is it legal to return reference to an InputIterator internal state?

user_1282773 0
Viewed 102

Let we have an input iterator it that conforms Cpp17InputIterator. Can we guarantee that the reference value *it remains the same after we do it++? For example,

const auto &old_ref = *it;
auto old_val = ref;
++it; // old_ref might be affected by this

assert(old_ref == old_val); // Is this guaranteed for Cpp17InputIterator?

This table says that the old copies of it are not required to be dereferenceable. But does this imply that old references obtained from it may not be dereferenceable too? Can *it return a reference to the iterator's internal state?

c++17 language-lawyer stl c++
1 Answers

It should never be assumed that a reference remains valid if an iterator is invalidated. This may be the case with some iterator implementations, but doing so is a violation of the iterator concept, and will not work generically with all iterators.

It's entirely legal for an iterator to be implemented internally as a std::optional<T> that may return a reference of T and reconstructs T between each iteration. This is especially true on Inputiterators, which don't require multipass support (such as for a generator range).

For example, an iterator doing the following is completely legal:

template <typename T>
auto some_special_iterator<T>::operator*() -> T&
{
  return *m_value; // returns a reference to the currently stored T
}

template <typename T>
auto some_special_iterator<T>::operator++() -> some_special_iterator&
{
  m_value.clear(); // Destroys the object which someone may be holding a reference to
  m_value.emplace( ... ); // Invalidates any existing references by constructing a new object

  return (*this);
}

Using a pointer or reference to an object that has been destroyed is undefined behavior, even if that pointer or reference points to the same storage of a new object. The only legal pointers or references to a newly constructed object are the ones returned by new (such as placement new) or std::launder.

Since this is tagged language-lawyer: There isn't really much in the line of quotes directly from the standard that can define this to be illegal, since there are no guarantees from the InputIterator concept that allow a preserved reference to remain valid.

So to prove this is undefined behavior, we need to work backwards. First off:

From defns.undefined

Undefined behavior may be expected when this International Standard omits any explicit definition of behavior or when a program uses an erroneous construct or erroneous data

So we need to check that the iterator example above adheres correctly to InputIterator's concept definition, of which the important part is the operator++ behavior:

From the table in input.iterators:

Requires: r is dereferenceable.
Postconditions: r is dereferenceable or r is past-the-end; any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==.

(emphasis mine)

In the above requirements, the condition that an iterator r is dereferencable before is upheld in the above example, just as the postcondition would be upheld as well.

What's interesting is the part that I bolded: "any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of =="

This means that any existing copies of the iterator itself may no longer be dereferenceable and nor may it properly perform a comparison in the same range as another iterator. This is the part that formally means that all copies of the iterator may have been invalidated (note: "may", since an iterator need not be invalidated -- but should be assumed to have).

The C++ Standard's document does not explicitly state that any held references are still valid, because this is not defined behavior of the process; however if the iterator itself is no longer considered "dereferencable" after an invocation of operator++, then it should also be assumed that its reference is no longer valid. Since the wording does not state that holding a reference after this point is guaranteed to remain valid, it must be assumed to be undefined behavior due to the passage above from defns.undefined.

The example illustrated above is a conforming iterator implementation where such an expectation would cause actual undefined behavior, which fits this interpretation.

On a different note, be careful using const auto& with input iterators.

operator*() on input iterators only needs to return an It::reference type which is convertible to T; it does not actually need to be a reference at all. Be aware that this is strengthened in forward iterators and beyond that "reference must be a reference to T", but this isn't true of input iterators.

Using const auto& here may actually cause you to unintentionally const-lifetime-extend a temporary proxy object rather than holding a real reference.

user_16787700
Related