面试题：自定义类似Rust向量动态扩展机制

Question

假设你需要在Rust中自定义一个数据结构，其行为类似Vec的动态扩展机制。请详细描述你将如何设计该数据结构，包括底层存储、动态扩展策略、内存管理等方面。编写核心代码来实现该数据结构的关键功能，如添加元素和内存重分配逻辑，并分析你的实现的时间和空间复杂度。

Answer 1

1. 设计思路

1. 底层存储：使用Box<[T]>作为底层存储，Box用于堆分配内存，[T]表示连续的数组。
2. 动态扩展策略：当当前容量不足以容纳新元素时，将容量翻倍。
3. 内存管理：Rust的所有权系统会自动管理内存的分配和释放。当数据结构被销毁时，Box<[T]>中的内存会自动释放。

2. 核心代码实现

struct MyVec<T> {
    data: Box<[T]>,
    capacity: usize,
    len: usize,
}

impl<T> MyVec<T> {
    fn new() -> Self {
        MyVec {
            data: Box::new([]),
            capacity: 0,
            len: 0,
        }
    }

    fn push(&mut self, element: T) {
        if self.len == self.capacity {
            self.resize();
        }
        self.data[self.len] = element;
        self.len += 1;
    }

    fn resize(&mut self) {
        let new_capacity = if self.capacity == 0 { 1 } else { self.capacity * 2 };
        let mut new_data = Vec::with_capacity(new_capacity);
        new_data.extend_from_slice(&self.data[..self.len]);
        self.data = new_data.into_boxed_slice();
        self.capacity = new_capacity;
    }

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

    fn capacity(&self) -> usize {
        self.capacity
    }
}

3. 时间和空间复杂度分析

1. 时间复杂度：
   • push操作：平均情况下，由于翻倍策略，每次push操作分摊的时间复杂度为$O(1)$。当需要扩容时，需要复制旧数据到新的内存空间，时间复杂度为$O(n)$，但这种情况发生的频率随着n的增大越来越低。
   • resize操作：时间复杂度为$O(n)$，因为需要将旧数据复制到新的内存空间。
2. 空间复杂度：
   • 空间复杂度为$O(n)$，其中n是当前存储的元素个数。由于采用翻倍策略，实际分配的内存可能会比当前元素个数略多，但仍然是$O(n)$级别的。