马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
std::vector 和 std::list 是 C++ 标准库中两种常用的容器，它们都用于存储和管理元素聚集，但在底层实现和性能特性上有显著的区别。
1. 底层实现
- std::vector:
- 基于动态数组实现。
- 元素在内存中是连续存储的。
- 支持随机访问（通过下标访问元素）。
- 当容量不足时，会重新分配更大的内存块，并将所有元素复制到新内存中。
- std::list:
- 基于双向链表实现。
- 元素在内存中是非连续存储的，每个元素包含指向前后元素的指针。
- 不支持随机访问，只能通过迭代器次序访问。
- 插入和删除操纵不会导致内存重新分配。
2. 性能特性
操纵std::vectorstd::list随机访问O(1)（通过下标直接访问）O(n)（需要遍历链表）尾部插入/删除O(1)（假如不需要扩容）O(1)头部插入/删除O(n)（需要移动所有元素）O(1)中央插入/删除O(n)（需要移动部门元素）O(1)（找到位置后直接插入/删除）内存占用较小（仅存储元素，无额外开销）较大（每个元素需要额外存储两个指针）缓存友好性高（元素连续存储，缓存命中率高）低（元素非连续存储，缓存命中率低） 3. 适用场景
- std::vector:
- 需要频仍随机访问元素的场景。
- 元素数量变化不大，或者主要在尾部插入/删除元素的场景。
- 对缓存性能要求高的场景。
- std::list:
- 需要频仍在任意位置插入/删除元素的场景。
- 不需要随机访问元素的场景。
- 元素数量变化较大的场景。
4. 实例
- #include <iostream>
- #include <vector>
- #include <list>
- int main() {
- // std::vector 示例
- std::vector<int> vec = {1, 2, 3};
- vec.push_back(4); // 尾部插入
- vec.insert(vec.begin() + 1, 5); // 中间插入
- std::cout << "Vector: ";
- for (int v : vec) std::cout << v << " "; // 随机访问
- std::cout << std::endl;
- // std::list 示例
- std::list<int> lst = {1, 2, 3};
- lst.push_back(4); // 尾部插入
- lst.insert(std::next(lst.begin()), 5); // 中间插入
- std::cout << "List: ";
- for (int l : lst) std::cout << l << " "; // 顺序访问
- std::cout << std::endl;
- return 0;
- }
|
