27.介绍一下vector、list的底层实现原理和优缺点？

C++ vector 和 list 底层实现原理与优缺点详解

1. vector 的底层实现与特性

底层实现

• 动态数组：vector 的底层是一个连续内存的动态数组，类似于 T* data + size + capacity 的结构。
• 扩容机制：
  • 当 size == capacity 时，vector 会申请一块更大的内存（通常是 2倍扩容，不同编译器可能不同）。
  • 将旧数据拷贝到新内存，释放旧内存。
  • 扩容时间复杂度：均摊 O(1)（因为扩容不是每次插入都发生）。

核心操作的时间复杂度

优点

✅ 高速随机访问：由于内存连续，vector[i] 直接计算地址，访问极快（CPU缓存友好）。
✅ 内存紧凑：无额外指针开销，存储密度高。
✅ 尾部操作高效：push_back() 和 pop_back() 在大多数情况下是 O(1)。

缺点

❌ 中间插入/删除慢：insert() 和 erase() 需要移动元素，时间复杂度 O(n)。
❌ 扩容成本高：扩容时需要拷贝所有元素，可能引发性能抖动。
❌ 内存浪费：capacity 可能远大于 size（例如扩容后删除大量元素）。

2. list 的底层实现与特性

底层实现

• 双向链表：list 的底层是一个双向循环链表，每个节点包含：

struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;
};

• 无扩容机制：每次插入/删除只需调整指针，无需内存拷贝。

核心操作的时间复杂度

优点

✅ 任意位置插入/删除快：insert() 和 erase() 只需调整指针，时间复杂度 O(1)。
✅ 无扩容开销：动态增删节点，不会发生内存拷贝。
✅ 内存利用率高：按需分配节点，无 capacity 浪费。

缺点

❌ 随机访问慢：访问第 i 个元素需要遍历链表，时间复杂度 O(n)。
❌ 内存碎片化：节点分散存储，缓存局部性差（CPU缓存不友好）。
❌ 额外存储开销：每个节点需要存储 prev 和 next 指针（64位系统每个指针占 8 字节）。

3. vector vs list 对比总结

4. 如何选择？

优先用 vector 的情况

• 需要快速随机访问（如 v[i]）。
• 尾部操作频繁（如 push_back/pop_back）。
• 内存紧凑性重要（例如嵌入式系统、高性能计算）。

优先用 list 的情况

• 需要频繁在中间插入/删除（如实现 LRU Cache）。
• 元素较大（避免 vector 扩容时的拷贝开销）。
• 不需要随机访问（如仅需顺序遍历）。

替代方案

• 如果既需要随机访问又需要高效插入/删除，可以考虑：
  • deque（双端队列，介于 vector 和 list 之间）。
  • unordered_map + list（例如 LRU Cache 实现）。

5. 代码示例

(1) vector 的扩容测试

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        std::cout << "Size: " << v.size() 
                  << ", Capacity: " << v.capacity() << std::endl;
    }
    return 0;
}

输出示例（不同编译器扩容策略可能不同）：

Size: 1, Capacity: 1
Size: 2, Capacity: 2
Size: 3, Capacity: 4
Size: 5, Capacity: 8
...
Size: 100, Capacity: 128

(2) list 的高效插入

#include <iostream>
#include <list>

int main() {
    std::list<int> l = {1, 2, 3};
    auto it = l.begin();
    ++it; // 指向第二个元素
    l.insert(it, 99); // 在第二个位置插入 99

    for (int x : l) {
        std::cout << x << " "; // 输出: 1 99 2 3
    }
    return 0;
}

6. 总结

• vector：适合随机访问+尾部操作，但中间插入/删除慢。
• list：适合频繁插入/删除，但随机访问慢。
• 选择依据：根据具体场景权衡访问模式、内存占用和缓存友好性。