STL如何订购容器知道他们的结局？

Question

我知道标准没有规定必须实现STL容器的方式,而是规定了每个容器的一组要求.

然而,众所周知,STL有序容器通常被实现为红黑树.

您可以使用各自的迭代器迭代a std::set或a 的元素std::map,或者使用ranged循环来迭代C++ 11.

然而令我困惑的是,STL中一个有序的容器如何"知道"它的"结束".或者换句话说,因为它们是作为树实现的,如何实现容器的结束还是可以实现？

我知道标准规定§23.2.1/ c一般容器要求(强调矿井):

begin()返回一个引用容器中第一个元素的迭代器.end()返回一个迭代器,它是容器的past-the-end值.如果容器为空,则begin()== end();

好吧,对于连续的容器来说这很容易,但这种"过去的结果"如何实现树木？

Answer 1

我刚刚map在Visual Studio 2013 STL中检查了容器的实现,这里是如何end实现的.在map构造时,分配RB树的头元素,并将该元素声明为容器的末尾.

当您通过一个有效的迭代器遍历容器,operator++并operator--直接跳过头元素.当你到达树的最后一个元素并增加一个迭代器时,它向上爬(寻找一个正确的子树)并最终到达树的头部,即end.

Answer 2

所有像这样的“类似列表”的容器都需要有某种类型的哨兵节点作为结尾，因为用户可以获取end()、向容器中插入一些东西、递减迭代器，并且递减的end()必须指向该插入的元素。我的理解是，有些实现会为此动态分配，有些实现会将动态哨兵节点放在容器本身内部。