Lib.rs

未展开链表

未展开链表是一种线性数据结构，是链表的变种。未展开链表在每个节点中存储的不是1个元素，而是一个完整的数组。

未展开链表结合了数组（较小的内存开销）和链表（快速的插入和删除）的优点，从而产生大幅提升的性能。通过在每个节点中存储多个元素，未展开链表有效地将链表的开销（指针）分散到多个元素上。所以，如果一个未展开链表在每个节点中存储了一个包含4个元素的数组，它就将链表的开销（指针）分散到这4个元素上。

未展开链表的真实好处体现在缓存上。未展开链表在索引方面利用了这一点。

如何使用

依赖项可以在以下位置找到：unrolled-linked-list = 1.0.1

示例

use unrolled_linked_list::UnrolledLinkedList;

fn main(){
  let mut list = UnrolledLinkedList::new();
  list.insert(0, 1);
  list.push(2);
  list.push(3);
  list.insert(3,4);
  if let Some(four) =  list.pop() { println!(" should be {}", four)}
  
  let one_opt = list.get(0);
  let one_mut_opt = list.get_mut(0);

  list.remove(0);  

  for el in list.iter(){
    println!("elem {}",el);
  }    
 
}

与链表和vec的比较

详细信息请参见bench文件夹。数字和结果符合库criterion的典型格式。

典型结果示例

Benchmarking push/unrolled_linked_list
Benchmarking push/unrolled_linked_list: Warming up for 3.0000 s
Benchmarking push/unrolled_linked_list: Collecting 100 samples in estimated 5.0358 s (364k iterations)
Benchmarking push/unrolled_linked_list: Analyzing
push/unrolled_linked_list
                        time:   [14.078 us 14.776 us 15.527 us]
                        change: [+3.9244% +7.5033% +11.271%] (p = 0.00 < 0.05)
                        Performance has regressed.