Lib.rs

› 数据结构
#linked-list #rc #doubly-linked #suitable

rc-dlist-deque

基于std::Rc的双向链表

作者：Ian Jackson. 协作者： Tony Finch.

5 个版本 (稳定版)

1.1.2 2022年11月16日
1.1.1 2022年11月12日
1.1.0 2022年11月7日
1.0.0 2019年5月10日
0.1.1 2019年3月9日

#957 在 数据结构 中

GPL-3.0-or-later

63KB
710 行

rc_dlist_deque - 基于 std::Rc 的双向链表

请参阅文档（在线副本）。

源代码、问题等在这里：https://salsa.debian.org/iwj/rc-dlist-deque

版权 (C) 2019-2022 Ian Jackson; GNU GPLv3+; 不提供任何担保。

lib.rs:

rc-dlist-deque - 基于 std::Rc 的双向链表

该软件包提供了在适合使用Rc管理单个节点的情况下，双向链表的实现。

如何使用此软件包

请参阅模块级文档

何时不使用此软件包

许多初学Rust的程序员在另一种数据结构更适合时寻找链表。考虑使用 Vec 和 VecDeque。双向链表在以下情况下很好：

  • 你需要保留和存储对列表中间的引用，并且需要快速访问相应的项，并且

  • 你需要能够快速在列表的中间添加或删除项，基于此类引用；或者当你在列表中间的其他位置添加或删除其他项时，对这些中间引用必须保持有效，并且

  • 你的列表可能很长。

在其他情况下，即大多数情况下，你可能更希望使用 Vec 或 VecDeque。它们的开销更低，更容易使用。

特别是

  • 如果你不需要在中间添加/删除项，那么 Vec 或 VecDeque 可以很好地工作。你可以使用数组索引作为你的引用。

  • 如果你需要一个具有稳定索引的 VecDeque，这可以通过维护一个元素在起始处推入/弹出的有符号计数器来实现，如 vecdeque-stableix 所做的那样。

  • 如果您不需要保留对列表中间部分的长期引用，则可以使用向量。在列表中间添加或删除项目确实意味着需要复制来重新排列项目，但如果您没有保留修改位置的引用，您仍然需要遍历以找到正确的地方。

请注意，有一些类似deque的替代方案，这些方案不是双链表，也不旨在支持在列表中间进行修改，其中一些似乎可能很有用。在crates.io上搜索deque，还可以考虑blist。

其他双链表库

如果您确实需要一个双链表，但不需要您的项目同时出现在多个列表中，请考虑使用generational_token_list。它有一个更简单的所有权模型，并且速度也会更快。

如果您希望每个项目能够同时出现在多个列表中（也许甚至可以在运行时动态地选择每个节点中的链表链接），那么这个crate rc-dlist-deque可能正是您想要的。

可用的Rust双链表概述，与VecDeque进行比较

（此表由Rustdoc、lib.rs等渲染得相当糟糕。请使用用pandoc独立构建的正确格式版本代替。）

<style> table.dlist_survey th, table.dlist_survey td { border-top-color: black; border-bottom-color: black; border-left-color: black; border-right-color: black; border: 1px solid; text-align: center; vertical-align: middle; } </style>
crate或模块 元素引用（即索引或游标） 其他可能的误用及其后果 列表所有者（T是元素类型） 在中间编辑的成本 内存局部性 元素可以出现在多个列表中 API完备性 Send/​Sync 安全性 注释
类型 在更改前端/后端列表之后 在更改中间列表之后 在删除引用元素之后 给定元素引用 没有元素引用
选择以下方法之一
std VecDeque
（或另一个deque库）		 usize
位置		 如果更改开始处的元素，则将出现错误元素 错误元素（或None或panic） 丰富的API可能会使索引无效 T O(n) O(n) 顺序的 - ++ 是 良好 如果您不需要持久的游标，则使用它
vecdeque-stableix i64 isize ... 有效的 不支持 索引可能会溢出，导致panic。 顺序的 - + 是 安全 如果您只需要在末端进行修改，则考虑使用它
rc-dlist-deque 指针<L,S> 有效的 有效的 有效的 指定错误的列表进行更改：debug_assert，“纠缠” Rc<T> O(1) 散列到堆上 是 + - 安全 如果您需要每个元素出现在多个列表中，则考虑使用它
generational_token_list 项目令牌
槽+代		 有效的 有效的 可靠地None（[] panic） 指定错误的列表进行访问或更改：可能会意外检测到，给出None，否则是错误元素 T 向量中的随机顺序 - ++ 是 安全（除IterMut外） 否则，使用以下方法之一
dlv-list 索引<T>
槽+代		 ++
使用generational_token_list或dlv-list代替以下任何一种
chainlink 索引
槽+代		 有效的 有效的 可靠地None 指定错误的列表进行访问或更改：可能会意外检测到，给出None，否则是错误元素 T O(1) O(n) 向量中的随机顺序 - - 是 安全 没有IterMut；否则可能
indexlist 索引<T>
槽+代		 - - - 是 安全
index_list 索引
槽		 None（或恐慌），或者（稍后）错误的元素 - + 是 安全
slabigator usize
槽		 T O(1) 向量中的随机顺序 - - 是 使用 unsafe usize 块索引是一个糟糕的 API 选择
数组-链表 usize
槽		 T O(1) 向量中的随机顺序 - + 是 不必要的 unsafe
im/im-rc Vector usize
位置		 如果更改开始处的元素，则将出现错误元素 错误元素（或None或panic） T O(log(n)) 堆中的块 - + im 使用 unsafe usize 位置索引是一个正确性风险
跳转链表 T O(log(n)) 散列到堆上 - - - 使用 unsafe
cddl Cursor，DoubleCursor 有效的 有效的 不支持 T O(1) 散列到堆上 - - - - - 使用 unsafe 奇怪且有限的 API
使用 VecDeque 而不是以下任何一种
intrusive-collections linked_​list Cursor​[Mut] 当存在任何其他光标时无法进行修改（由生命周期阻止）。这几乎完全抵消了使用双链表的意义。 各种 O(1) O(n) 散列到堆上 是 + 是 使用 unsafe 如果这个 API 对你来说足够了，请使用 VecDeque
cordyceps List Cursor​[Mut]（大致） 不安全 实现 处理 散列到堆上 - 是 unsafe 使用！
tsil_cev Cursor​[Mut] T 向量中的随机顺序 - 是 安全（除IterMut外）
ixlist Cursor T - + 是 不必要的 unsafe
链表 Cursor T 散列到堆上 - 是 使用 unsafe
循环链表 Cursor​[Mut] T 散列到堆上 是 使用 unsafe
固定列表 Cursor​[Mut] 复杂 用户提供 Pin<&mut Node> - 是 使用 unsafe
键节点列表 Cursor​[Mut] T O(log(n)) 在向量中（通过 HashMap） - - 是
std LinkedList 不支持。这违背了使用双链表的意义。 T n/a 散列到堆上 - 是
双 T 散列到堆上 - 是 使用 unsafe
linked_lists_rs / rust_linked_list T 散列到堆上 - 是 使用 unsafe
xor_list T 散列到堆上 - - 使用 unsafe
索引队列 T 顺序的 - - - 是 VecDeque 的重新实现

在不使用 unsafe 的情况下实现 IterMut 可能很困难，因此不对使用 unsafe 的这些 crate 进行批评。

未考虑

单端，或专用

未在此处考虑，因为它们是单端列表（因此几乎没有理由使用除了 Vec 以外的任何东西）；或者因为它们是专用

c_linked_list，char-list，concurrent_list，cons-list，doubly_linked_list，fplist，functional_list，fwdlist，im-list，linked_hash_map，linked_hash_set，linked_list_allocator，linked-tail-list，list，moonlight_collections，nerdondon-hopscotch，nt_list，persistent-list，rose_bloom，secured_linked_list，simple-stack，stack_list，static-linkedlist，weak-list2，uell，unrolled_linked_list。

不打算（或不适合）用于通用用途

由于文档质量差或缺失、API非常糟糕、仅限Nightly版本、无法构建或其他表明它们不打算（或不适合）供全世界使用的信息，因此未在此处考虑

cll，clist，double_linkedlist，dynalist，ilist，linkedlist，rs_trie，static-linkedlist，matecito-dll。

调查序言

最后更新和最后重新调查的时间为2022年11月。如果我在将来进行调查，我可能只查看最受欢迎的crate。如果您认为您的库应该列在“选择这些方法之一”的部分，请告知我。

rc-dlist-deque的变更日志和序言

最低支持的Rust版本是1.31.0。MSRV策略：我们预计在可预见的未来不会更改MSRV。如果我们这样做，它至少是次版本升级。我们不会将MSRV提高到Debian oldstable中可用的版本以上。

1.1.2

  • 对双链表调查的次要更新（crate级别文档）。
  • 没有API或实现更改。

1.1.1

  • 对双链表调查的次要更新（crate级别文档）。
  • 没有API或实现更改。

1.1.0

  • MSRV 1.31.0（以前是1.30.0）
  • 改为2018版。
  • 添加此变更日志。
  • 更新双链表调查（crate级别文档）。
  • 文档生成和发布安排的更改。

1.0.0

  • 文档。没有API或实现更改。

0.1.0

  • 首次公开发布。

rc-dlist-deque版权所有2019-2022 Ian Jackson。GNU GPLv3+；无担保。

无运行时依赖