Rust - SparseList<T>

SparseList<T>实现了一个稀疏列表数据结构，它具有以下特点：

核心概念

• 维护一个固定大小的底层数组 (Vec<Option<T>>)

• 支持高效的索引重用（删除元素后，其索引可以被新插入的元素重用）

• 通过 free_indices队列管理可用的空闲索引

主要特性

1. 插入操作 (insert)

• 优先使用空闲索引（如果有的话）

• 如果没有空闲索引，则追加到数组末尾

• 返回插入位置的索引

2. 删除操作 (remove)

• 将指定位置的元素设为 None

• 将该索引加入空闲索引队列

• 返回被删除的元素

3. 内存管理

• 不会收缩底层数组：删除元素只是标记为可用，不释放内存

• 索引重用机制避免内存碎片

• clear()会重置所有位置为空，但保持数组容量

使用场景

这种数据结构适用于：

• 对象池/资源管理：需要频繁创建销毁对象，且希望重用标识符

• 游戏开发：实体组件系统（ECS）中的实体ID管理

• 需要稳定索引的场景：索引在对象生命周期内保持不变

use std::collections::VecDeque;

pub struct SparseList<T> {
    data: Vec<Option<T>>,
    free_indices: VecDeque<usize>,
}

impl<T> SparseList<T> {
    pub fn new() -> Self {
        SparseList {
            data: Vec::new(),
            free_indices: VecDeque::new(),
        }
    }

    pub fn insert(&mut self, value: T) -> usize {
        if let Some(index) = self.free_indices.pop_front() {
            self.data[index] = Some(value);
            index
        } else {
            self.data.push(Some(value));
            self.data.len() - 1
        }
    }

    pub fn remove(&mut self, index: usize) -> Option<T> {
        if index < self.data.len() {
            let ret = self.data[index].take();
            self.free_indices.push_back(index);
            ret
        } else {
            panic!("Index out of bounds");
        }
    }

    pub fn clear(&mut self) {
        self.data.iter_mut().for_each(|item| *item = None);
        self.free_indices.clear();
        self.free_indices.extend(0..self.data.len());
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.data.len() {
            self.data[index].as_ref()
        } else {
            None
        }
    }

    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index < self.data.len() {
            self.data[index].as_mut()
        } else {
            None
        }
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }
}