c++ - 标准模板库列表 - 双向链接还是循环链接？

Question

我刚刚注意到 C++ 中的 std::list 类，我觉得很好奇。简而言之，它涉及列表迭代器的工作方式。考虑以下代码:

std::list<int> alist;
alist.push_back(0);
alist.push_back(1);
alist.push_back(2);

很明显，这会创建一个包含三个整数元素的列表。我可以在列表的开头定义一个迭代器，并使用它来打印出第一个元素中包含的值，如下所示:

std::list<int>::iterator iter = alist.begin();
std::cout << *iter << std::endl;  // Prints "0" to stdout

我觉得有点奇怪的是，如果我现在递减迭代器，它会“循环”并最终指向列表中的最后一个元素:

--iter;
std::cout << *iter << std::endl;  // Prints "2" to stdout

对于应该作为双向链表实现的事物，这种行为是否合理？如果列表是循环 链表，我非常希望迭代器有类似的行为，但我觉得这很奇怪。

您过去使用过的迭代器行为是否有任何实际用途？是否有任何我应该注意的与此行为相关的陷阱？

(顺便说一句，这发生在 gcc 4.7.0 (MinGW) 上。我还没有用任何其他版本或编译器测试过它。)

Answer 1

在 begin 之后递减迭代器会调用未定义的行为。您看到的行为很可能是巧合(实际上，看看不同的编译器会发生什么 here)。

如果你想证实这一点，你可以简单地看一下GCC的list的实现；您通常可以在 /usr/include/c++/4.x.y/bits/STL_list.h 找到源代码。