c++ - end() 以何种方式指向非连续容器中的 'one past the end'？

Question

根据this中的回答和 this问题，C++ 标准在 § 23.2.1 中声明 end() 对于所有 STL 容器都具有恒定的时间复杂度。

如果我理解正确的话:

1. std::forward_list 只知道它的第一个元素，每个列表条目只知道下一个元素。
2. 列表在内存中是不连续的
3. a.begin() == a.end() 对于空容器 a
为真
4. end() 应该是一个指向“容器末尾的一个”的迭代器

因此，在对 forward_list 进行一些循环时，我想知道:

在 forward_list 的情况下，end() 如何具有恒定的时间复杂度(即不前进到“结束后的一个”)？

我查看了 forward_list.cpp 并找到了声明

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

这对于恒定时间要求是有意义的，但对于对应于上面第 4 点的 - 无可否认的 vage - 规则则不是。

所以还有一些问题:

• 对于非连续存储，“最后一次”应该意味着什么？
• nullptr 如何符合“最后一个”的定义？
• 如果 MyForwardList 为空，MyForwardList.begin() == MyForwardList.end() 如何为真？
• 为什么 end() 不总是定义为 nullptr？

Answer 1

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

这意味着如果你将迭代器递增到最后一个元素，你会得到什么。

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

如果这是将迭代器递增到最后一个元素时得到的结果，那么它符合定义。

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

对于一个空列表，它们都返回同样的东西。可能是一个“空”迭代器。

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

因为有时候这并不是最方便的定义方式，只要你满足要求，你想怎么实现就怎么实现。

这基本上只是一个循环定义。 end 函数返回您将迭代器带到列表中的最后一个元素并将其递增时得到的任何内容，或者对于空列表，返回相同的内容 begin返回。只要所有这些关系都存在，一切都会正常进行，无论您使用什么内部值(value)观或逻辑来保证这些关系。