链表迷魂阵

只要粗粗看过数据结构,对链表的印象一定是插入、删除操作都很快。不过对 C++ 标准库里的 list(也就是 std::list )就得多加小心。比如下面的代码:

std::list node_list;
...
NodeData a = node_list.front();
...
node_list.remove(a);

熟悉 STL 的人可能一眼发现其中的陷阱:node_list.remove(a) 可不是一个 O(1) 的操作(虽然经典链表的删除操作是)。这是因为 std::list<T>::remove(const T&) 实际是一个经典链表的查找操作加上一个经典删除操作。虽然能看出这个问题的人也许不在少数,但是犯下这个错误的人也不在少数。而且,当前者遇到后者编写的代码时,修改起来往往很头疼。因为虽然 NodeData 是从链表中取出的,但是它并没有存储前后节点的信息。所以要想把上面的有缺陷的代码改正,必须把所有涉及到 NodeData 参数传递和临时存储的地方都加以修改。所以说,使用 std::list::front() 这样的拷贝语义函数的行为本身看起来就是个错误。

这里先插上两句说说所谓『经典』链表(因为后文会拿来比较)。很多数据结构的书里的链表就是把 NodeData 这个对象本身加上一个 prev 指针和一个 next 指针,用来分别指向前一个和后一个节点。所以『经典』链表的数据结构和节点数据本身由一个对象表示。经典链表对 NodeData 的定义是侵入式的 —— 如果你希望把一个原来和链表操作完全没有联系的对象或者 struct 加入链表,就必须修改它本身的结构。相对的,std::list 的方式是把链表看成一种『容器』,包容原有的对象而无需修改其结构。

所以你的第一反应也许是应该永远用 std::list::begin() 或者 --std::list::end() 之类的操作返回 iterator,相比 NodeData,iterator 更像经典链表的节点,带有前后节点的联系。但是 C++ 永远不会给你简单的方案。这个方案的问题在当在代码的多处拥有指向同一个 NodeData 的 iterator 时,调用任何一个 iterator 或者 list 本身的 erase() 方法都会导致其它 iterator 失效。而且,C++ 标准库仅仅告诉你唯一的以定义行为是其它 iterator 会『失效』。你甚至没有一个 valid() 方法来检验一个 iterator 是否失效。C++ 标准期待的是你无论如何知道这一状态并且决不能再对那些 iterator 做任何操作。

所以 std::list 相比『经典』链表有两个致命问题。第一是直接取出 NodeData 的操作丢失了和 list 本身的联系,让后续操作承受性能损失。第二,『经典』链表可以通过设置 prev/next 让任何拥有 NodeData 指针的代码轻易的判断一个节点数据是否还在链表中,而 std::list 对 iterator 行为的粗略定义让这一点变得不可行。

接下来我们把问题搞得更全面(也更复杂)一些,考虑 NodeData 的生命周期。C++ 标准库一贯的拷贝语义让这个问题得到了(幼稚地)解决。但是对于 std::list 来说,我们已经看到拷贝语义的操作会让取出的节点丢失和 list 的联系,而总是取出 iterator 又会带来失效的问题。

当然,经典链表虽然没有 iterator 失效问题,但是仍然要面对何时销毁节点数据本身的问题。不过,讽刺的是并非所有的数据都是可复制(copiable)的,所以 std::list 里面存储的也经常并非数据本身,而是数据的指针。因此,在同样面对 std::list<NodeData> 的『联系切断』和『iterator 失效』两难之际,std::list<NodeData*> 还必须面对经典链表的销毁节点数据的时机问题。更遗憾的是,C++ 的内存管理法宝 shared_ptr 在这个问题上完全无能为力。一个 std::list< shared_ptr<NodeData> > 同样拥有『联系切断』和『iterator 失效』的矛盾。这时只有经典链表,加上在 NodeData 中实现手工引用计数才算一个比较完美的方案。

链表是 C++ 的好几个设计理念走麦城的地方。链表重在『链』,它的灵活性就在于『链』。把链表作为『容器』,特别是和 STL 其它容器一样保持拷贝语义操作就毁了链表。而且基于拷贝构造和自动析构的共享指针和手工的引用计数相比也并非处处领先。

如果一开始能抛开 STL 那种容器的概念和对数据节点不侵入的要求,C++ 的链表设计不会这么差。比如 Linux 内核的链表设计,把链表节点作为链表数据的一部分,让链表数据包含节点,而不是反之。这样的设计用 C++ 模版也完全可以作到。(当然我更喜欢 Linux 内核的基于宏的设计,而且 Linux 的设计通过一个可被优化的 forced cast 同样保证了类型安全。)

后记:

写这篇 blog 的时候又重温了一下 Java 的 LinkedList 文档,发现 C++ 还不是最差的。LinkedList 的文档是,至少 6.0 还如此 —— 对 LinkedList 做的任何结构更改(什么意思?删除节点算吗?)都会导致所有已经获取的 iterator 失效。什么玩艺,这样的话我还用链表干什么?

6条回应 to “链表迷魂阵”

  1. fuzhou Says:

    remove()操作是个麻烦。至少VS的STL7.0的确是如老兄所言。

    就是有些细节上,我觉得有误导的嫌疑:

    a) node_list.front() 返回的不是取值而是引用。
    b) iterator的问题在于它一开始就不打算支持垃圾收集。老哥你多引用支持做理由,未免要求太多了。

    • sipoint Says:

      我没有单独谈iterator,也没有讨论是否应该让iterator支持什么,而是在说std::list缺少一个真正取出『经典』节点的操作。front()取出的东西缺少next/prev联系,iterator又存在失效问题。像『经典』节点那样有next/prev联系又不会失效的操作在std::list里没有。

      • fuzhou Says:

        从个人的实践角度上说,我倒没觉得失去了经典节点操作给我带来了什么问题。

        不过我同意STL的实现对形式完美的考虑似乎超过了实用标准,以至于忽略了一个“节点是否仍在队列中”的操作。从STL的整体角度上看,这符合STL的设计目的,不过时间中却带来了一些不便,有些可惜。

  2. fuzhou Says:

    >>> 『经典』链表可以通过设置 prev/next 让任何拥有 NodeData 指针的代码轻易的判断一个节点数据是否还在链表中。

    如果确实考虑生命期管理问题,在C的立场上这句话是不成立的。因为如果使用多个指针指向这个节点,而不是节点中的数据,那么它一样可能有有指针失效的问题。别忘了free()掉一块buffer时里面的内容如何变化在C规范也是没有定义的。

    所以除非将垃圾收集引入语言,否则指针失效问题在“传统”和STL风格的链表例都存在。

    简而言之,如果承认interator这个概念在设计上就没有将生命期纳入考虑——根据我的了解,这也就是STL最初的设计目的之一——那么老兄说的问题都不再是问题,而是设计决定。如果明知这一点还要拿生命期进行指责的话,未免有失公允了。

    • sipoint Says:

      主旨是STL链表应该提供iterator之外的更接近经典链表的一些操作。重点不在iterator本身设计的如何,而是STL链表缺乏必要的操作,而iterator只是用来说明现有的操作并不够用的部分说明。

  3. nic Says:

    iterator可以失效的设计是为了性能的妥协,因为修改容器时可能会重新分配容器数据的内存,而iterator也为了性能被设计成类似指针的形式。但是我们完全可以不改变接口而采用经典链表的实现方式,于是C的优点完全可以继承,还拥有STL的高级抽象能力。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s


%d 博主赞过: