为什么 std::list 迭代器没有 operator+？

Question

我正要写这样的代码：

std::list<whatevertype> mylist;

// ...

std::list<whatevertype>::iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it) {
    // ...
    if(some condition)
        mylist.erase(it);
}

但我意识到，这段代码是错误的：mylist.erase(x)会使迭代器it无效，所以++it很可能会失败。

所以我尝试将其更改为

std::list<whatevertype>::iterator it;
std::list<whatevertype>::iterator nextit;

for(it = mylist.begin(); it != mylist.end(); it = nextit) {
    // ...
    nextit = it + 1;
    if(some condition)
        mylist.erase(it);
}

但是，令我惊讶的是，这失败了：显然 operator+ 没有为 std::list 迭代器定义。

我后来发现 this other question 并了解到删除 "out from under" 迭代器的标准用法更像是

for(it = mylist.begin(); it != mylist.end(); ) {
    if(some condition)
          it = mylist.erase(it);
    else  ++it;
}

我相信我也可以逃脱

for(it = mylist.begin(); it != mylist.end(); ) {
    // ...
    std::list<whatevertype>::iterator previt = it;
    ++it;

    if(some condition)
        mylist.erase(previt);
}

但我的问题是，有没有为这些迭代器定义 operator+ 的原因？

Answer 1

他们对 std 迭代器和集合的一个规则是让昂贵的东西变得冗长。

在列表迭代器上，it+50 需要 O(50) 时间。在向量迭代器上，it+50 需要 O(1) 时间。因此，他们在向量迭代器（和其他随机访问迭代器）上实现了 +，但在列表迭代器（和其他较弱的迭代器）上实现了。

std::next和std::advance和std::prev更容易解决你的问题：

auto previt = std::prev(it);

或

auto nextit = std::next(it);

这些也需要计数，但因为它们是显式函数调用，所以决定它们昂贵是可以接受的。

除其他外，您可以搜索以查找对std::next 和std::prev 的调用并获取迭代器操作； + 严重超载，很难找到昂贵的调用。

请注意，std::basic_string 不遵循与其他 std 容器相同的约定。

Answer 2

并不是所有迭代器都缺少 +。 std::list 个迭代器缺少它。

那是因为列表迭代器在随机访问时效率极低。因此，让随机访问变得容易不是一个好主意。

您可以使用 std::advance。它使您在列表中一次移动一个元素变得更加明显。

Answer 3

std::list 使用仅定义递增和递减的双向迭代器。由于std::list是一个链表迭代器的实现一次只能移动一个节点。

该界面旨在确保您知道移动多个元素并不像其他迭代器那样简单，例如从 std::vector.

返回的 RandomAccessIterator

有关不同迭代器类型的定义，请参阅 http://en.cppreference.com/w/cpp/concept/Iterator。

为什么 std::list 迭代器没有 operator+？

Why no operator+ for std::list iterators?

c++

iterator

erase