C++标准库容器尾后迭代器支持operator--()的实现原理

我在实现自定义的list和map容器时，遇到了end()方法的实现难题。一开始我参考思路把end()实现为持有nullptr的迭代器，这能满足大部分场景（比如空列表时begin() == end()，因为空列表没有节点，head指向nullptr）。但我发现标准库中可以对尾后迭代器调用operator--()，使其指向容器最后一个元素，示例代码如下：

int main() {
  {
    std::map<int, char> m = {{1, 'a'}, {2, 'b'}, {3, 'c'}};
    auto it = m.end();
    --it;
    std::cout << it->first << "\n";  // output: 3
    std::cout << it->second << "\n"; // output: c
  }
  {
    std::list<int> l{ 1, 2, 8};
    auto it = l.end();
    --it;
    std::cout << *it << "\n"; // output: 8
  }
}

这是如何实现的？我看到GCC中_List_iterator的operator--()实现是直接让当前节点指向前一个节点：

_Self&
operator--() _GLIBCXX_NOEXCEPT
{
  _M_node = _M_node->_M_prev;
  return *this;
}

但如果尾后迭代器指向的节点不在列表中，这怎么可能做到？这个节点是怎么存在的？是不是意味着容器分配了额外的节点？另外，标准是否允许对尾后迭代器调用operator--()？

附上GCC中std::list的begin()和end()实现供参考：

/**
 *  Returns a read-only (constant) iterator that points to the
 *  first element in the %list.  Iteration is done in ordinary
 *  element order.
 */
_GLIBCXX_NODISCARD
const_iterator
begin() const _GLIBCXX_NOEXCEPT
{ return const_iterator(this->_M_impl._M_node._M_next); }

/**
 *  Returns a read/write iterator that points one past the last
 *  element in the %list.  Iteration is done in ordinary
 *  element order.
 */
_GLIBCXX_NODISCARD
iterator
end() _GLIBCXX_NOEXCEPT
{ return iterator(&this->_M_impl._M_node); }

解答 #

1. 标准是否允许对尾后迭代器调用operator--() #

根据C++标准，只要容器非空，就允许对尾后迭代器调用前置或后置的operator--()。这是双向迭代器（list、map的迭代器都属于双向迭代器）的核心要求之一，确保迭代器能在有效范围内反向移动。

2. GCC的实现原理：环形哨兵节点 #

GCC中的std::list采用环形哨兵节点的设计方案，这是实现上述特性的关键：

• 容器内部会分配一个额外的空节点（哨兵节点），它不属于容器的有效元素，但作为链表的固定组成部分存在。
• 非空list中，最后一个元素的_M_next指向哨兵节点；哨兵节点的_M_prev则指向容器的最后一个有效元素。
• 空list时，哨兵节点的_M_next和_M_prev都指向自身，此时begin()返回的是哨兵节点的_M_next（即自身），end()返回指向哨兵节点的迭代器，因此begin() == end()的条件成立。

结合你提供的GCC代码可以验证：

• begin()返回的是_M_impl._M_node._M_next，也就是哨兵节点的下一个节点（非空时为第一个有效元素，空时为哨兵自身）。
• end()直接返回指向哨兵节点的迭代器。

因此，对end()迭代器调用operator--()时，迭代器指向的哨兵节点的_M_prev正是容器的最后一个有效元素，这就实现了从尾后迭代器反向移动到最后一个元素的操作。

3. 自定义容器的改进方向 #

如果你的自定义容器用nullptr作为尾后迭代器的目标，调用operator--()会触发空指针访问的未定义行为，无法实现标准库的特性。要对齐标准行为，你需要给容器添加一个哨兵节点，让尾后迭代器指向它，并维护好哨兵节点与首尾元素的双向链接关系。

内容的提问来源于stack exchange，提问作者edugomez102