Crate hicollections

source ·
Expand description

C-liked Collections: List/RbTree/AvlTree. List/RbTree/AvlTree本身不分配任何内存,也支持Send,但任何元素挂接到集合后,就不能支持转移和覆写, 元素是不支持Send的. BtreeMap/BTreeSet可以定制内部节点的内存分配策略.

Macros

  • 方便构造一个AvlTree.
  • 方便构造一个List.
  • 方便构造一个RbTree.

Structs

  • 类似List的设计思路,AvlTree支持Send. 支持基于Borrow<Q>实现比较插入,无需强制节点数据结构实现Ord Trait
  • 需要在用户数据结构中定义此类型的成员才能加入到AvlTree.
  • 用户可以定制内部节点的分配策略.
  • 用户可以定制内部节点的分配策略.
  • 增加到容器后的返回值类型,其生命周期参数为加入元素的生命周期. 在其生命周期内避免获取加入元素的可写引用.
  • C的实现版本中,List也成为链表中的一个节点,这在Rust中不可行. 原因是List无处不在的所有权转移,实际就是内存拷贝,但程序员无法干预, 导致拷贝之后,整个链表就被破坏了. 节点也是这样的, 加入链表后还需要避免任何所有权转移,节点的增删是unsafe的,但List是管理节点,要完全避免所有权转移非常困难. 因此这里设计为List不在链表环中, 可支持所有权转移后不影响链表,自然也支持Send. 由此也带来一些不方便之处:比如节点无法自删除,必须由List删除, 好处内存安全得到保证. 比如,不会出现在迭代过程中删除某个节点导致迭代器失效的异常情况.
  • 需要在用户数据结构中定义此类型的成员才能加入到List.
  • 类似List的设计思路,RbTree支持Send. 支持基于Borrow<Q>实现比较插入,无需强制节点数据结构实现Ord Trait
  • 需要在用户数据结构中定义此类型的成员才能加入到RbTree.