I.vector 的介绍及使用

0x00 vector 介绍

🔍 vector 文档介绍：vector - C++ Reference

1.vector是表示可变大小数组的序列容器，我们说vector像是数组，但又不像数组

为啥像数组：vector就像是数组一样，它也是采用连续存储空间来存储元素的，这也就意味着我们可以用下标访问vector元素，和数组一样高效。

为啥不像数组：vector的大小是可以动态改变的，而且它的大小会被容器自动处理

2.本质上来说，vector使用动态分配数组来存储它的元素。

 当新元素插入时，为了增加存储空间，这个数组就需要被重新分配大小。具体做法是分配一个新的数组，然后将全部的元素转移到这个新的数组。就时间成本而言，vector的消耗过高，我们通常不会考虑每次插入新的元素就要重新分配一次数组空间。

3.vector空间分配策略：所以为了简化我们的操作，vector在动态分配上往往会分配额外的存储空间以适应可能的增长，因此容器的实际容量可能会大于严格容纳其元素所需的存储空间（即其大小)。

4.与其他动态序列容器（双端队列、列表和前向列表）相比，向量在访问其元素方面非常高效（与数组一样），并且在从其末尾添加或删除元素方面相对高效。对于涉及在非末尾位置插入或删除元素的操作，向量的性能比其他容器差，并且与列表和前向列表相比，其迭代器和引用的一致性较差。

0x01 初始化vector

1.无参构造

vector<int> v1;   // 无参构造，创建一个int类型的，空的vector对象

2.构造并初始化：用 n 个 value 初始化：

vector<int> v2(10, 3);   // 10个3

3.迭代器区间初始化：begin 👉 end

vector<int> v3(v2.begin(), v2.end());

4.拷贝构造

vector<int> v4(v2);

但是不乏有这种情况，我不要拷贝对象的头尾数据呢？即，不要它的 begin 和 end 

vector<int> v3(++v2.begin(), --v2.end());

综合

vector<int> arr1;								//一个空数组
vector<int> arr2 {1, 2, 3, 4, 5};				//包含1、2、3、4、5五个变量
vector<int> arr3(4);							//开辟4个空间，值默认为0
vector<int> arr4(5, 3);							//5个值为3的数组
vector<int> arr5(arr4);							//将arr4的所有值复制进去，和arr4一样
vector<int> arr6(arr4.begin(), arr4.end());		//将arr4的值从头开始到尾复制
vector<int> arr7(arr4.rbegin(), arr4.rend());	//将arr4的值从尾到头复制

---------------------------------------------------------------------------------------------------------------------------------

对于迭代器区间初始化，它这里的 InputInerator 不一定是 vector Inerator。

它是一个模板，所以你传的是谁的迭代器，它就可以实例化出谁的迭代器

0x02 关于 vector 的析构、拷贝构造和赋值构造
​ 至于析构函数，一般情况下我们不需要管，因为它会自动调用。

拷贝构造和赋值构造，vector 的拷贝构造和赋值其实就是深拷贝。

这些我们放在 vector 模拟实现的章节里详细探讨。

II.vector的遍历

0x00 push_back

vector 不能用爽到飞起地 operator+= 

string 能用 += 主要是 string 不仅可以尾插一个字符还可以追加一个字符串。

但是 vector 就只支持一个一个数据的插入和删除，push_back 和 pop_back。

vector.push_back(内容);

0x01 下标+方括号遍历

vector 是连续的空间，又支持 operator[] 和 size() ，所以可以用下标+方括号遍历。

void vector_Traversal_test() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	// 遍历
	for (size_t i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

结果如下

当然也支持修改

void vector_Traversal_test() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	// 遍历
	for (size_t i = 0; i < v.size(); i++) {
		v[i] += 1;    // 令每个元素+1
		cout << v[i] << " ";
	}
	cout << endl;
}

结果如下

0x02 访问vector（）的at（）

顺便再讲一下 at() ，它和 operator[] 一样，也是用来访问 vector 的，但是 at() 会进行边界检查

void test_vector4() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	cout << v.at(0) << endl;
	cout << v.at(3) << endl;
}

结果如下

需要注意的是！！！ operator会用断言assert检查是否越界，而at（）会抛出异常

void test_vector4() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	cout << v.at(5) << endl;  // 故意越界看看
}

结果如下

0x03 迭代器遍历vector

//迭代器：vector<int>::iterator
for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++)
{
    cout << *it << endl;
}
//迭代器：vector<int>::reverse_iterator
for (vector<int>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++)
{
    cout << *it << endl;
}

0x04 范围for

vector 支持迭代器，也就支持范围 for，这个我们在模拟实现 string 的时候已经验证过了。

范围 for 的本质就是编译器在编译时自动替换成迭代器，这里也一样。

void vector_Traversal_test() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	// 范围for
	for (auto e : v) {
		cout << e << " ";
	}
	cout << endl;
 
	for (auto& e : v) {
		e += 10;
		cout << e << " ";
	}
	cout << endl;
}

结果如下

Ⅲ. vector 空间

0x00 获取数据个数的 size()

和string里的一样，用来获取数据的元素个数

void test_vector2() {
	vector<int> v(6, 6);        // 生成6个6
	cout << v.size() << endl;
}

0x01 改变 vector 容量的 reserve()

void test_vector3() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	v.reserve(100);
}

结果如下

reserve 会扩容，但是不会影响数据个数。[capacity] 4  → [capacity]100

0x02 改变 vector 大小的 resize()

void test_vector4() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	v.resize(100);
}

string 的 resize 如果不指定 "填充值" ，默认给的是 \0

而 vector 的 resize 如果不指定，默认给的是其对应类型的缺省值作为 "填充值"

这里是 int 就是 0，如果是指针，对应的缺省值就是空指针。

注意注意！！！如果开的数据比之前小，还会删除数据

void test_vector4() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	v.resize(2);
}

结果如下

Ⅳ. vector 增删查改

0x00 pop_back（）尾删

void test_vector5() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	for (auto e : v) cout << e << " "; cout << endl;
 
	v.pop_back();   // 尾删：3
	for (auto e : v) cout << e << " "; cout << endl;
	
	v.pop_back();   // 尾删：2
	for (auto e : v) cout << e << " "; cout << endl;
}

结果如下

0x01  assign() 赋值

assign 可以把 vector 的内容覆盖掉。允许给一段区间覆盖，也可以给  个 value 去覆盖。

void test_vector6() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	v.assign(10, 5);   // 原来是1到4，现在改成10个5
}

结果如下

0x02探讨：为什么vector不提供find接口

string、map、set 都有 find() 用，凭什么 vector 和 list 没有

其实，我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。

而 vector 之所以不提供 find ，是因为如果去查找元素效率就会是  ……

但其实我们也可以用，算法库algorithm里就有同样的find操作。

该find内部是从begin到end进行一次遍历，复杂度为O（n）

值得一提的是，在C++中，凡是使用迭代器区间，都是左闭右开的——（first，last].

再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时，

得到的结果是按 key 排序的结果，而不是插入时的顺序，所以这两个容器没有 push_back 操作。

其实，插入到 map 与 set 中的元素会被组织到一颗红黑树上，红黑树是一颗平衡二叉树，

平衡二叉树是一颗二叉排序树，对一颗二叉排序树的查找有点像二分查找，复杂度是 ，

由于 map 与 set 的数据结构能有更快的查找方法，所以在容器内提供了 find 方法。
 

0x03 insert () 插入

void test_vector7() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
	vector<int>::iterator ret = find(v.begin(), v.end(), 3);
	if (ret != v.end()) {
		cout << "找到了" << endl;
		v.insert(ret, 30);         // 在ret位置前面插入一个30
	}
 
	for (auto e : v) cout << e << " "; cout << endl;
}

结果如下

用insert去头插：

void test_vector8() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
    for (auto e : v) cout << e << " "; cout << endl;
 
	v.insert(v.begin(), -1);   // 在起始位置插入一个-1
 
	for (auto e : v) cout << e << " "; cout << endl;
}

结果如下

0x04 erase（）删除

使用erase（）的时候需要判断一下有没有要删除的元素：

void test_vector9() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (auto e : v) cout << e << " "; cout << endl;
 
	vector<int>::iterator pos = find(v.begin(), v.end(), 5);
	if (pos != v.end()) {   // 判断pos是否存在
		v.erase(pos);       // 删除pos
	}
 
	for (auto e : v) cout << e << " "; cout << endl;
}

结果如下

怕的就是要删的目标不存在！比如我要删个 5，但是 vector 里只有 1，2，3，4 。

vector<int>::iterator pos = find(v.begin(), v.end(), 5);
v.erase(pos);

如果有了判断，就不会翻车了，如果待删目标不存在，就不会去走 erase()  。 

因为 pos 如果找不到就会等于 end() 上的值，我们利用这一点进行 if 判断

vector<int>::iterator pos = find(v.begin(), v.end(), 5);
if (pos != v.end()) {   // 检查！
	v.erase(pos);   
}

0x05 clear（）清空数据

void test_vector10() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	
	printf("清空前：");
	for (auto e : v) cout << e << " "; cout << endl;
	
	v.clear();
	printf("清空后：");
	for (auto e : v) cout << e << " "; cout << endl;
}

结果如下