大话C++：第31篇 顺序容器

1 容器概述

C++标准模板库（STL）中的容器是用于存储集合数据结构的模板类。容器可以分为几个不同的类别，每种类别都有其特定的用途和特性。C++容器类别及其成员包括：

• 顺序容器：存储一序列的元素，可以进行随机访问。

  • vector：可变大小数组，支持快速随机访问。

  • deque（双端队列）：双端队列，支持快速的前端和后端插入和删除操作。

  • list：双向链表，支持高效的元素插入和删除操作。

• 关联容器：用于存储键值对，可以快速进行查找、添加和删除操作。

  • set：唯一值的集合，自动排序。

  • map：键值对的集合，键是唯一的，自动排序。

  • multiset：允许有重复值的集合。

  • multimap：允许键有多个值的映射。

• 无序容器（C++11引入）：基于哈希表的容器，提供平均恒定时间的查找、插入和删除操作。

  • unordered_set：无序的唯一值集合。

  • unordered_map：无序的键值对集合。

  • unordered_multiset：无序的允许重复值的集合。

  • unordered_multimap：无序的允许键有多个值的映射。

• 容器适配器：提供有限的或特定的接口以访问底层容器。

  • stack：后进先出（LIFO）的栈。

  • queue：先进先出（FIFO）的队列。

  • priority_queue：优先队列，元素按优先级排序

容器的选择取决于具体的使用场景。例如，如果需要随机访问元素，并且插入和删除操作主要在尾部进行，那么vector可能是一个好选择。如果需要在任何位置进行高效的插入和删除操作，但不需要随机访问，那么list可能更合适。而如果需要按键值快速查找、插入或删除元素，那么关联容器（如set、map等）可能是最佳选择。

注意，这些容器都是模板类，这意味着它们可以存储任何类型的元素（包括自定义类型），只要这些类型满足容器的要求（例如，对于排序容器，元素类型必须支持比较操作）。

2 迭代器

在C++中，迭代器（Iterator）是一种抽象概念，它允许程序员使用统一的方法遍历容器中的元素，而无需关心容器的具体实现细节。迭代器提供了一种方式来访问容器中的每个元素，使得容器的访问方式与数组类似，但同时提供了更多的功能和灵活性。

每种容器都定义了适合它的迭代器类型。例如，std::vector有正向迭代器（iterator）和常量正向迭代器（const_iterator），而std::list有双向迭代器（iterator）和常量双向迭代器（const_iterator）。

迭代器的基本操作包括：

• 解引用操作符（*）：用于获取迭代器当前指向的元素的值。

• 成员访问操作符（->）：用于访问迭代器当前指向的元素的成员。

• 前缀递增（++）和后缀递增（++）：将迭代器向前移动到下一个元素。

• 前缀递减（--）和后缀递减（--）：将迭代器向后移动到上一个元素。

• 相等和不等比较：可以比较两个迭代器是否相等或不等。

#include <vector>
#include <iostream>

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

    // 使用迭代器遍历 vector
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) 
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用基于范围的 for 循环（C++11引入）
    for (int num : vec) 
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3 顺序容器

3.1 vector

vector是C++标准模板库（STL）中的一种数据结构，它表示同一种类型的对象的集合，每个对象都有一个对应的整数索引值。可以把vector理解为动态数组，因为其大小是可以动态改变的，这一点与静态数组不同。同时，vector使用连续存储空间来存储元素，因此可以使用下标操作符像数组一样访问其元素，具有很高的效率。

在内部，vector使用了动态分配数组来存储元素。当新元素被插入时，且当前数组的空间不足以容纳新元素，vector会分配一个更大的数组，并将所有元素移到新的数组中。这个过程被称为重新分配，它相对耗时，因此vector的实现会尽量避免频繁进行重新分配。通常，vector会以对数增长的间隔大小来进行重新分配，以实现在尾部插入元素的时间复杂度为常数。

vector提供了许多成员函数来操作数组元素，管理存储空间等。常用的 std::vector 成员函数及其功能：

综合案例：使用std::vector来存储整数，并对其进行一系列的操作，包括：创建vector、添加元素、访问元素、修改元素、遍历元素、删除元素以及清空vector。

#include <iostream>
#include <vector>

int main()
{
    // 创建vector容器
    std::vector<int32_t> vec;

    // 容器中的元素长度
    std::cout << "当前容器中元素个数：" << vec.size() << std::endl;
    // 容器的容量
    std::cout << "当前容器中元素个数：" << vec.capacity() << std::endl; 

    // 往容器中插入三个元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 遍历容器
    // 采用迭代器方式
    std::vector<int32_t>::iterator iter = vec.begin();
    for (; iter != vec.end(); ++iter)
    {
        // 利用迭代器的解引用方式访问容器中当前位置的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // C++11遍历方式
    for (int32_t num : vec)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 访问第2个元素
    // 1.类似于数组下标[]
    std::cout << "容器中第2个元素的值：" << vec[1] << std::endl;
    // 2.at成员函数
    std::cout << "容器中第2个元素的值：" << vec.at(1) << std::endl;

    // 插入元素
    // 向第2个位置插入元素40
    vec.insert(vec.begin() + 1, 40);
    iter = vec.begin();
    for (; iter != vec.end(); ++iter)
    {
        // 利用迭代器的解引用方式访问容器中当前位置的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 删除元素
    vec.erase(vec.begin());
    iter = vec.begin();
    for (; iter != vec.end(); ++iter)
    {
        // 利用迭代器的解引用方式访问容器中当前位置的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 容器中的元素长度
    std::cout << "当前容器中元素个数：" << vec.size() << std::endl;
    // 容器的容量
    std::cout << "当前容器中元素个数：" << vec.capacity() << std::endl; 

    // 清空容器
    vec.clear();

    return 0; 
}

3.2 list

list是C++的一个序列容器，它可以在常数范围内（即O(1)时间复杂度）在任意位置进行插入和删除操作。这是由于其底层数据结构为双向链表，每个元素存储在互不相关的独立节点中，节点之间通过指针相互连接。这种设计使得list的元素可以存储在非相邻的内存中，通过指向前一个元素的指针和指向后一个元素的指针来关联不同元素。

但是，由于list的这种特性，它不能直接通过位置（下标）来直接访问元素，这使得在需要随机访问元素的场景下，list的效率可能不如vector。然而，在需要频繁插入和删除元素的场景下，list的高效性就显得尤为重要。

std::list 成员函数及其功能：

综合案例，代码示例：

#include <iostream>
#include <list>

int main()
{
    // 创建list对象
    std::list<int32_t> list;
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    list.push_front(40);

    // 正向遍历
    for (std::list<int>::iterator iter = list.begin(); iter != list.end(); ++iter)
    {
        // 解引用当前迭代器所指向的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 逆向遍历
    for (std::list<int>::reverse_iterator iter = list.rbegin(); iter != list.rend(); ++iter)
    {
        // 解引用当前迭代器所指向的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 插入数据
    std::list<int>::iterator curIter = list.begin();
    ++curIter;
    list.insert(curIter, 50);
    // 正向遍历
    for (std::list<int>::iterator iter = list.begin(); iter != list.end(); ++iter)
    {
        // 解引用当前迭代器所指向的元素
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 删除元素   
    ++curIter;
    list.erase(curIter);

    // 获取list长度
    std::cout << "list当前长度=" << list.size() << std::endl;
    // 获取list最大长度
    std::cout << "list最大长度=" << list.max_size() << std::endl;

    // 容器清理
    list.clear();

    return 0; 
}

3.3 deque

std::deque ，也被称为双端队列，是一种具有队列和栈性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

std::deque 具有以下特点：

• std::deque 是由一段一段的定量连续空间构成，第一个区块朝某个方向扩展，最后一个区块朝相反方向扩展。这种结构使得std::deque 在首尾两端都能快速的安插、删除元素。

• std::deque 在内部管理这些分段的定量连续空间，维护其整体连续的假象，并提供随机存取的接口。因此，尽管在需要安插、删除元素时，std::deque 的内部结构会多一个间接过程，操作元素的效率会比vector低一些，但是它依然支持随机存取功能。

• 在实际使用中，std::deque 还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。

• 如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。

std::deque 成员函数及其功能：

综合案例，代码示例：

#include <iostream>
#include <deque>

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

    // 向 deque 中添加元素
    numbers.push_back(3);
    numbers.push_back(1);
    numbers.push_front(2); // 在开头插入元素
    numbers.push_front(0);

    // 访问 deque 中的元素
    std::cout << "First element: " << numbers.front() << std::endl;
    std::cout << "Last element: " << numbers.back() << std::endl;

    // 遍历 deque 并输出元素
    std::cout << "Deque elements in forward order:" << std::endl;
    for (std::deque<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用反向迭代器遍历 deque
    std::cout << "Deque elements in reverse order:" << std::endl;
    for (std::deque<int>::const_reverse_iterator rit = numbers.rbegin(); rit != numbers.rend(); ++rit) 
    {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    // 在指定位置插入元素
    std::deque<int>::iterator it = numbers.begin();
    std::advance(it, 2); // 前进到第三个元素的位置
    numbers.insert(it, 9);

    // 删除元素
    it = numbers.begin();
    std::advance(it, 1); // 前进到第二个元素的位置
    numbers.erase(it);

    // 修改元素
    it = numbers.begin();
    std::advance(it, 2); // 前进到第三个元素的位置
    *it = 7; // 修改第三个元素的值

    // 输出修改后的 deque
    std::cout << "Modified deque:" << std::endl;
    for (int num : numbers) 
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 检查 deque 是否为空
    if (!numbers.empty()) 
    {
        std::cout << "Deque is not empty." << std::endl;
    }

    // 获取 deque 的大小
    std::cout << "Size of the deque: " << numbers.size() << std::endl;

    // 调整 deque 的大小
    numbers.resize(5); // 如果 deque 的大小大于 5，则删除多余的元素；如果小于 5，则添加元素直到大小为 5

    // 输出调整大小后的 deque
    std::cout << "Resized deque (with default-initialized values):" << std::endl;
    for (int num : numbers) 
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}