2014-03-14

C++ STL 迭代器的失效原则

Views: 12480 | Add Comments

有一段时间, 我对 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

Related posts:

  1. 百行代码实现一个简单的Zset(SortedSet)
  2. 概率选取的实现
  3. C# 版的 SimpleXML
  4. Redis 的作者狂喷某 NoSQL 数据库
  5. 基于列的数据库
Posted by ideawu at 2014-03-14 09:50:51

Leave a Comment