vector

1. 容器概述

1.1 vector

• 动态数组：vector基于动态数组实现，这意味着它的元素在内存中是连续存储的。
• 随机访问：由于元素的连续性，vector支持快速的随机访问。

1.2 list

• 双向链表：list基于双向链表实现，每个元素通过指针连接到前一个和后一个元素。
• 非连续存储：元素在内存中不是连续存储的，这使得元素的插入和删除操作更加灵活。

2. 性能比较

2.1 访问速度

• vector提供了O(1)时间复杂度的随机访问能力，可以直接通过索引访问元素。
• list的访问速度较慢，需要O(n)时间复杂度来访问特定位置的元素。

2.2 插入和删除

• vector在中间插入或删除元素时，需要移动插入点后的所有元素，时间复杂度为O(n)。
• list可以在O(1)时间内完成元素的插入和删除，只需调整相邻节点的指针。

2.3 内存使用

• vector通常使用较少的额外内存，因为它是连续存储的。
• list由于需要存储额外的指针，所以每个元素的内存开销更大。

3. 功能特性

3.1 容量管理

• vector会自动管理其容量，当需要更多空间时会进行扩容操作。
• list没有容量的概念，因为它不预先分配内存。

3.2 迭代器失效

• 在vector中，插入或删除操作可能会使迭代器失效。
• list的迭代器在插入和删除操作后仍然有效，除非被删除的元素的迭代器。

4. 适用场景

4.1 使用vector的场景

• 当你需要快速随机访问元素时。
• 当插入和删除操作不频繁，或者主要在容器的末端进行时。
• 当内存使用是一个考虑因素时。

4.2 使用list的场景

• 当你需要频繁地在容器中间插入或删除元素时。
• 当你需要一个双向可迭代的容器时。
• 当元素的大小较大，且不希望因插入操作而移动大量元素时。

5. 实例代码

5.1 使用vector

#include <vector>
#include <iostream>

int main() {
   
    std::vector<int> vec = {
   1, 2, 3, 4, 5};
    vec.push_back(6); // 在末尾添加元素
    for (int num : vec) {
   
        std::cout << num << " ";
    }
    return 0;
}

5.2 使用list

#include <list>
#include <iostream>

int main() {
   
    std::list<int> lst = {
   1, 2, 3, 4, 5};
    lst.insert(lst.begin(), 0); // 在开始处插入元素
    for (int num : lst) {
   
        std::cout << num << " ";
    }
    return 0;
}