前言

前面我们讲了C语言的基础知识，也了解了一些数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点——STL（vector）。下面话不多说坐稳扶好咱们要开车了😍

一、vector简介

1. 概念

std::vector是C++标准库中的一个容器类模板，是一种动态数组，可以存储相同类型的元素。它提供了动态调整大小、快速随机访问、插入和删除元素的操作。（vector的官方介绍链接）

2. 特点

1. 动态调整大小：std::vector会自动处理内存的分配和释放，可以根据需要在运行时动态调整容器的大小。当添加或删除元素时，std::vector会自动调整内部数组的大小以适应新的元素数量。

2. 快速随机访问：std::vector中的元素在内存中是连续存储的，因此可以通过下标或迭代器快速访问任意位置的元素。具有常数时间复杂度的随机访问使得std::vector非常适合需要频繁访问元素的场景。

3. 动态增长和收缩：当需要添加更多元素时，std::vector会自动扩展内部数组的大小，以容纳新的元素；而当需要删除元素时，std::vector会自动收缩内部数组的大小，以减少内存的使用。

4. 插入和删除操作：std::vector提供了插入和删除元素的方法。可以在指定位置插入一个或多个元素，也可以通过下标或迭代器删除指定位置的元素。

5. 元素的访问和遍历：可以通过下标或迭代器访问指定位置的元素。使用迭代器可以对std::vector进行遍历，包括正向和反向遍历。

6. 其他功能：除了上述基本功能外，std::vector还提供了其他一些有用的功能，如获取容器的大小、判断容器是否为空、重新分配容器的大小、与其他容器进行交换、排序等。

注意：使用std::vector需要包含头文件<vector>，命名空间为 std。std::vector是一个模板类，需要指定存储的元素类型，如std::vector<int>表示存储int类型的元素。

二、vector的使用

1.vector 构造函数

std::vector 提供了多个构造函数来创建和初始化向量，这些构造函数使得创建 std::vector 对象变得灵活，并提供了多种初始化向量的方式。选择适当的构造函数取决于具体的需求和数据源。

1. 默认构造函数

vector()

该构造函数创建一个空的 std::vector 对象。

2. 大小和初始值构造函数

vector(size_type count, const T& value = T())

该构造函数创建一个包含 count 个元素的 std::vector 对象，并用 value 的值初始化每个元素。如果未提供 value 的值，则使用类型 T 的默认构造函数进行初始化。

3. 范围构造函数

template <class InputIt>
vector(InputIt first, InputIt last)

该构造函数使用迭代器范围 [first, last) 中的元素创建一个 std::vector 对象。可以通过传递两个迭代器来指定范围，从而将其他容器中的元素复制到新的 std::vector 对象中。

4. 拷贝构造函数

vector(const vector& other)

该构造函数创建一个与 other 相同的 std::vector 对象，复制 other 中的所有元素。

5. 移动构造函数

vector(vector&& other)

该构造函数使用 other 的资源来创建一个新的 std::vector 对象，同时将 other 置为空。

6. 初始化列表构造函数

vector(std::initializer_list<T> init)

该构造函数使用花括号 {} 内的元素列表初始化 std::vector 对象。可以通过传递元素的列表来创建和初始化向量。

下面是所有使用构造函数创建 std::vector 对象的代码：

#include <vector>
#include <iostream>

int main() {
    // 默认构造函数
    std::vector<int> numbers;  // 空的向量

    // 大小和初始值构造函数[10, 10, 10, 10, 10]
    std::vector<int> numbers1(5, 10); 

    // 范围构造函数[1, 2, 3, 4, 5]
    std::vector<int> numbers2 = {1, 2, 3, 4, 5};  
    
    // 拷贝构造函数[1, 2, 3, 4, 5]
    std::vector<int> numbers3 = numbers2;  

    // 移动构造函数[1, 2, 3, 4, 5]
    std::vector<int> numbers4 = std::move(numbers2);  
    // numbers2 现在为空

    // 初始化列表构造函数[1, 2, 3, 4, 5]
    std::vector<int> numbers5 {1, 2, 3, 4, 5}; 

    // 输出向量内的元素
    for (const auto& num : numbers5) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. vector 空间增长问题

在 std::vector 中，空间增长（space growth）是指在向向量添加元素时，当容量不足时，向量自动增加内部存储空间的过程。这是为了确保向量能够容纳更多的元素，并减少频繁的内存重新分配操作。

1. 容量和大小

• 大小（size）：指的是 std::vector 中当前拥有的元素个数。

• 容量（capacity）：指的是 std::vector 内部存储空间的大小，即它可以容纳的元素个数。

2. 空间分配器（allocator）

std::vector 使用内部的空间分配器来动态管理存储空间。默认情况下，它使用标准全局的 operator new 和 operator delete 来分配和释放内存。也可以提供自定义的空间分配器来满足特定的需求。

3. 容量增长策略

std::vector 使用一种策略来决定何时以及如何增加内部存储空间的容量：

• 固定增长因子：许多实现会以固定的因子（例如2倍）来增加容量。这意味着每次增长时，容量都会以固定比例增加。这种策略通常具有较好的性能，但可能会占用更多的内存。

• 线性增长：某些实现会以固定的大小（如每次增加n个元素）增加容量。这可以提供更节省内存的方式，但在某些情况下可能导致频繁的重新分配操作。

容量增长过程通常包括以下步骤：

1. std::vector 判断当前的容量是否能够容纳新的元素。如果容量不足，进入空间增长阶段。

2. 分配新的更大的内部存储空间。这通常涉及到申请更大的内存块，并将已有的元素从旧的内存块拷贝到新的内存块中。

3. 释放旧的内部存储空间，回收内存资源。

4. 更新 std::vector 的容量信息，以反映新的内部存储空间大小。

空间增长的频率取决于添加元素的数量和容器的策略。过于频繁的空间增长可能会导致性能下降，因为内存重新分配和元素拷贝都是开销较大的操作。因此，预先分配一定容量的空间（使用 std::vector::reserve()）可以减少空间增长的次数，提高性能。

注意：自定义类型的元素在空间增长过程中会涉及到拷贝构造函数和析构函数的调用。确保自定义类型的正确实现这些特殊函数是非常重要的，以避免潜在的内存错误和资源泄漏。

⭕resize 和 reserve 函数

在 C++ 的 std::vector 中，reserve() 和 resize() 是两个用于管理向量容量和大小的成员函数。

1. reserve(n)

reserve() 函数用于预留至少能够容纳 n 个元素的内部存储空间，而不会改变向量的大小。这样做是为了避免频繁的重新分配和拷贝操作，提高性能。

调用 reserve(n) 后，如果 n 大于当前容量（capacity()），则向量会重新分配新的内部存储空间，容量会大于等于 n。如果 n 小于或等于当前容量，则不会有任何变化。

void reserve(size_type n);

2. resize(n, value)

resize() 函数用于改变向量的大小，并根据需要添加或删除元素。

• 如果 n 小于当前大小（size()），则会删除超出 n 个元素后的元素，向量的大小变为 n。
• 如果 n 大于当前大小，则会添加足够的元素，以便向量的大小变为 n。添加的元素将使用 value 进行初始化。

void resize(size_type n);
void resize(size_type n, const value_type& value);

注意：如果增加了向量的大小，新添加的元素（在当前大小和 n 之间）将通过拷贝构造函数进行初始化。如果存储的是自定义类型的元素，确保该类型的拷贝构造函数正确实现是很重要的。

以下是 reserve() 和 resize() 的示例代码：

#include <iostream>
#include <vector>

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

    numbers.reserve(10);  // 预留至少能容纳 10 个元素的空间

    std::cout << "Capacity: " << numbers.capacity() << std::endl;  // 输出容量

    numbers.resize(5);  // 更改大小为 5
    std::cout << "Size after resize: " << numbers.size() << std::endl;  // 输出大小

    numbers.resize(8, 42);  // 更改大小为 8，并用值 42 进行初始化
    std::cout << "Size after resize 2: " << numbers.size() << std::endl;  // 输出大小

    return 0;
}

总的来说，reserve() 用于预留足够的存储空间以容纳更多的元素，而 resize() 用于改变向量的大小并根据需要添加或删除元素。这两个函数可以帮助我们灵活地管理 std::vector 的容量和大小，以满足不同的需求。

3. vector 增删查改

当使用 C++ 的 std::vector 容器时，可以使用下面的方法来执行向向量中增加数据、删除数据、查找数据和修改数据的操作。

1. 增加数据

向 std::vector 中增加数据可以使用 push_back() 函数将元素添加到向量的末尾。

void push_back(const T& value);

使用示例：

#include <iostream>
#include <vector>

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

    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. 删除数据

可以使用 erase() 函数从向量中删除数据。它接受一个迭代器参数，指示要删除的元素位置。

iterator erase(iterator position);

使用示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    numbers.erase(numbers.begin() + 1);  // 删除索引为 1 的元素

    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 查找数据

可以使用 std::find() 算法函数在向量中查找特定的元素。该函数接受两个迭代器参数，指示要搜索的范围，以及要查找的值。它返回指向找到的元素的迭代器，如果未找到，则返回指向容器末尾的迭代器。

iterator find(iterator first, iterator last, const T& value);

使用示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    auto it = std::find(numbers.begin(), numbers.end(), 20);
    if (it != numbers.end()) {
        std::cout << "Element found at index: " << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

4. 修改数据

可以通过迭代器来访问和修改 std::vector 中的元素。通过修改迭代器指向的元素来实现数据的修改。

使用示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    auto it = numbers.begin();
    ++it;
    *it = 25;  // 修改元素值

    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

⭕operator[] 函数

还可以使用 operator[] 运算符来访问 std::vector 中的元素并进行修改。operator[] 函数的官方链接

operator[] 运算符允许通过索引来访问向量中的元素，并提供了对元素的非常快速的随机访问。索引从 0 开始，依次增加。

使用示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    std::cout << numbers[0] << std::endl;  // 访问索引为 0 的元素

    numbers[1] = 25;  // 修改索引为 1 的元素的值

    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

需要注意以下几点：

1. 使用 operator[] 访问索引超出向量范围的元素是未定义行为，因此要确保索引值在有效范围内。

2. 如果要对不存在的元素使用 operator[] 进行访问，它将创建一个新元素并分配给该索引位置。因此，在使用 operator[] 之前，通常需要确保向量具有足够的大小。

3. operator[] 返回对索引位置的引用，因此可以通过返回的引用进行修改和赋值操作。

operator[] 运算符是一种快速访问和修改 std::vector 中元素的便捷方式，它提供了类似于数组的索引操作。

三、迭代器失效

在 std::vector 中，迭代器失效指的是当在向量进行插入或删除操作后，原本指向向量元素的迭代器可能会失效，即不能再安全地使用。

迭代器失效的问题存在于插入和删除操作中，因为这些操作可能会导致向量重新分配内存，使得原来的迭代器指向的位置变得无效。下面是常见的迭代器失效情况：

1. 在插入或删除一个元素后，迭代器失效

当向向量中插入或删除元素时，迭代器可能会失效。插入操作可能导致内部存储重新分配，而删除操作可能使元素位置向前移动。这会导致之前的迭代器指向的位置变得无效。

std::vector<int> numbers = {10, 20, 30};
auto it = numbers.begin();

numbers.insert(it + 1, 15);  // 在索引为 1 的位置插入元素

// 在插入之后，迭代器 it 可能失效，不能再使用

2. 使用被删除元素的迭代器，迭代器失效

当使用被删除元素的迭代器继续访问向量时，迭代器可能会失效。因为删除元素会导致元素位置的变动，原本的迭代器指向的位置可能已经被其他元素占据。

std::vector<int> numbers = {10, 20, 30};
auto it = numbers.begin();

numbers.erase(it);  // 删除首个元素

// 在删除之后，迭代器 it 变成无效的迭代器，不能再使用

为了避免迭代器失效问题，可以采取以下几种方法：

• 使用索引替代迭代器：使用基于索引的访问方式，而不是依赖迭代器。

• 在插入或删除元素后重新获取迭代器：在插入或删除操作后，重新获取迭代器，而不是继续使用之前的迭代器。

std::vector<int> numbers = {10, 20, 30};
auto it = numbers.begin();

numbers.insert(it + 1, 15);
it = numbers.begin();  // 插入后重新获取迭代器

numbers.erase(it);
it = numbers.begin();  // 删除后重新获取迭代器

• 使用算法和函数：使用标准库提供的算法和函数，而不是手动操作迭代器。这些函数会处理好迭代器失效的情况，例如使用 std::for_each 遍历向量。

std::vector<int> numbers = {10, 20, 30};
std::for_each(numbers.begin(), numbers.end(), [](int& num) {
    // 修改元素值
});

了解迭代器失效的情况，并采取适当的措施来避免迭代器失效问题，是在操作 std::vector 时需要注意的重要方面。

温馨提示

感谢您对博主文章的关注与支持！在阅读本篇文章的同时，我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章，可以点赞、评论和分享给您的同学，这将对我提供巨大的鼓励和支持。另外，我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！

再次感谢您的支持和关注。我们期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！