一文读懂 c++ 容器

发布时间:2024年01月22日

容器根据不同的使用场景和需求,有序序列、无序集合以及专门的适配器等各种形式。了解如何根据场景选择合适的容器并使用它们,是写出高效可读性强的 C++ 代码的关键所在,C++ 标准库提供了一系列标准容器来存储和操作数据集合。这些容器被设计为通用、高效且易于使用。它们都是模板类,意味着可以用来存储任何类型的对象! 接下来我们一起了解下关于容器的分类及使用。


接下来我们一起了解下关于容器的分类及使用。)

序列式容器

vector (向量)

动态数组
用于存储动态大小的数组,提供了快速的随机访问和数组型接口,并能够在运行时动态增长或收缩(尾部添加/删除操作)。

案例
#include <vector>
#include <iostream>

int main() {
   
#if 0
	std::vector<int> vec = {
   10, 20, 30};
#else
    // 初始化一个空的 vector
    std::vector<int> vec;
    // 添加元素至末尾
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
#endif
    // 访问元素
    std::cout << "First element: " << vec[0] << '\n'; // 使用下标操作符
    std::cout << "Second element: " << vec.at(1) << '\n'; // 使用 .at() 方法,带边界检查

    // 获取 vector 的大小
    std::cout << "The vector size is: " << vec.size() << '\n';

    // 遍历 vector
    for (size_t i = 0; i < vec.size(); ++i) {
   
        std::cout << vec[i] << ' ';
    }
    std::cout << '\n';

    // 使用迭代器遍历
    for (auto it = vec.begin(); it != vec.end(); ++it) {
   
        std::cout << *it << ' ';
    }
    std::cout << '\n';
    
    // 使用范围基于的 for 循环
    for (int num : vec) {
   
        std::cout << num << ' ';
    }
    std::cout << '\n';

    // 移除最后一个元素
    vec.pop_back();

    // 清空 vector
    vec.clear();
    
    return 0;
}
使用场景
  1. 当你需要一个可以动态改变大小的数组时: std::vector允许在运行时添加和删除元素。因此,如果数据集合的大小不是固定的,使用vector会非常方面。
  2. 当需要频繁访问元素(通过下标),而不需要在中间插入或删除元素时: std::vector提供了对其元素的快速随机访问(时间复杂度为O(1)),但在中间插入或删除操作会导致内部元素的移动,时间复杂度较高(平均为O(n))
  3. 当要求内存连续存储时: std::vector的所有元素都是在一个连续的内存块内存储的,这意味着可以获得数据局部性的优势,并且可以利用指针算术直接访问元素
  4. 在进行大量元素插入或移除操作时,通常在末端操作: 对于std::vector,在末尾添加(push_back())或移除(pop_back())元素效率最高,因为这些操作不需要移动除新增或移除元素之外的任何元素
总结

选择std::vector时应该注意的是,为了支持动态扩展,它可能会在内存中实现多次分配和复制。当vector容量不足以容纳更多元素时,它将进行重新分配,并将所有元素复制到新的内存地址。为了减少这种分配和复制的开销,如果知道大致所需的容量,可以使用reserve()方法预先分配足够的空间。

deque (双端队列)

双端动态数组
允许在容器的两端快速插入和删除对象。与 std::vector 不同的是,std::deque 支持在两端高效地添加或移除元素,非常适合用作队列或双端队列数据结构。

案例
#include <deque>
#include <iostream>

int main() {
   
#if 0
	std::deque<int> d = {
    10, 20 };
#else
    std::deque<int> d;
    // 在末尾添加元素
    d.push_back(10);
    d.push_back(20);
#endif
    // 在开头添加元素
    d.push_front(0);
    d.push_front(-10);

    // 访问元素
    std::cout << "First element: " << d.front() << '\n'; // 访问第一个元素
    std::cout << "Last element: " << d.back() << '\n';   // 访问最后一个元素

    // 下标访问元素(但不如 std::vector 那么快)
    std::cout << "Element at index 2: " << d[2] << '\n';

    // 使用迭代器遍历
    for (std::deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
   
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    // 使用范围基于的 for 循环
    for (int n : d) {
   
        std::cout << n << ' ';
    }
    std::cout << '\n';

    // 删除元素
    d.pop_front(); // 删除第一个元素
    d.pop_back();  // 删除最后一个元素

    return 0;
}
使用场景
  1. 两端操作: 如果你的应用场景需要在容器的两端添加或删除元素,使用 std::deque 是非常合适的。它在两端的插入和删除效率都很高
  2. 作为真正的双端队列(Double-ended queue): std::deque 可被用作队列(先进先出结构)或栈(先进后出结构),因为它提供了一致的接口来操作容器的两端
  3. 大量插入或删除: 如果需要在开始位置频繁插入或删除元素,std::vector 在这种情况下可能会有较差的性能,因为每次都需要移动元素。相比之下,std::deque 在两端插入和删除都有良好的性能
  4. 随机访问: 尽管 std::deque 也提供了随机访问能力,但由于其内部可能是块状链表结构,访问中间元素的效率可能不如 std::vector 那么快。因此,当你需要结合两端插入/删除和不太频繁的随机访问时,std::deque 是一个不错的选择
  5. 作为适配器的基础容器: C++ 标准库中的 stack 和 queue 容器适配器可以使用 std::deque 作为默认的底层容器,尽管 stack 通常用 std::deque(或 std::vector),而 queue 通常专门使用 std::deque,因为 stack 不需要两端操作,而 queue 需要
总结

总的来说,std::deque 在需要灵活操作两端元素的场合表现良好,特别是当你不确定需要的容量大小,并且插入或删除操作在元素集的两端比中间更频繁时,它是一个很好的选择。由于其对两端操作的优化,std::deque 在特定应用场景下,性能可能优于 std::vector。

list (链表)

双向链表
通过双向指针连接各个元素。与数组(如 std::vector)或块状连续存储(如 std::deque)不同,std::list 中的元素在内存中并不连续存放,这使得它非常适合在中间位置进行快速插入和删除操作。

案例
#include <list>
#include <iostream>

int main() {
   
    // 初始化列表
#if 0
    std::list<int> mylist = {
   2, 4, 6, 8};
#else
	std::list<int> mylist;
	mylist.push_front(6); 
文章来源:https://blog.csdn.net/weixin_43779276/article/details/135737334
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。