额滴笔记

Appearance

1. 容器 ​

1.1 容器的定义 ​

在C++中，容器的概念是指一种对象类型，它可以持有其他对象或指向其他对象的指针。这种对象类型在数据存储上提供了一种有效的方式来管理一组元素。容器在C++中通常是模板类的形式。

一般来说，容器内的元素都是相同类型的。即如果该容器内存放的是int类型的数据，那么其他所有的数据都是int类型的。如果你想存储多种类型的数据，建议使用结构体。

容器和数组的联系与区别 ​

  • 联系：数组在广义上可以被视为一种容器，因为它用于存储一组相同类型的元素。然而，在C++标准库的语境中，当我们提到"容器"，通常不包括数组。
  • 区别：
    • 创建和大小调整：
      • 数组：在创建数组时，必须指定其大小、且一旦创建，数组的大小就是固定的，不能动态改变。
      • 容器：容器的创建不需要预先指定大小，且其大小可以动态改变，根据需要添加或删除元素。
    • 存储方式：
      • 数组：数组在内存空间上是连续存储的，这意味着数组元素在内存中的位置是连续的，可以通过下标直接访问。
      • 容器：不同的容器有不同的存储方式。例如，std::vector 和 std::deque 是连续存储的，而 std::list 则是链式存储的。
    • 访问效率：
      • 数组：通过数组下标可以直接访问对应位置的元素，因此访问效率非常高。
      • 容器：连续存储的容器（如 std::vector 和 std::deque）也支持通过下标访问元素，但链式存储的容器（如 std::list）则不支持，需要遍历链表来查找元素。
    • 元素操作：
      • 数组：数组的元素操作通常包括赋值、读取等，但由于其连续，在数组中间位置插入或删除元素比较麻烦，需要移动其他元素。
      • 容器：容器提供了更丰富的元素操作。例如，std::list 支持在容器中间位置插入或删除元素，而无需移动其他元素。

为什么要学习和使用容器 ​

  • 动态内存管理：容器类负责动态分配和释放内存，简化了内存管理的复杂性。使用容器时，我们无需担心数组越界、内存泄漏等问题。
  • 自动扩展和收缩：一些容器类（如 std::vector）能够自动扩展和收缩，以适应存储元素数量的变化。这意味着我们可以将元素添加到容器中，而无需预先分配固定大小的内存空间。
  • 代码复用和可维护性：使用容器类可以提高代码的复用性和可维护性。由于容器类提供了通用的数据结构和操作接口，我们可以将更多的精力放在实现业务逻辑上。

1.2 容器的分类 ​

基于容器内部数据的组织方式、访问方式以及操作特性，容器大致可分为两大类：顺序（序列）容器和关联容器。

1.2.1 顺序容器 ​

顺序容器是将单一类型的元素聚集起来成为容器，并根据元素的插入位置来存储和访问这些元素。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。

顺序容器常用的方法主要包括以下方面：

  1. 构造函数：用于创建容器对象
  2. 赋值操作：使用赋值运算符（=）赋值
  3. 元素访问：通过下标运算符（[]）或迭代器访问
  4. 容器大小：使用 size() 获取元素数量
  5. 添加元素：push_back()、push_front() 等方法
  6. 删除元素：erase()、pop_back()、pop_front() 等方法
  7. 修改元素：通过下标或迭代器修改
  8. 关系运算符：比较两个容器
  9. 获取迭代器：begin() 和 end() 成员函数

1.2.1.1 array ​

在C++标准模板库（STL）中，array 是一个顺序容器，它封装了固定大小的数组，并提供了与自定义数组类似的接口，但增加了类型安全和一些额外的功能。

主要特点：

  • 固定大小
  • 随机访问
  • 类型安全
  • 空间连续

常用方法：

cpp
#include <array>
#include <iostream>

int main()
{
    // 构造函数
    std::array<int, 5> arr1; // 默认构造
    std::array<int, 5> arr2 = {1, 2, 3, 4, 5}; // 列表初始化
    
    // 元素访问
    arr2[2] = 10; // 通过下标访问
    std::cout << arr2.at(3) << std::endl; // 安全访问
    
    // 容量和大小
    std::cout << "Size: " << arr2.size() << std::endl;
    
    // 迭代器
    for(auto it = arr2.begin(); it != arr2.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 比较操作
    if(arr1 == arr2) {
        std::cout << "Arrays are equal" << std::endl;
    }
    
    return 0;
}

1.2.1.2 vector ​

在C++中，vector（向量）是一个顺序容器，它封装了动态大小数组的功能。

主要特性：

  1. 动态大小
  2. 连续内存
  3. 迭代器支持

常用方法：

cpp
#include <vector>
#include <iostream>

int main()
{
    // 创建vector
    std::vector<int> vec;
    
    // 添加元素
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    
    // 访问元素
    std::cout << "Element at 1: " << vec[1] << std::endl;
    
    // 大小和容量
    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    
    // 插入元素
    vec.insert(vec.begin() + 1, 10);
    
    // 删除元素
    vec.erase(vec.begin() + 2);
    
    // 遍历
    for(const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

1.2.1.3 deque ​

std::deque（双端队列）是C++标准库中的一个容器，它允许在序列的两端进行元素的快速插入和删除操作。

主要特点：

  • 快速的头部和尾部操作
  • 中间操作的效率优于vector
  • 随机访问
  • 内存使用不如vector紧凑

常用方法：

cpp
#include <deque>
#include <iostream>

int main()
{
    std::deque<int> dq;
    
    // 头部插入
    dq.push_front(1);
    dq.push_front(2);
    
    // 尾部插入
    dq.push_back(3);
    dq.push_back(4);
    
    // 访问元素
    std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << std::endl;
    
    // 中间插入
    dq.insert(dq.begin() + 2, 5);
    
    // 删除元素
    dq.pop_front();
    
    // 遍历
    for(const auto& elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

1.2.1.4 list ​

std::list 是 C++ 标准模板库（STL）中的一个容器，它表示一个双向链表。

主要特性：

  • 双向迭代
  • 任意位置插入删除高效
  • 非连续内存
  • 迭代器稳定性

常用方法：

cpp
#include <list>
#include <iostream>

int main()
{
    std::list<int> lst;
    
    // 添加元素
    lst.push_back(10);
    lst.push_back(20);
    lst.push_front(5);
    
    // 插入元素
    auto it = lst.begin();
    std::advance(it, 1);
    lst.insert(it, 15);
    
    // 删除元素
    lst.remove(10);
    
    // 反转和排序
    lst.reverse();
    lst.sort();
    
    // 遍历
    for(const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

总结 ​

容器特点适用场景
array固定大小，连续存储需要固定大小数组时
vector动态数组，连续存储需要随机访问，尾部操作频繁
deque双端队列，分块存储需要头尾操作频繁
list双向链表，非连续存储需要任意位置插入删除

根据具体需求选择合适的容器可以优化程序性能和内存使用。

知识如风，常伴吾身

Copyright © 2023-2025 Kgumo