索引列表

索引列表是数组和链表的混合体，具有各自的一些属性。每个元素在数组中都有一个索引，可以直接在那里访问。这个索引在元素保持在列表中且不受列表中其他元素影响的情况下是持久的。如果元素在列表中移动，或者从列表中插入或删除其他元素，索引都不会改变。

用户不需要知道索引的确切值，也不应该自己创建任何索引，但可以安全地复制现有的一个。索引仅应用于在特定位置访问元素数据或遍历列表的目的。这就是为什么几乎所有的索引方法都是私有的。

当在列表中插入新元素时，其索引将由该方法返回，但用户可以安全地忽略该值，因为无论如何都可以通过遍历列表来获取元素。

在添加新索引之前，旧索引将按先进先出（FIFO）的方式重复使用。

索引列表设计

列表元素被放置在一个向量中，因此可以直接访问，其中每个元素都知道其前后元素的索引以及该索引处的数据。这种间接性使得在Rust中安全实现列表变得容易，因为传统的下一个和上一个指针被相应的索引替换，这些索引只是数字。

你可以将列表节点想象成这样

struct IndexElem<T> {
	next: Option<u32>,
	prev: Option<u32>,
	data: Option<T>,
}

其中没有数据的元素是空闲的，如果next或prev是None，那么这就是该方向的列表末尾。

元素向量

除了直接访问元素外，元素向量提供了更好的内存效率以及它们之间的局部性，这在遍历列表时非常有用，因为它可能意味着更少的缓存未命中。然而，元素在向量中可能会出现混乱，只有通过遍历列表才能建立正确的顺序。

遍历列表

要遍历列表，用户需要一个起始索引。可以从 first_index 或 last_index 方法调用中获取一个。然后使用 next_index 或 prev_index 方法在相应方向上移动。只要元素没有被删除，索引在列表中就是持久的，并且可以在以后存储和使用。索引通常是随机的，因为列表是遍历的。

请参阅包含的示例代码，了解其工作方式。

请注意，任何对 trim_swap 方法的调用都可能使一个或多个索引失效。可以通过任何大于 capacity 的索引已移动来验证这一点。为了防止这种失效，您可以同时持有对列表和索引的引用，但这也会阻止在引用保持期间对列表进行任何修改。

列表容量

索引列表会在添加新元素时自动增长。在添加新索引之前会重用旧索引。然而，元素向量不会自动缩小。相反，用户需要选择机会来减小列表容量，以适应当时实际需要的容量。

有一个安全的方法（trim_safe），它实际上可能根本不会缩小列表，因为它只会释放向量末尾的任何未使用索引。

然后是另一个不安全的方法（trim_swap），它会将元素交换到向量的末尾，然后截断向量。它被称为不安全，因为所有高于所需容纳所有使用元素的截止点的索引都将失效。因此，如果用户将这些索引存储在任何地方，它们将不再返回正确的数据。

可变迭代器

目前没有 iter_mut 方法，但是有一个简单且安全的模式可以实现相同的效果，使用 while 循环。

let mut index = list.first_index();
while index.is_some() {
    let elem = list.get_mut(index).unwrap();
    *elem = elem.to_string().to_lowercase();
    index = list.next_index(index);
}

请参阅iter_mut_alternative.rs 以获取完整示例。

安全的 Rust

索引列表没有不安全代码块。原因是它不使用元素之间的指针，而是使用它们在向量中的索引。

然而，trim_swap 方法被认为是不可靠的，但原因完全不同，因为它可能会改变某些元素的索引。因此，任何缓存的索引在方法调用后可能无效，并在索引重用时最终指向不同的元素。请明智地使用此方法，并确保在此期间不保留此类索引。

性能

在我的简单基准测试中，索引列表似乎提供了比 LinkedList 多两倍以上的性能，并且它还提供了一些 LinkedList 仅作为实验性功能的功能，例如光标方法。

然而，这可能不会反映任何实际性能差异，并且强烈建议您在自己的用例中进行评估，而不是依赖包含的基准测试中提供的数字。

使用 IndexList 的原因

• 经常从列表的主体中插入或删除数据（不是两端）。
• 经常重新排序或排序的数据。
• 即使在插入或删除数据时，也需要持久索引。
• 希望维持跳过元素以通过列表进行更大步长的操作。
• 需要缓存某些元素以实现快速检索，而不保留对其的引用。

使用替代方案的原因

• 当数据主要在列表两端插入和删除时，VecDeque 可能是更好的替代方案。
• 列表的合并和拆分很常见；在 IndexList 设计中，这些是重 O(n) 操作。在这方面，LinkedList 可能要更好。
• 当处理超过 40 亿次条目的列表时，因为此列表限制为 32 位索引。
• 当需要经常缩小列表时，因为 trim_swap 成本高昂，并且可能具有使索引无效的副作用。例如，LinkedList 完全不需要修剪。

这并不是替代方案的完整列表，我可能遗漏了一些重要的选择，但这些是在撰写此文档时我所了解的。

• std::collections::LinkedList
• std::collections::VecDeque
• std::vec::Vec