有一段时间, 我对 STL 的容器有一些疑惑, 那便是如何快速将地将给定的元素从容器中删除. 例如 std::list 是链表, 本应支持快速的 O(1) 的删除操作, 但给定的 remove() 方法是 O(n) 成本的. 后来, 我才明白, C++ STL 的迭代器(iterator)不仅仅用来遍历容器, 它们的另一作用便是实现那些不是很直观的操作.
先举一个 C 语言链表的例子, 节点的结构体一般这样定义:
struct Node{ struct Node *prev, *next; Item item; };
链表的数据结构即节点的数据结构. 删除节点的操作非常直接:
void list_del(struct Node *node){ // 不做头尾结点特殊处理 struct Node *next = node->next; node->next->prev = node->prev; node->prev->next = next; }
但是, 使用 C++ STL 的链表(list)时, 一般只关注数据本身, 不会关于链表指针, 所以 C++ 就不会定义一个节点结构体, 而是这样使用:
std::list<Item *> items;
那么, 这样的代码是无法快速地删除指定的 Data 的, 因为对于 Data 的使用者, 它是无法知道自己所处的节点是什么.
其实, C++ STL 的容器类可不是这样使用的, 正确的使用方法其实和 C 语言的版本差不多, 还是需要对 Data 进行封装, 记录每个 Data 对应其所处链表的节点的指针:
class Node{ public: std::list<Node *>::iterator ref; Item item; };
Node 类里有一个成员 ref, 它指向自己所处的链表的节点. 这样, 从 STL 链表中删除一个节点时, 就可以使用 O(1) 的方法:
std::list<Node *> items; Node *node = new Node(); node->ref = items.insert(items.end(), node); // O(1) items.erase(node->ref); // O(n) // items.remove(node);
不过, 你可能会有一个怀疑, 在 insert() 时返回的 iterator, 它会不会在后续的操作中失效, 因为 iterator 的失效是一个非常重要的问题, 如果 iterator 失效了你再调用 items.erase(node->ref);
, 就会出现内存非法操作异常.
没错, STL 不同容器的 iterator 有不同的失效原则, 但可以肯定, std::list 的 iterator 不会因为添加或者删除元素而失效. STL 容器的 iterator 的失效原则(部分)可见下表:
容器类 | 插入 | 删除 |
---|---|---|
list | 所有迭代器不失效 | 有且仅有被删除的节点的迭代器才失效 |
vector | 当 vector 的容量(不是size)不改变时, 只失效之后的迭代器, 否则全部失效 | 被删除节点之后的迭代器全部失效 |
set, map | 所有迭代器不失效 | 有且仅有被删除的节点的迭代器才失效 |
来源: stackoverflow