在不连续的容器中end()以什么方式指向'一个接一个'？

Question

根据这个和这个问题的答案,C++标准在第23.2.1节中规定end()了所有stl容器的时间复杂度.

如果我理解正确:

因此,当forward_list我在s 上进行一些循环时,我想知道:

在forward_list的情况下,end()如何具有恒定的时间复杂度(即不会提前到'结束一个')？

我看了看forward_list.cpp并发现了声明

iterator       end() _NOEXCEPT
    {return       iterator(nullptr);}

这对于恒定时间要求是有意义的,但不适用于与上述第4点相对应的 - 公认的规则 - 规则.

所以仍有一些问题:

Answer 1

one past the end对于非连续存储应该是什么意思？

这意味着如果将迭代器增加到最后一个元素,您将获得什么.

如何nullptr符合"一个接一个"的定义？

如果你将迭代器增加到最后一个元素,那就是你得到的,那么它符合定义.

如何为MyForwardList.begin() == MyForwardList.end()真,如果MyForwardList是空的？

对于一个空列表,它们都返回相同的内容.可能是一个"空"的迭代器.

为什么不end()总是被定义为nullptr？

因为有时这不是定义它的最方便的方法,只要你满足要求,你就可以随意实现它.

它基本上只是一个循环定义.end如果你将迭代器带到列表中的最后一个元素并递增它,或者对于一个空列表返回相同的东西begin返回,该函数将返回你得到的任何内容.只要所有这些关系成立,一切都有效,无论您使用什么内部价值观或逻辑来保证关系.

Answer 2

"一个接一个结束"是根据迭代器遍历而不是内存位置来定义的.一个end迭代器是当你把一个迭代的最后一个元素,并增加它(或你所得到的begin空容器).

std::forward_list指向的结束迭代器nullptr是有意义的:在实现中,最后一个节点可能有一个nullptr下一个节点,并且在该链接之后确实产生了end迭代器.std::vector的end可能物理指向过去存储出于同样的原因.

Answer 3

end() 应该是一个指向'一个超过容器末尾'的迭代器.

这与标准所说的略有不同(强调我的):

begin()返回一个迭代器,引用容器中的第一个元素.end()返回一个迭代器,它是容器的过去值.如果容器是空的,那么begin() == end();

标准说"过去的结束",而不是"一个接一个的结束".

实现者可以自由选择特定容器类型的"过去 - 结束"工作的任何实现.