C++----STL（vector）

vector的介绍

vector的文档介绍：cplusplus.com/reference/vector/vector/

1.基本概念

• 简单来说，vector是表示可以改变大小的数组的顺序容器。
• 使用连续的存储位置来存储元素，因此可以通过常规指针的偏移量来高效访问。

2.内部机制

• vector内部使用动态分配的数组来存储元素。
• 插入新元素时，数组可能需要重新分配以增大尺寸，这是一项相对昂贵的任务。为避免频繁重新分配，vector可能会分配一些额外的存储空间以适应可能的增长。
• vector的实际容量可能大于存储元素所需的空间（即大小）。

3.内存管理

• 库采用不同的增长策略来平衡内存使用和重新分配。
• 重新分配通常只在大小以对数增长间隔发生时进行，以提供摊还常数时间复杂度的插入操作（如push_back）。
• 与数组相比，向量消耗更多内存，但具备管理和动态增长存储的能力。

4.vector的原型

vector的使用

vector 学习时一定要学会查看文档 ， vector 在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。（vector与string都基于顺序表实现，因此接口相似。如果已经掌握string用法的，理解vector会更容易。后续讲解将简要提及相似之处，重点介绍vector的特有特性和用法。）

迭代器

begin()

• 功能说明：返回一个指向vector第一个元素的迭代器。
• 注意：有可读可写和只读两种迭代器。

rbegin()

• 功能说明：返回一个指向vector最后一个元素的迭代器。
• 同样有可读可写和只读两种。（下面讲解的迭代器都如此）

end()

• 功能说明：返回一个指向vector最后一个元素之后位置的迭代器。

rend()

• 功能说明：返回一个指向vector第一个元素之前位置的反向迭代器。

构造函数

1.使用填充构造

//原型：explicit vector (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
vector<int> v1(10, 1);//创建一个包含10个整数的vector，每个整数初始化为1
vector<string> v2(10, "***");//创建一个包含10个字符串的vector，每个字符串初始化为"***"

2.使用迭代器范围构造

//原型：template <class InputIterator> vector (InputIterator first, InputIterator last，const allocator_type& alloc = allocator_type());
vector<int> v3(v1.begin(), v1.end());//使用v1的迭代器范围构造v3string str("hello world");
vector<char> v4(str.begin(), str.end());//使用字符串string的迭代器范围构造字符vector v4int a[] = {16, 2, 77, 29};
vector<int> v5(a, a + 4); // 使用数组a的迭代器范围构造v5

补充：配合sort函数的使用进行升序和降序排序

sort(v5.begin(), v5.end()); // 使用默认比较器（less<int>）对v5进行升序排序
sort(v5.begin(), v5.end(), greater<int>()); // 使用greater<int>比较器对v5进行降序排序
sort(v5.rbegin(),v5.rend()); // 使用反向迭代器对v5进行降序排序
sort(str.begin(), str.end()); // 对字符串str进行字典序排序
sort(a, a + 4); // 对数组a进行排序

容量相关的操作

size()

• 功能说明：返回vector中当前元素的个数。

max_size()

• 功能说明：返回vector中能容纳的最大元素个数。

capacity()

• 功能说明：返回vector在当前情况下能容纳的元素个数。

reserve()

• 功能说明：扩容。
• 注意：reserve不改变vector的大小（即size()的值），也不初始化新分配的内存。
• 易错展示：

  vector<int> v1;
  v1.reserve(10);
  for (size_t i = 0; i < 10; i++) {v1[i] = i; // 错误：v1.size()仍为0，访问v1[i]是未定义行为。
  }

•  正确做法：

  vector<int> v1;
  v1.reserve(10);
  for (size_t i = 0; i < 10; i++) {v1.push_back(i); // 正确：使用push_back添加元素并初始化。
  }

resize()

• 功能说明：扩容+初始化

  vector<int> v1;
  v1.resize(10); // 改变大小为10，新元素初始化为0（对于int类型）。
  for (size_t i = 0; i < 10; i++) {v1[i] = i; // 正确：v1的大小已经是10。
  }

empty()

• 功能：检查vector是否为空。如果vector的大小为0，则返回true；否则返回false

shrink_to_fit()

• 功能：请求移除vector中多余的容量。调用后，vector的容量将被调整为当前大小（即size()的值），前提是这不会增加内存分配的总大小。

元素访问

operator[]

• 功能：通过索引访问vector中的元素。
• 注意：不进行边界检查，如果索引超出范围，则行为未定义，可能导致程序崩溃或数据损坏）

    vector<int> v = {1, 2, 3};int first = v[0]; // 访问第一个元素，值为1。

at()

• 功能：通过索引访问vector中的元素。
• 与operator[]不同，at会进行边界检查。如果索引超出范围，则抛出std::out_of_range异常。

    vector<int> v = {1, 2, 3};int second = v.at(1); // 访问第二个元素，值为2。

data()

• 功能说明：返回指向vector中第一个元素的指针（类型为T*，其中T是vector存储的元素类型）。如果vector为空，则返回空指针。
• 类似于string中的c_str()方法，但data返回的是可修改的指针。

    vector<int> v = {1, 2, 3};int* ptr = v.data();cout << ptr[0] << " " << ptr[1] << " " << ptr[2] << endl; // 输出：1 2 3

修改操作

push_back()

• 功能：在vector末尾添加一个元素。

pop_back()

• 功能：移除vector末尾的元素.

insert()

• 功能：在指定位置插入一个或多个元素。

    int a[] = { 16,2,77,29,3,33,43,3,2,3,3,2 };vector<int> v1(a, a + sizeof(a)/sizeof(int));// 头插 v1.insert(v1.begin(), 100);

erase()

• 功能：移除指定位置的元素或一段元素。

    int a[] = { 16,2,77,29,3,33,43,3,2,3,3,2 };vector<int> v1(a, a + sizeof(a)/sizeof(int));// 头删v1.erase(v1.begin());// 删除第3个数据v1.erase(v1.begin() + 2);

注意：std::vector中使用erase和insert后迭代器失效的情况

在C++的STL（标准模板库）中，vector是一个动态数组，其内存可以重新分配和移动。因此，当你对vector进行erase或insert，可能会导致指向vector元素的迭代器失效。失效的迭代器不能再被用来访问vector中的元素，因为这样做会导致未定义行为。

下面的代码例子，展示了在std::vector中使用erase后迭代器失效的情况：

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// 创建一个指向vector中第三个元素的迭代器auto it = vec.begin() + 2; // 指向3// 输出迭代器指向的值cout << "Before erase: " << *it << endl; // 输出: 3// 删除迭代器指向的元素vec.erase(it);// 此时it已经失效for (auto e : vec) {cout << e << " ";}cout << endl;// 下面的代码是未定义行为，因为it已经失效// cout << "After erase (undefined behavior): " << *it << endl; // 不要这样做return 0;
}

正确做法：

#define _CRT_SECURE_NO_EARNINGS 1
#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// 创建一个指向vector中第三个元素的迭代器auto it = vec.begin() + 2; // 指向3// 输出迭代器指向的值cout << "Before erase: " << *it << endl; // 输出: 3// 删除迭代器指向的元素it = vec.erase(it);// 我们可以获取删除元素后的下一个元素for (auto e : vec) {cout << e << " ";}cout << endl;cout << "After erase (undefined behavior): " << *it << endl; // 此时的it指向被删除的位置的下一个元素4return 0;
}

下面的代码例子，展示了在std::vector中使用insert后迭代器失效的情况：

#define _CRT_SECURE_NO_EARNINGS 1
#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> vec = { 1, 2, 3, 4, 5 };vector<int>::iterator it = vec.begin() + 2;cout << "it: " << *it << endl;// 插入新元素vec.insert(vec.begin(), 10); // 在开头插入10for (auto e : vec) {cout << e << " ";}cout << endl;// 所有指向vec元素的迭代器（包括end()之前的迭代器）都可能失效// 下面的代码同样是未定义行为，因为之前的迭代器（即使它们没有直接指向被插入的位置）也可能不再有效// cout << "After insert (undefined behavior): " << *it << endl; // 这是错误的return 0;
}

正确做法：

#define _CRT_SECURE_NO_EARNINGS 1
#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> vec = { 1, 2, 3, 4, 5 };vector<int>::iterator it = vec.begin() + 2;cout << "it: " << *it << endl;// 插入新元素vec.insert(vec.begin(), 10); // 在开头插入10for (auto e : vec) {cout << e << " ";}cout << endl;// 正确的做法是重新获取迭代器it = vec.begin() + 2;cout << "After insert (undefined behavior): " << *it << endl; return 0;
}

swap()

• 功能：交换两个vector的内容。

clear()

• 功能：移除vector中的所有元素，使其变为空容量。

assign()

• 功能：清楚vector中的值，并用新值重新赋值。

    v1.assign(10, 1); // 将v1重新赋值为10个1

补充：find在 vector 中的应用

vector中的find：vector不像string在成员函数中直接提供了find(),而是通过<algorithm>头文件中的find函数，用于查找元素的位置。

#include<iostream>
#include<algorithm>
using namespace std;int main()
{int a[] = { 16,2,77,29,3,33,43,3 };vector<int> v1(a, a + sizeof(a)/sizeof(int));auto pos = find(v1.begin(), v1.end(), 3); // 在v1中查找元素3// 删除第3个数据v1.erase(v1.begin()+2);return 0;
}

迭代器失效问题：

#include<iostream>
#include<algorithm>
using namespace std;int main()
{int a[] = { 16,2,77,29,3,33,43,3 };vector<int> v1(a, a + sizeof(a)/sizeof(int));auto pos = find(v1.begin(), v1.end(), 3); // 在v1中查找元素3// 删除所有的3 -- 涉及迭代器失效！后面解决while(pos != v1.end()){v1.erase(pos);pos = find(v1.begin(), v1.end(), 3); // 可能导致无限循环，因为pos可能已失效}return 0;
}

原因：vector在insert或erase操作后，可能会重新分配内存（尤其是当容量不足时），导致所有指向该vector的迭代器失效。

解决：

    while((pos = find(v1.begin(), v1.end(), 3)) != v1.end()){v1.erase(pos);}