STL中遍历erase()与clear()效率问题
发布网友
发布时间：2022-11-23 02:58
共1个回答
热心网友
时间：2023-12-30 15:32
看似一个简单的动作，然而对不同类型的容器，内部却做了截然不同的事情，后面介绍。
假设有这样一个题目，将某个容器中所有满足条件N == X的元素删除，按照常规的思路应该有类似这样的代码：
// 假设Container和container分别表示一种容器和对应的一个对象
Container<T>::iterator it;
for (it = container.begin(); it != container.end(); ++it) {
if (N == X)
container.erase(it);
}
然而这样的代码对于任一种容器都是错误的
容器按内存分配方式可以分为链表容器和数组容器。
所谓的链表容器指的是一种表现方式，包括list、slist等这样基于节点的容器（动态分配内存块）和set、map、multiset、multimap等关联容器（平衡树实现），而数组容器指的是在一块连续的内存上保存元素的连续内存容器，比如vector、deque、string等。
链表容器以list为例，当执行container.erase(it)时，确实第一个满足条件的元
