【C++容器和算法】顺序容器

byte轻骑兵

发布于 2026-01-21 16:24:08

1170

在C++标准模板库（STL）中，容器是非常重要的工具。容器可以帮助我们管理一组对象，并且提供了各种操作这些对象的方法。顺序容器（Sequential Containers）是 C++ 标准库中的一类容器，它们按照元素插入的顺序来存储元素，并且可以通过元素的位置来访问它们。本文详细介绍 C++ 中的顺序容器，包括 vector、deque、list、forward_list 和 array，并提供相应的代码示例。

一、顺序容器概述

顺序容器提供了高效的元素存储和访问方式。不同的顺序容器在性能和使用场景上有所差异，主要体现在插入、删除元素的效率，以及随机访问的能力上。以下是 C++ 标准库中常见的顺序容器：

1.1 `vector`

vector 是最常用的顺序容器，它类似于动态数组。vector 可以自动调整大小以容纳更多的元素，并且支持随机访问。在尾部插入和删除元素的效率很高，但在中间或头部插入和删除元素的效率较低。

1.2 `deque`

deque 是双端队列，它支持在头部和尾部高效地插入和删除元素，同时也支持随机访问。与 vector 不同，deque 在头部插入和删除元素的效率也很高。

1.3 `list`

list 是双向链表，它支持在任意位置高效地插入和删除元素，但不支持随机访问。如果需要频繁地在中间插入或删除元素，list 是一个不错的选择。

1.4 `forward_list`

forward_list 是单向链表，它只支持单向遍历，不支持反向遍历。forward_list 在插入和删除元素方面比 list 更高效，但功能相对较少。

1.5 `array`

array 是固定大小的数组，它的大小在编译时就已经确定。array 支持随机访问，并且在性能上与普通数组相当，但提供了更多的标准库功能。

下面是一个简单的表格对比这些顺序容器的特点：

容器类型	随机访问	头部插入 / 删除	尾部插入 / 删除	中间插入 / 删除
vector	支持	低效率	高效率	低效率
deque	支持	高效率	高效率	低效率
list	不支持	高效率	高效率	高效率
forward_list	不支持	高效率	不支持	高效率
array	支持	不支持	不支持	不支持

二、`vector` 容器

2.1 `vector` 的基本使用

vector 位于 <vector> 头文件中，使用时需要包含该头文件。以下是一个简单的 vector 使用示例：

#include <iostream>
#include <vector>

int main() {
    // 创建一个空的 vector
    std::vector<int> vec;

    // 向 vector 中添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 访问 vector 中的元素
    for (int i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

首先创建了一个空的 vector，然后使用 push_back 方法向 vector 中添加元素，最后使用下标运算符 [] 访问 vector 中的元素。

2.2 `vector` 的常用操作

获取元素个数：可以使用 size() 方法获取 vector 中元素的个数。
检查是否为空：使用 empty() 方法检查 vector 是否为空。
访问元素：除了使用下标运算符 [] 访问元素外，还可以使用 at() 方法，at() 方法会进行边界检查，如果越界会抛出异常。
插入元素：可以使用 insert() 方法在指定位置插入元素。
删除元素：使用 erase() 方法删除指定位置的元素，使用 pop_back() 方法删除最后一个元素。

以下是一个包含更多操作的示例：

#include <iostream>
#include <vector>

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

    // 获取元素个数
    std::cout << "Size: " << vec.size() << std::endl;

    // 检查是否为空
    std::cout << "Is empty: " << (vec.empty() ? "Yes" : "No") << std::endl;

    // 使用 at() 方法访问元素
    std::cout << "Element at index 2: " << vec.at(2) << std::endl;

    // 在指定位置插入元素
    vec.insert(vec.begin() + 2, 10);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除指定位置的元素
    vec.erase(vec.begin() + 3);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除最后一个元素
    vec.pop_back();
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.3 `vector` 的内存管理

vector 会自动管理内存，当元素数量超过当前容量时，vector 会重新分配更大的内存空间，并将原有元素复制到新的内存空间中。可以使用 capacity() 方法获取 vector 当前的容量，使用 reserve() 方法预先分配一定的内存空间，以减少内存重新分配的次数。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    std::cout << "Initial capacity: " << vec.capacity() << std::endl;

    // 预先分配内存
    vec.reserve(10);
    std::cout << "Capacity after reserve: " << vec.capacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
    }
    std::cout << "Capacity after adding elements: " << vec.capacity() << std::endl;

    return 0;
}

三、`deque` 容器

3.1 `deque` 的基本使用

deque 位于 <deque> 头文件中，使用时需要包含该头文件。deque 的使用方法与 vector 类似，但它支持在头部和尾部高效地插入和删除元素。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> deq;

    // 在尾部插入元素
    deq.push_back(10);
    deq.push_back(20);

    // 在头部插入元素
    deq.push_front(5);

    // 访问元素
    for (int num : deq) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2 `deque` 的常用操作

deque 提供了与 vector 类似的操作，如 size()、empty()、at() 等，同时还提供了 push_front() 和 pop_front() 方法用于在头部插入和删除元素。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> deq = {1, 2, 3, 4, 5};

    // 获取元素个数
    std::cout << "Size: " << deq.size() << std::endl;

    // 检查是否为空
    std::cout << "Is empty: " << (deq.empty() ? "Yes" : "No") << std::endl;

    // 在头部插入元素
    deq.push_front(0);

    // 在尾部插入元素
    deq.push_back(6);

    // 访问元素
    for (int num : deq) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除头部元素
    deq.pop_front();

    // 删除尾部元素
    deq.pop_back();

    // 访问元素
    for (int num : deq) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

四、`list` 容器

4.1 `list` 的基本使用

list 位于 <list> 头文件中，使用时需要包含该头文件。list 是双向链表，支持在任意位置高效地插入和删除元素。

#include <iostream>
#include <list>

int main() {
    std::list<int> lst;

    // 在尾部插入元素
    lst.push_back(10);
    lst.push_back(20);

    // 在头部插入元素
    lst.push_front(5);

    // 遍历 list
    for (int num : lst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

4.2 `list` 的常用操作

list 提供了一些特殊的操作，如 insert() 可以在指定位置插入元素，erase() 可以删除指定位置的元素，splice() 可以将一个 list 中的元素转移到另一个 list 中。

#include <iostream>
#include <list>

int main() {
    std::list<int> lst1 = {1, 2, 3};
    std::list<int> lst2 = {4, 5, 6};

    // 在指定位置插入元素
    auto it = lst1.begin();
    ++it;
    lst1.insert(it, 10);

    // 遍历 lst1
    for (int num : lst1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除指定位置的元素
    it = lst1.begin();
    ++it;
    lst1.erase(it);

    // 遍历 lst1
    for (int num : lst1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 将 lst2 中的元素转移到 lst1 中
    lst1.splice(lst1.end(), lst2);

    // 遍历 lst1
    for (int num : lst1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

五、`forward_list` 容器

5.1 `forward_list` 的基本使用

forward_list 位于 <forward_list> 头文件中，使用时需要包含该头文件。forward_list 是单向链表，只支持单向遍历。

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flst;

    // 在头部插入元素
    flst.push_front(10);
    flst.push_front(20);

    // 遍历 forward_list
    for (int num : flst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

5.2 `forward_list` 的常用操作

forward_list 提供了一些特殊的操作，如 insert_after() 可以在指定位置之后插入元素，erase_after() 可以删除指定位置之后的元素。

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flst = {1, 2, 3};

    // 在指定位置之后插入元素
    auto it = flst.begin();
    flst.insert_after(it, 10);

    // 遍历 forward_list
    for (int num : flst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除指定位置之后的元素
    it = flst.begin();
    flst.erase_after(it);

    // 遍历 forward_list
    for (int num : flst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

六、`array` 容器

6.1 `array` 的基本使用

array 位于 <array> 头文件中，使用时需要包含该头文件。array 是固定大小的数组，需要在定义时指定数组的大小。

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 遍历 array
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

6.2 `array` 的常用操作

array 提供了与普通数组类似的操作，如 size() 可以获取数组的大小，at() 可以访问指定位置的元素。

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 获取数组的大小
    std::cout << "Size: " << arr.size() << std::endl;

    // 访问指定位置的元素
    std::cout << "Element at index 2: " << arr.at(2) << std::endl;

    return 0;
}

七、选择合适的顺序容器

在选择顺序容器时，需要根据具体的需求来决定使用哪种容器。以下是一些选择的建议：

如果需要随机访问元素，并且插入和删除操作主要在尾部进行，vector 是一个不错的选择。
如果需要在头部和尾部都进行高效的插入和删除操作，并且也需要随机访问元素，deque 是合适的。
如果需要频繁地在中间插入或删除元素，list 或 forward_list 是更好的选择。如果只需要单向遍历，forward_list 可以提供更高的效率。
如果数组的大小在编译时就已经确定，并且不需要动态调整大小，array 是一个不错的选择。

八、进阶技巧与注意事项

8.1. 迭代器失效问题

// 错误示例：在循环中保存end迭代器
std::vector<int> vec = {1,2,3};
auto end_it = vec.end();
for(auto it = vec.begin(); it != end_it; ++it) {
    if(*it == 2) {
        vec.erase(it); // 导致end_it失效
        break;
    }
}

// 正确做法：实时获取end迭代器
for(auto it = vec.begin(); it != vec.end(); ) {
    if(*it == 2) {
        it = vec.erase(it); // 返回下一个有效迭代器
    } else {
        ++it;
    }
}

8.2. 性能优化技巧

预留空间：对vector/string使用reserve()预分配内存
批量插入：使用insert(iter, first, last)代替多次单次插入
emplace操作：使用emplace_back()直接在容器内构造对象

8.3. 容器性能与内存管理

① 时间复杂度对比

操作容器	随机访问	头部插入	尾部插入	中间插入
vector	O(1)	O(n)	O(1)	O(n)
deque	O(1)	O(1)	O(1)	O(n)
list	O(n)	O(1)	O(1)	O(1)
forward_list	O(n)	O(1)	O(n)	O(1)

② 内存管理策略

vector扩容机制：

vector<int> v;
v.reserve(50); // 预分配内存
for(int i=0; i<100; ++i){
    v.push_back(i);
    std::cout << "Size: " << v.size() 
              << " Capacity: " << v.capacity() << std::endl;
}

扩容过程图示：

[元素][元素][元素][空] → 插入 → [元素][元素][元素][元素] → 扩容 → [元素][元素][元素][元素][空][空][空][空]

8.4. C++11/14/17新特性

非成员begin/end：支持统一获取迭代器
移动语义：提高容器操作效率
结构化绑定：简化元素访问（C++17）

九、常见误区解答

Q：为什么vector中间插入比list慢？ A：vector采用连续内存存储，中间插入需要移动后续所有元素，时间复杂度O(n)；而list通过指针调整即可完成，时间复杂度O(1)

Q：何时应该选择forward_list？ A：当只需要单向遍历且内存敏感时，forward_list比list节省约25%内存，但失去双向遍历能力

Q：array与原生数组的区别？ A：array提供边界检查（at()方法）、标准容器接口和自动内存管理，比原生数组更安全易用

十、总结

本文详细介绍了 C++ 中的顺序容器，包括 vector、deque、list、forward_list 和 array。每个容器都有其特点和适用场景，在实际编程中，需要根据具体的需求来选择合适的容器。通过合理使用顺序容器，可以提高程序的性能和可维护性。

十一、参考资料

《C++ Primer（第 5 版）》这本书是 C++ 领域的经典之作，对 C++ 的基础语法和高级特性都有深入讲解。
《Effective C++（第 3 版）》书中包含了很多 C++ 编程的实用建议和最佳实践。
《C++ Templates: The Complete Guide（第 2 版）》该书聚焦于 C++ 模板编程，而using声明在模板编程中有着重要应用，如定义模板类型别名等。
C++ 官方标准文档：C++ 标准文档是最权威的参考资料，可以查阅最新的 C++ 标准（如 C++11、C++14、C++17、C++20 等）文档。例如，ISO/IEC 14882:2020 是 C++20 标准的文档，可从相关渠道获取其详细内容。
cppreference.com：这是一个非常全面的 C++ 在线参考网站，提供了详细的 C++ 语言和标准库文档。
LearnCpp.com：该网站提供了系统的 C++ 教程，配有丰富的示例代码和清晰的解释，适合初学者学习和理解相关知识。
《Effective STL》Scott Meyers
CppReference容器文档
开源项目STL源码分析

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数组

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度