C++ STL：list和vector的比较

时间：2024-02-20 13:49:15

底层数据结构

Vector: 底层实现为动态数组，提供了一段连续的内存空间。这种连续存储使得 vector 能够提供快速的随机访问能力。

随机访问（通过索引访问元素）的时间复杂度为 O(1)。

因为可能涉及内存重新分配和数据移动，所以在尾部插入和删除操作的平均时间复杂度接近 O(1)。

因为可能需要移动后续或前面的元素，所以在中间或开始进行插入或删除操作的时间复杂度为 O(n)。

List: 底层实现为双向链表，由分散的内存块通过指针链接而成，使其在插入和删除操作上更加高效，但牺牲了随机访问的性能。

因为需要从头部或尾部遍历，随机访问的时间复杂度为 O(n)。

因为只需要修改指针，而不涉及元素的移动，插入和删除操作的时间复杂度接近 O(1)。

容量管理

Vector: 当当前容量不足以容纳新元素时，vector 会自动增加其容量（通常是加倍），这涉及到现有元素的复制和移动到新的内存地址。

List: 每次插入或删除操作只涉及局部内存分配或释放，不需要整体移动其他元素。

   由于 vector 的连续内存特性，可能会导致更大的内存预留（容量）以减少重新分配的频率，而 list 的内存使用更为紧凑，但每个元素需要额外的空间来存储前后节点的地址。

迭代器支持

Vector: 支持随机访问迭代器，可以进行 +、-、<、> 等操作。

List: 仅支持双向迭代器，不支持随机访问操作，但支持 ++ 和 -- 来前后移动。

  list不能使用普通指针作为迭代器，因为它需要特殊的迭代器来正确地遍历链表，包括进行递增、递减、取值等操作​​。它提供的迭代器是双向迭代器（Bidirectional Iterators），允许前移和后移操作​​。

 vector中，插入操作可能会导致容器重新分配内存，这会使所有现有迭代器、引用和指针失效。list的插入和删除操作不会使除了“指向被操作元素”的迭代器之外的任何迭代器失效。即使是删除操作，也只有指向被删除元素的迭代器会失效，其他迭代器仍然有效​​。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4};

    // 插入前的迭代器
    auto it = vec.begin() + 2;
    std::cout << "Before insertion: " << *it << std::endl; // 输出: 3

    // 插入元素导致容量可能改变
    vec.insert(vec.begin() + 1, 99);

    // 尝试访问原迭代器（未定义行为，因为迭代器可能失效）
    // std::cout << "After insertion: " << *it << std::endl; // 未定义行为

    // 正确的做法是重新获取迭代器
    it = vec.begin() + 3;
    std::cout << "After insertion: " << *it << std::endl; // 输出: 3

    return 0;
}

缓存友好性

vector 由于其连续的内存布局，通常提供更好的缓存一致性和性能。

CPU 缓存是一种非常快速的内存，位于 CPU 和主内存（RAM）之间，用于减少从主内存访问数据的延迟。当程序访问内存中的数据时，它会尝试先从缓存中获取数据，因为从缓存读取数据比从主内存读取要快得多。

由于 vector 使用一段连续的内存空间来存储数据，这意味着当你访问 vector 中的一个元素时，相邻的元素很可能已经被预加载到 CPU 缓存中。这是因为 CPU 通常会预加载你访问的内存地址附近的数据，这个过程称为预取。当你遍历一个 vector 并访问它的元素时，由于数据连续存储，许多元素访问操作可能直接从缓存中进行，而不是从更慢的主内存中。这种特性使得 vector 在执行连续内存访问操作时，如遍历或顺序访问元素，具有很高的性能。

相比之下，list 使用的是非连续存储，即它的元素分布在内存的不同位置，通过指针链接。这种存储方式意味着即使你在遍历 list，相邻元素之间在物理上可能相隔很远，不能保证它们会一起被加载进 CPU 缓存。每次访问一个新的元素可能都需要从主内存中读取，因为这些元素不太可能已经在缓存中。所以 list 在许多情况下比 vector 在性能上要。

应用场景

Vector: 适用于需要频繁随机访问元素的场景，以及在尾部进行插入和删除操作的情况。

List: 更适合频繁在任意位置插入或删除元素的场景，尤其是当元素大小较大或复制成本较高时。

vector 由于其简单性和高性能通常是首选，除非有特定的理由需要使用 list 的特殊能力。

参考：

https://www.cnblogs.com/Sherloy/p/4979159.html

https://www.cnblogs.com/enterBeijingThreetimes/archive/2009/03/15/1412421.html


 

相关文章