---

📝前言

本节我们将学习vector容器的使用和操作，让我们学习起来吧！
库函数网址查询：https://legacy.cplusplus.com/reference/vector/vector/?kw=vector

🌠 熟悉vector

C++ 标准库中的 std::vector 是一个动态数组容器，能够存储并管理元素的集合。它提供了动态调整大小的能力，并且在底层维护一个连续的存储区域，使得元素可以通过索引进行快速访问。

std::vector 是一个类模板，它的定义如下：

template <class T, class Allocator = std::allocator<T>>
class vector;

模板参数

• T：向量中存储的元素的类型。
• Allocator：用于分配内存的分配器类型，默认是 std::allocator<T>。

就像数组一样，向量对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样高效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。

在内部，向量使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组才能增大大小，这意味着分配一个新数组并将所有元素移动到该数组。就处理时间而言，这是一项相对昂贵的任务，因此，每次将元素添加到容器时，向量都不会重新分配。

相反，矢量容器可能会分配一些额外的存储来适应可能的增长，因此容器的实际容量可能大于包含其元素（即其大小）严格需要的存储。库可以实施不同的增长策略，以平衡内存使用和重新分配之间的平衡，但无论如何，重新分配应该只在大小的对数增长间隔下发生，以便在向量末尾插入单个元素时可以提供摊销的恒定时间复杂度（参见push_back）。

因此，与数组相比，向量消耗更多的内存，以换取以有效的方式管理存储和动态增长的能力。

与其他动态序列容器（deques、lists 和 forward_lists）相比，向量非常有效地访问其元素（就像数组一样），并且相对有效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他操作差，并且迭代器和引用的一致性低于列表和forward_lists。

🌉使用vector

成员类型	定义
value_type	第一个模板参数
allocator_type	第二个模板参数 （Alloc)
size_type	一个无符号的整数类型，可以表示 difference_type 的任何非负值

🌠构造函数

std::vector 的四种不同构造函数分别是：

1. 默认构造函数

explicit vector (const allocator_type& alloc = allocator_type());

这个构造函数创建一个空的 std::vector，allocator_type 是用来分配内存的分配器类型，默认使用 std::allocator<T>，构造函数是 explicit 的，这意味着它不能进行隐式转换或复制初始化。

示例：

std::vector<int> v1; // 使用默认分配器创建一个空的 vector
std::vector<int> v2(std::allocator<int>()); // 使用指定的分配器创建一个空的 vector

2. 填充构造函数

explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());

这个构造函数创建一个包含 n 个 val 值的 std::vector， size_type 是一个无符号整数类型，通常是 std::size_t， value_type 是存储在 std::vector 中的元素的类型， allocator_type 是分配器类型，默认值为 std::allocator<T>。

示例：

std::vector<int> v1(10); // 创建一个包含 10 个默认值（0）的 vector
std::vector<int> v2(10, 5); // 创建一个包含 10 个值为 5 的 vector

3. 范围构造函数

template <class InputIterator>
vector (InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type());

这个构造函数使用范围 [first, last) 中的元素创建 std::vector，InputIterator 是输入迭代器类型，可以是指向数组的指针、其他容器的迭代器等。

示例：

int arr[] = {1, 2, 3, 4, 5};
std::vector<int> v1(arr, arr + 5); // 使用数组中的元素创建 vector
std::list<int> lst = {1, 2, 3, 4, 5};
std::vector<int> v2(lst.begin(), lst.end()); // 使用 list 中的元素创建 vector

4. 复制构造函数

vector (const vector& x);

这个构造函数使用另一个 std::vector x 的内容创建一个新的 std::vector，它会复制 x 中所有的元素，并且新创建的 std::vector 会有与 x 相同的大小和容量。

示例：

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2(v1); // 使用 v1 中的元素创建 v2

综合测试代码：

void test_vector07()
{
    // 默认构造函数
    vector<int>  v1;
    // 遍历 v1 并输出其中的元素,由于 v1 是空的,所以没有任何输出
    for (const auto& e : v1)
    {
        cout << e;
    }
    cout << endl;

    // 填充构造函数
    vector<int> v2(10);
    // 遍历 v2 并输出其中的元素,输出为 "0000000000"
    for (const auto& e : v2)
    {
        cout << e;
    }
    cout << endl;

    // 填充构造函数(带初始值)
    vector<int> v3(10, 3);
    // 遍历 v3 并输出其中的元素,输出为 "3333333333"
    for (const auto& e : v3)
    {
        cout << e;
    }
    cout << endl;

    // 复制构造函数
    vector<int> v5 = { 1, 2, 3, 4, 5 };
    vector<int> v6(v5);
    // 遍历 v5 并输出其中的元素,输出为 "12345"
    for (const auto& e : v5)
    {
        cout << e;
    }
    cout << endl;

    // 范围构造函数
    vector<int> v4(v5.begin() + 1, v5.end() - 2);
    // 遍历 v4 并输出其中的元素,输出为 "23"
    for (const auto& e : v4)
    {
        cout << e;
    }
    cout << endl;
}

🌉vector遍历

🌠operator[]

void test_vector08()
{
	std::vector<int> numbers = { 10, 20, 30, 40, 50 };

	// 非 const 访问
	numbers[1] = 25; // 修改第二个元素
	std::cout << "numbers[1]: " << numbers[1] << std::endl; // 输出：25

	// const 访问
	const std::vector<int> const_numbers = { 100, 200, 300, 400, 500 };
	std::cout << "const_numbers[2]: " << const_numbers[2] << std::endl; // 输出：300
	// const_numbers[2] = 350; // 错误：不能修改常量向量
}

🌉迭代器

迭代器基本使用方法大致相同，这里讲解基础的两个使用：

1. begin 函数：
   

   • 作用： 返回指向容器开头的迭代器。
   • 非 const 版本：

     iterator begin();
     

     • 返回类型： iterator，这是一个指向容器第一个元素的迭代器。
     • 用途： 可以用于遍历和修改容器中的元素。
   • const 版本：

     const_iterator begin() const;
     

     • 返回类型： const_iterator，这是一个指向容器第一个元素的常量迭代器。
     • 用途： 可以用于遍历但不能修改容器中的元素。

2. end 函数：
   

   • 作用： 返回指向容器末尾的迭代器。
   • 非 const 版本：

     iterator end();
     

     • 返回类型： iterator，这是一个指向容器末尾（即最后一个元素的下一个位置）的迭代器。
     • 用途： 通常用于标记迭代的结束。
   • const 版本：

     const_iterator end() const;
     

     • 返回类型： const_iterator，这是一个指向容器末尾的常量迭代器。
     • 用途： 通常用于标记迭代的结束，不能用于修改元素。

例子：

#include <vector>
#include <iostream>

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

    // 非 const 迭代器遍历
    std::cout << "使用非 const 迭代器遍历和修改向量元素：" << std::endl;
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        *it *= 2; // 将每个元素乘以 2
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // const 迭代器遍历
    std::cout << "使用 const 迭代器遍历向量元素：" << std::endl;
    const std::vector<int> const_vec = {10, 20, 30, 40, 50};
    for (std::vector<int>::const_iterator it = const_vec.begin(); it != const_vec.end(); ++it) {
        std::cout << *it << " "; // 只读访问
    }
    std::cout << std::endl;

    return 0;
}

🌠Capacity容量操作

🌉 size()

函数定义：

size_type size() const;

示例

#include <vector>
#include <iostream>

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

    // 获取向量的大小
    std::vector<int>::size_type vec_size = vec.size();
    std::cout << "向量的大小是：" << vec_size << std::endl;
    return 0;
}

输出：

5

🌉 capacity()

函数定义：

size_type capacity() const;

探索capaccity()的扩容机制

// 测试vector的默认扩容机制
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}	

vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容

making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141

g++运行结果：linux下使用的STL基本是按照2倍方式扩容

making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够 就可以避免边插入边扩容导致效率低下的问题了

void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

小结：capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

🌉resize()

resize 成员函数用于调整向量的大小。根据新大小，可以增加或减少向量中的元素。如果新大小大于当前大小，新的元素将被添加到向量的末尾。如果新大小小于当前大小，向量将被截断。

void test_vector09()
{
	vector<int> vec = { 1, 2, 3, 4, 5 };

	// 调整大小到 8，不指定新元素的值
	vec.resize(8);
	cout << "调整大小到 8，不指定新元素的值：" << endl;
	for (size_t i = 0; i < vec.size(); ++i) 
	{
		cout << "vec[" << i << "] = " << vec[i] << endl;
	}

	// 调整大小到 3（截断向量）
	vec.resize(3);
	cout << "调整大小到 3（截断向量）：" << endl;
	for (size_t i = 0; i < vec.size(); ++i) 
	{
		std::cout << "vec[" << i << "] = " << vec[i] << std::endl;
	}

	// 调整大小到 6，并指定新元素的值为 10
	vec.resize(6, 10);
	cout << "调整大小到 6，并指定新元素的值为 10：" << endl;
	for (size_t i = 0; i < vec.size(); ++i) 
	{
		cout << "vec[" << i << "] = " << vec[i] << endl;
	}


}

🌉reserve()

std::vector::reserve 是一个成员函数，用于请求将向量的容量增加到至少指定的大小。这与 resize 不同，reserve 只改变容量（即预分配的存储空间），而不改变实际存储的元素数量。通过预先分配足够的存储空间，可以避免频繁的重新分配，从而提高性能，特别是在知道将要存储的大量元素时。

函数定义：

void reserve(size_type new_cap);
 new_cap:是请求的新容量值。

如果 new_cap 大于当前容量，向量的容量将增加到至少 new_cap。如果 new_cap 小于或等于当前容量，则容量保持不变。

• 无返回值： 该函数没有返回值。

使用示例：

#include <vector>
#include <iostream>

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

    std::cout << "初始容量：" << vec.capacity() << std::endl;

    // 预分配容量
    vec.reserve(10);
    std::cout << "调用 reserve(10) 后的容量：" << vec.capacity() << std::endl;

    // 添加元素
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    std::cout << "添加三个元素后的容量：" << vec.capacity() << std::endl;

    // 再次预分配容量
    vec.reserve(20);
    std::cout << "调用 reserve(20) 后的容量：" << vec.capacity() << std::endl;

    return 0;
}

输出：

初始容量：0
调用 reserve(10) 后的容量：10
添加三个元素后的容量：10
调用 reserve(20) 后的容量：20

使用注意事项：

• 效率： 使用 reserve 可以提高性能，避免在添加大量元素时频繁重新分配内存。
• 内存增长策略： 如果没有调用 reserve，向量在需要更多容量时通常会自动增长，大多数实现使用倍增策略（即每次需要更多空间时，容量翻倍）。
• 容量和大小的区别： 容量（capacity）是向量在重新分配前可以存储的元素数量，而大小（size）是向量当前实际存储的元素数量。

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size

🌠 常用操作符

🌉 push_back

#include <iostream>
#include <vector>

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

    // 添加整数元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    // 打印向量的内容
    std::cout << "Vector contents: ";
    for (int i : v) 
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

🌉pop_back

std::vector<int> v = { 1, 2, 3, 4, 5 };

// 在删除最后一个元素之前打印向量的内容
std::cout << "删除前向量的内容: ";
for (int i : v) 
{
	std::cout << i << " ";
}
std::cout << std::endl;

// 删除向量的最后一个元素
v.pop_back();

// 在删除最后一个元素之后打印向量的内容
std::cout << "删除后向量的内容: ";
for (int i : v) 
{
	std::cout << i << " ";
}
std::cout << std::endl;

🌉 find

注意std::find 是 C++ 标准库中 <algorithm> 头文件中的一个函数模板,而不是vector的find，vector中没有find，用于在给定范围内查找指定的值。

函数原型如下:

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
其中:
- `InputIterator first` 和 `InputIterator last` 表示查找范围的起始和结束迭代器。
- `const T& val` 表示要查找的值。

返回一个迭代器,指向范围内第一个等于 val 的元素。如果在给定范围内没有找到该值,则返回 last 迭代器。

示例:

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

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

    // 查找值为 3 的元素
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) 
    {
        std::cout << "Found value: " << *it << std::endl;
    } else 
    {
        std::cout << "Value not found." << std::endl;
    }

    // 查找值为 10 的元素
    it = std::find(v.begin(), v.end(), 10);
    if (it != v.end()) 
    {
        std::cout << "Found value: " << *it << std::endl;
    } else 
    {
        std::cout << "Value not found." << std::endl;
    }

    return 0;
}

输出:

Found value: 3
Value not found.

std::find 函数的时间复杂度为 O(n),其中 n 是给定范围的大小。它会顺序遍历整个范围,直到找到目标元素或者到达范围末尾。因此,它适用于小型数据集,但对于大型数据集可能性能较差。在这种情况下,可以考虑使用更高效的算法,如 std::binary_search 或者基于哈希表的查找。

🌉 insert

std::vector::insert 是 C++ 标准库中 <vector> 头文件中的一个成员函数,用于在给定位置插入元素。

它有三种重载形式:

1. 单元素插入:

   iterator insert (iterator position, const value_type& val);
   

   该形式在迭代器 position 指向的位置插入一个值为 val 的元素,并返回指向新插入元素的迭代器。

2. 区间插入:

   void insert (iterator position, size_type n, const value_type& val);
   

   该形式在迭代器 position 指向的位置插入 n 个值为 val 的元素。

3. 范围插入:

   template <class InputIterator>
   void insert (iterator position, InputIterator first, InputIterator last);
   

   该形式在迭代器 position 指向的位置插入 [first, last) 范围内的元素。

需要注意的是,在调用 insert 函数时,如果 vector 的大小需要扩张以容纳新的元素,则会自动分配新的内存空间。这可能会导致迭代器、指针和引用失效,因此在使用这些元素时需要格外小心。(这里我们在学习vector的模拟实现中可以看出)

下面是一个示例:

#include <iostream>
#include <vector>

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

    // 插入单个元素
    auto it = v.insert(v.begin() + 2, 10);
    std::cout << "Inserted at position: " << it - v.begin() << ", value: " << *it << std::endl;

    // 插入多个元素
    v.insert(v.end(), 3, 20);
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 插入范围
    std::vector<int> other = {30, 40, 50};
    v.insert(v.begin(), other.begin(), other.end());
    for (int x : v)
     {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出:

Inserted at position: 2, value: 10
1 2 10 3 4 5 20 20 20 
30 40 50 1 2 10 3 4 5 20 20 20

🌉 erase

std::vector::erase 是 C++ 标准库中 <vector> 头文件中的一个成员函数,用于删除 vector 中的元素。它有两种重载形式:

1. 单个元素删除:

   iterator erase (iterator position);
   

   该形式删除迭代器 position 指向的元素,并返回指向被删除元素之后的下一个元素的迭代器。

2. 范围删除:

   iterator erase (iterator first, iterator last);
   

   该形式删除 [first, last) 范围内的所有元素,并返回指向被删除元素之后的下一个元素的迭代器。

需要注意的是,在调用 erase 函数时,如果 vector 的大小需要收缩以适应被删除的元素,则会自动缩小内存空间。这可能会导致迭代器、指针和引用失效,因此在使用这些元素时需要格外小心(这就是她为什么要有返回值，返回值是iterator)。

下面是一个示例:

#include <iostream>
#include <vector>

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

    // 删除单个元素
    auto it = v.erase(v.begin() + 2);
    std::cout << "Erased element at position: " << it - v.begin() << ", value: " << *it << std::endl;

    // 删除范围
    it = v.erase(v.begin() + 1, v.begin() + 3);
    std::cout << "Erased elements from position " << it - v.begin() << " to " << v.end() - it << std::endl;

    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出:

Erased element at position: 2, value: 4
Erased elements from position 1 to 3
1 5

---

🚩总结