底层数据结构

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 #include int main() {std::vector 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; // 输出: 3return 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