是否有一个标准容器允许插入元素而不使迭代器无效？

Question

在 C++ 中，是否有一种数据结构允许我在以下 for 循环中向其中添加元素？

（我使用 list 作为示例，因为这是我迄今为止尝试过的。）

list<Elem> elems;
// fill elems with some Elems;

for(list<Elem>::iterator it=elems.begin(); it!=elems.end();) {

    // ...

    if(condition)
        it = elems.erase(it);
    else {
        Elem elem;
        it = elems.push_back(elem);
    }
}

PS：这是 从向量中删除元素

Answer 1

StackOverflow 上的这个答案很好地总结了所有标准容器的行为。

不会在插入或删除时使迭代器失效的容器有 list、set、multiset、map、和多重映射。当然这不包括迭代器被擦除。

Answer 2

是的， list 允许您执行此操作..正如我在其他答案的评论中所说的那样......

Answer 3

根据请求编写此内容。

PS：这是从向量中删除元素的后续问题

这是您的提问中的一个令人不安的模式。

说真的，在迭代容器时修改容器是很糟糕的。很难做到正确。它通常不会在性能方面为您节省太多。它很少（除非在有限的情况下有一个完全适合您的需求的标准库算法）更容易表达。如果做错了，性能成本可能会非常高。如果你做错了，程序的正确性可能会付出非常高昂的代价，而这一点比其他任何事情都重要得多。

如果涉及线程，情况会变得更加糟糕。 Java 有一个专用的异常类型，专门针对某些在尝试执行此操作时可能出错的事情。在 C++ 中你就没那么幸运了；类似的问题可能无法检测到。

只需编写产生最终结果的代码，然后替换原始容器即可。唯一真正能减慢速度的事情是“复制实例的成本很高”，在这种情况下，无论如何，您应该已经使用间接层来处理问题（假设它确实很重要）。

list<Elem> original;
// fill elems with some Elems;
list<Elem> modified;
for (
    list<Elem>::iterator it = original.begin(), end = original.end();
    it != end; ++it
) {
    if (something()) {
        modified.push_back(*it);
    } else if (something_else()) {
        modified.push_back(Elem()); // for example
    }
    // else, 'erase' the element by just not putting anything into 'modified'
    // Or we could do whatever other combination of things,
    // maybe insert more than one
}
std::swap(original, modified);

Answer 4

有几个容器支持插入而不使迭代器无效。在您的代码中，您的删除情况是正确的，但我相信您过度考虑了插入情况。试试这个：

else {
    Elem elem;
    elems.push_back(elems);
    ++it;
}

您在给定的示例中使用了 list，因此您知道 push_back 调用不会使它失效。因此，您可以简单地增加它以到达下一个元素。您只需在删除元素时小心，因为您无法增加指向不再存在的位置的迭代器。