What Is the Past-The-End Iterator in Stl C++

What is the past-the-end iterator in STL C++?

The functions begin() and end() define a half open range([begin, end)), which means:

The range includes first element but excludes the last element. Hence, the name past the end.

The advantage of an half open range is:

1. It avoids special handling for empty ranges. For empty ranges, begin() is equal to
   end() .

2. It makes the end criterion simple for loops that iterate over the elements: The loops simply
   continue as long as end() is not reached

In what way does end() point to 'one past the end' in non-contiguous containers?

What is one past the end supposed to mean for non-contiguous storage?

It means whatever you'd get if you incremented an iterator to the last element.

How does nullptr fit the definition of 'one past the end'?

If that's what you get if you increment an iterator to the last element, then it fits the definition.

How is MyForwardList.begin() == MyForwardList.end() true if MyForwardList is empty?

For an empty list, they both return the same thing. Likely an "empty" iterator.

Why isn't end() always defined as nullptr?

Because sometimes that's not the most convenient way to define it, and so long as you meet the requirements, you can implement it however you want.

It's basically just a circular definition. The end function returns whatever you'd get if you took an iterator to the last element in the list and incremented it or, for an empty list, returns the same thing begin returns. So long as all these relationships hold, everything works, regardless of what internal values or logic you use to guarantee the relationships.

Iterator to one past the last element in list

How can it be known at which positions (in memory) the next elements will be stored?

It is not. Also, using that memory address as (part of) the past-the-end iterator would be incorrect.

Is not:
An iterator is not (necessarily) a pointer. An iterator is not required to store a memory address. What is required is that the de-reference operator be able to calculate a memory address (returned in the form of a reference). Good news, everyone! Applying the de-reference operator to the past-the-end iterator is undefined behavior. So even this reduced requirement is not applicable to the past-the-end iterator. If you are storing an address, go ahead and store whatever you want. (Just be consistent since two past-the-end iterators must compare equal.)

If your iterator does store a pointer (which admittedly is probably common), a simple approach would be to store whatever you would put in the next field of the last node in the list. This is typically either nullptr or a pointer to the list's sentinel node.

Would be incorrect:
A std::list does not invalidate iterators when elements are added to the list. This includes the past-the-end iterator. (See cppreference.com.) If your past-the-end iterator pointed to where the next element would be stored, it would be invalidated by adding that element to the list. Thus, you would fail to meet the iterator invalidation requirements for a std::list. So not only is storing that address in the past-the-end iterator impossible, it's not allowed.

What happens if you increment an iterator that is equal to the end iterator of an STL container

Following is the quote from Nicolai Josuttis book:

Note that advance() does not check
whether it crosses the end() of a
sequence (it can't check because
iterators in general do not know the
containers on which they operate).
Thus, calling this function might
result in undefined behavior because
calling operator ++ for the end of a
sequence is not defined

In other words, the responsibility of maintaining the iterator within the range lies totally with the caller.

Past-the-end iterator invalidation in C++11

My question is about all containers:

• In C++11, are there any container operations that may invalidate a past-the-end iterator, and where this behavior is ambiguous in the
  language specification?

I am not sure what you mean with "where this behavior is ambiguous in the language specification", but there certainly are operations that invalidate past-the-end operators (like insert into a std::vector or std::string).

Said differently,

• Can I trust the validity of a past-the-end iterator after performing a container operation that does not say it may invalidate
  the past-the-end iterators?

You can trust the past-the-end iterator like any other iterator: Any operation that does not (potentially) invalidate iterators won't invalidate them. Except for the possibility of the standard sporting a bug, that is all operations where it doesn't say that they (potentially) invalidate operators.

---

Related Topics