c++ - 当数据结构是模板参数时，如何判断操作是否会使迭代器无效？

Question

具体来说，我有一个当前使用 vector 和 push_back 的类。我要跟踪的 vector 中有一个元素。推回 vector 可能会使迭代器无效，所以我保留它的索引。使用索引再次找到迭代器很便宜。我无法保留 vector ，因为我不知道要插入多少项。

我考虑过将数据结构作为模板参数，也许可以使用列表来代替。在这种情况下，从索引中找到一个迭代器并不是一个简单的操作。由于推回列表不会使现有元素的迭代器无效，因此我可以只存储此迭代器。

但是我怎样才能编写一个可以轻松处理这两种情况的泛型类呢？

如果我能确定 push_back 是否会使迭代器失效，我可以存储迭代器并在每次 push_back 之后通过存储操作前从开始的距离来更新它。

Answer 1

您应该尽量避免这种灵 active 。引用来自 Effective STL 的第 2 项“小心容器独立代码的错觉”斯科特迈耶斯:

Face the truth: it's not worth it. The different containers are different, and they have strengths and weaknesses that vary in significant ways. They're not designed to be interchangeable, and there's littel you can do to paper that over. If you try, you're merely tempting fate, and fate doesn't like to be tempted.

如果您确实必须维护有效的迭代器，请使用 std::list。如果您还需要随机访问，请尝试 Boost.MultiIndex (虽然你会失去连续的内存访问)。

如果您查看标准容器适配器(std::stack、std::queue)，您会发现它们支持 intersection的自适应容器接口(interface)，而不是它们的 union。