How does end () point to "one end" in non-contiguous containers?
According to the answers in this and this question, the C ++ standard says in § 23.2.1 that end()
has constant time complexity for all stl containers.
If I understand correctly:
-
std::forward_list
only knows about that first item, and each of the list entries only knows about the next item. - the lists are not contiguous in memory
-
a.begin() == a.end()
true for empty containersa
-
end()
must be an iterator pointing to "one past the end of the container"
So while working on some loops on forward_list
s I was wondering:
How can end () have constant time complexity (ie not go to "one per end") in the case of a redirect?
I looked forward_list.cpp
and found an ad
iterator end() _NOEXCEPT
{return iterator(nullptr);}
This makes sense for the constant time requirement, but not for the rule — the general rule of vage, which corresponds to point 4 above.
So, some questions remain:
- What does "one end" mean for non-contiguous storage?
- How does the
nullptr
definition of "one by the end" fit? - Is it
MyForwardList.begin() == MyForwardList.end()
true ifMyForwardList
empty? - Why is it not
end()
always defined hownullptr
?
source to share
What does it mean
one past the end
for non-contiguous storage?
This means what you get if you incremented the iterator to the last element.
How does the
nullptr
definition of "one by the end" fit?
If that's what you get, if you increment the iterator to the last element, then it matches the definition.
How
MyForwardList.begin() == MyForwardList.end()
true if MyForwardList is empty?
For an empty list, they both return the same thing. Probably an "empty" iterator.
Why is it not
end()
always defined hownullptr
?
Because sometimes it's not the most convenient way to define it, and as long as you meet the requirements, you can implement it however you want.
It's basically just a circular definition. The function end
returns whatever you got if you took the iterator to the last item in the list and incremented it, or, for an empty list, returned the same as begin
. As long as all of these relationships persist, everything works no matter what intrinsic values or logic you use to guarantee the relationship.
source to share
"One end" is defined in terms of iterator traversal, not memory locations. An iterator end
is what you get when you take an iterator to the last element and increment it (or begin
an empty container).
std::forward_list
The end iterator pointing to nullptr
makes sense: in the implementation, the last node probably has the nullptr
next node, and after that link does indeed give an iterator end
. std::vector
end
can physically indicate storage location for the same reason.
source to share
end()
must be an iterator pointing to "one past the end of the container".
This is subtly different from what the standard says (emphasis mine):
begin()
returns an iterator referring to the first item in the container.end()
returns an iterator that is the last-end-end value for the container. If the container is empty, thenbegin() == end()
;
The standard says "past", not "one end".
Developers are free to choose which pass-through implementation works for a particular container type.
source to share
What does "one end" mean, which is supposed to mean for non-contiguous storage?
Just the node that the last valid node points to.
How does the
nullptr
definition of "one by the end" fit?
Ok, when you build a data structure based on a node, the last valid node will point to nullptr
for the next node, that is, as you know it at the end.
How
MyForwardList.begin() == MyForwardList.end()
true
if it'sMyForwardList
empty?
In an empty list, head nullptr
or head points to nullptr
, so the comparison nullptr
is nullptr
- true
.
Why isn't it
end()
always defined as nullptr?
Because there is no need to use your pointers.
source to share