一、关于vector

vector容器是C++ STL中封装了动态数组的顺序容器，可以自动管理内存大小，也就是在运行时根据需要动态增长或缩小，并且支持通过下标快速访问，在使用前必须include<vector>，在此头文件内，vector实际上是定义于namespace std内的一个类模板：

1
2
3
4
namespace std {
    template <typename T, typename Allocator = allocator<T>>
    class vector;
}

也就是说vector可存储元素可以是任意类型T，而第二个template参数用来定义内存模型，默认为C++标准库的allocator。存储的区域不同于array，array的内存空间是固定大小的，并且对象和数组存储在相同的内存区域（栈）中，而vector对象存储在自由存储区（堆）

在正式介绍vector的基本使用前，还需知道vector的两个概念（有对应的函数方法）——大小（Size）和容量（Capacity）

  • capacity()：返回vector实际能容纳的元素个数
  • size()：返回当前 vector 容器中已经存有的元素个数

如果想知道当前vector容器有多少未被使用的存储空间，可以通过capacity() - size()得知，若size()和capacity()返回的值相同，则表明当前 vector容器中多余的存储空间，这意味着，下一次向 vector 容器中添加新元素，将导致vector容器扩容

《C++标准库(第二版)》中提到：

vector的容量之所以重要，有两个原因：

1.一旦内存重新分配。vector元素相关的所有reference、pointer或iterator都会失效

2.内存重新分配很耗时间

二、vector的创建和方法

一维数组的创建与初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::vector<int> v1;                                //一个空数组
std::vector<int> v2{ 1, 2, 3, 4, 5 };               //包含1、2、3、4、5五个变量
std::vector<int> v3(4);                             //开辟4个空间，值默认为0
std::vector<int> v4(5, 3);                          //5个值为3的数组
std::vector<int> v5(v4);                            //将v4的所有值复制进去，和arr4一样
std::vector<int> v6(v4.begin(), v4.end());          //将v4的值从头开始到尾复制
std::vector<int> v7(v4.rbegin(), v4.rend());        //将v4的值从尾到头复制
//使用函数resize()
std::vector<int> v8;
v8.resize(5);       //此时的v8内的元素为：0 0 0 0 0
v8.resize(5, 5);    //此时的v8内的元素为：5 5 5 5 5 
//使用函数reserve()
std::vector<int> v9;
reserve(5)          //此时的v9并没有任何元素
v9[0] = 1;   //error!

二维数组的创建与初始化

1
2
3
4
5
6
7
8
9
std::vector<vector<int>> v1;						//定义一个空的二维vector
std::vector<vector<int>> v2(6, vector<int>(6, 6));	//创建一个6行6列值全为6的二维vector
//使用函数resize()
vector<vector<int>> v3;
v3.resize(6);
for (auto v : v3)
{
    v.resize(6, 6);       //创建一个6行6列值全为6的二维vector
}

无论一维还是二维，vector都可以直接通过下标进行快速访问，都可通过双重for循环遍历访问

resize()与reserve()的区别

resize(n, t)：

  • resize(n)意味着调整vectior容器的大小（size），使其能容纳n个元素。若n小于容器当前的大小，则删除多出来的元素，否则，添加默认初始化的元素，如上述例子里的v8
  • 参数t，是用来指定调整vector的大小后，创建的元素初始化值为t，如上述例子里的v8
  • 如果n>当前容器容量(capacity)，内存会自动重新分配

reserve(n)：

  • reserve(n)意味着更改vector的容量（capacity），使vector至少可以容纳n个元素，用来控制vector的预留空间
  • reserve(n)分配出的空间不会被初始化（在空间内不真正创建元素对象），在没有添加新的元素之前，不可访问，如上述例子的v9
  • 若n<当前容器大小(size)，预留空间无变化

vector常用的方法总览

begin()：返回指向容器中第一个元素的迭代器

end()：返回指向容器最后一个元素所在位置的后一个位置的迭代器

empty()：判断vector是否为空，为空返回true否则false

shrink_to_fit()：将capacity调整到size的大小

back()：返回最后一个元素

data()：返回指向容器中第一个元素的指针

clear：清除容器内容，size=0，存储空间不变

swap()：交换2个vector容器的内容

insert()：在指定位置插入多个元素

emplace()：在指定位置插入一个元素

push_back()：在容器的尾部插入元素

pop_back()：删除最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变

emplace_back()：在容器的尾部插入元素，和push_back不同

insert()与emplace()

insert()函数的功能是在vector容器的指定位置插入一个或多个元素。该函数的语法格式有多种，常用用法：

insert(pos,elem)：在迭代器pos指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器

insert(pos,n,elem)：在迭代器pos指定的位置之前插入n个元素elem，并返回表示第一个新插入元素位置的迭代器

insert(pos,first,last) ：在迭代器pos指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器

insert(pos,initlist)：在迭代器pos指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，元素之间逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
void printVector(const std::vector<int>& v)  //打印v1中所有元素
{
	std::cout << "v1: ";
	for (int n : v) {
		std::cout << n << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::vector<int> v1{ 6,6,6 };
	std::vector<int> v2{ 666,666,666 };
	printVector(v1);

	//第一种
	auto it = v1.begin();
	it = v1.insert(it, 8);
	printVector(v1);
	//第二种
	it = v1.insert(it, 2, 8);
	printVector(v1);
	//第三种
	it = v1.insert(it, v2.begin(), v2.end());
	printVector(v1);
	//第四种
	v1.insert(it, { 888,888,888 });
	printVector(v1);
}

emplace()是C++ 11标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素

注：每次只能插入一个元素，而不是多个

函数原型：iterator emplace (const_iterator pos, args...)，其中，pos 为指定插入位置的迭代器，args… 表示与新插入元素的构造函数相对应的多个参数（即被插入元素的构造函数需要多少个参数，那么在 emplace() 的第一个参数的后面，就需要传入相应数量的参数），该函数会返回表示新插入元素位置的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>
void printVector(const std::vector<int>& v)
{
	std::cout << "v: ";
	for (int n : v) {
		std::cout << n << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::vector<int> v{ 6,6,6 };
	v.emplace(v.begin(), 8);
	printVector(v);

	return 0;
}

那么insert()和emplace()谁的效率会比较高呢？答案是emplace()。因为insert()在插入元素时，需要调用类的构造函数和移动构造函数（或拷贝构造函数），而 emplace() 在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中，所以在实现相同功能的情况下，emplace()更胜一筹

push_back()和emplace_back()

两者在用法上一样，且都是在vector容器尾部插入一个元素：

1
2
3
std::vector<int> v;
v.push_pack(8);
v.emplace_back(6);

两者的主要差别在于底层实现的机制不同：push_back()将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素），而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。所以emplace_back()的速度更快，详情可以参考我的cpp学习笔记的P48：My cpp note

eraze()和swap()

erase()函数通过迭代器删除某个或某个范围的元素，并返回表示下一个元素位置的迭代器

1
2
3
4
5
std::vector<int> v{1, 2, 3, 4, 5};
//删除v开头往后偏移两个位置的元素，即arr的第三个元素，3
v.erase(v.begin() + 2);
//删除v.begin()到v.begin() + 2之间但不包括v.begin() + 2的元素：即删除在v.begin()和v.begin()+1上的元素
v.erase(v.begin(), v.begin() + 2);

swap()函数将两个vector中的内容进行交换，不在单独的元素上调用任何移动、复制或交换操作

1
2
3
std::vector<int> v1 = {5, 4, 3, 2, 1};
std::vector<int> v2 = { 1, 2, 3, 4, 5 };
v1.swap(v2);

三、std::vector删除元素的几种方式及区别

pop_back():删除 vector 容器中最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变

erase(iter):删除 vector 容器中iter迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变

erase(iter1，iter2):删除 vector 容器中位于迭代器 [iter1,iter2)指定区域内的所有元素，并返回指向被删除区域下一个位置元素的迭代器。该容器的大小（size）会减小，但容量（capacity）不会发生改变

clear():删除 vector 容器中所有的元素，使其变成空的 vector 容器。该函数会改变 vector 的大小（变为 0），但不是改变其容量

remove(iter1，iter2，key):删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。（后面会详细说明，该函数的用法）

swap(vector):用于交换向量的内容，用一个向量调用它并接受另一个向量作为参数并交换它们的内容。 (两个向量的大小可能不同)。通过交换向量进行删除

shrink_to_fit():将vector 容器的容量缩减至和实际存储元素的个数相等。可以配合以上的函数，收回内存

1.使用earse和remove配合删除容器中指定值的元素

remove函数本质上没有完成元素的完全删除工作，因为容器的大小和容量都没有改变，它只是将所有被删除的元素用下一个未被删除的元素进行覆盖且容器中的元素顺序不变，并返回一个迭代器。也就是说，删掉指定的元素后，容器的大小和容量没有发生变化，这是不合理的，通常来说我们希望删掉一些元素后，至少保证容器的大小也相应减少，因此需要借助上面提到的erase函数，所以说remove需要和erase搭配使用才能实现完整的删除指定值的元素功能

单独使用remove:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>			// 注意：remove位于algorithm函数库中
int main()
{
    std::vector<int> v{0, 1 , 2 ,3 ,4};

    std::cout << v.size() << std::endl;     // 输出的结果为5，容器中存了5个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量

    std::remove(v.begin(), vecInt.end(),3); //删除容器中值为3的元素
    
    std::cout << v.size() << std::endl;     // 输出的结果为5，容器中存了5个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量

    for(auto i : v)
    {
        std::cout << i << std::endl;
    }
}
// 使用remove之前，容器vector的值为： 0,1,2,3,4
// 使用remove函数删除值为3的元素后，容器vector的值为：0,1,2,4,4
// 可以看出remove,没有改变容器的size，只是将值为3的元素删除后，将后面的元素，移动到前面(后面的值还保留，因此最后是4)。

earse和remove配和使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>		//注意：remove位于algorithm函数库中
int main()
{
    std::vector<int> v{0, 1 , 2 ,3 ,4};

    std::cout << v.size() << std::endl;     // 输出的结果为5，容器中存了5个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量

    vecInt.erase(std::remove(v.begin(), v.end(), 3), v.end());
    
    std::cout << v.size() << std::endl;     // 输出的结果为4，容器中存了4个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量

    for(auto i : v)
    {
        std::cout << i << std::endl;
    }
}
// 使用remove之前，容器vector的值为： 0,1,2,3,4
// 使用remove函数删除值为3的元素后，容器vector的值为：0,1,2,4,
// 可以看出remove,容器的size变成了size-1，删除了值为3的元素。容器的capacity不变

注意：

remove函数位于algorithm函数库中，使用时需要调用algorithm头文件。

earse和remove不改变vector的容量capacity，(不会收回容器在内存中开辟的空间）

2.使用swap删除容器的所有元素，并收回内存

使用clear清空容器中的元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>

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

    std::cout << v.size() << std::endl;     //  输出的结果为5，容器中存了5个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量

    vecInt.clear();					// 使用clear清空容器
    
    std::cout << v.size() << std::endl;     // 输出的结果为0，容器中存了0个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为5，容器在内存开辟空间的容量
}

使用swap清空容器中的元素并回收内存:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>

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

    std::cout << v.size() << std::endl;      //  输出的结果为5，容器中存了5个元素
    std::cout << v.capacity() << std::endl;  //  输出的结果为5，容器在内存开辟空间的容量

    std::vector<int>().swap(v);		// 使用swap函数，将容器与空的容器交换，从而删除容器数据并收回内存
    
    std::cout << v.size() << std::endl;     // 输出的结果为0，容器中存了0个元素
    std::cout << v.capacity() << std::endl; // 输出的结果为0，容器在内存开辟空间的容量
}

四、vector的扩容底层机制

前面提到，vector作为容器有着动态数组的功能，当向vector容器中插入元素，如果元素有效个数size与空间容量capacity相等时，vector容器会自动扩容：系统会自动申请新空间，拷贝元素到新的空间，并释放旧空间

所以在发生扩容的时候会给程序带来额外的开销，导致代码在运行的时候会被拖慢，还会使vector元素相关的iterator等失效，为尽量避免这种情况的发生，可以在每次定义一个std::vector的对象后，使用reserve()函数来指定容量大小，避免内存再分配产生的开销

扩容后的空间容量：

扩容的时候，申请新的内存空间的空间大小为原空间的2倍或1.5倍。不同的的实现厂商都是按照自己的方式扩容的，如：linux下是按照2倍的方式扩容的，而vs下是按照1.5倍的方式扩容的，示例如下演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>
void printVector(const std::vector<int>& v)
{
	std::cout << "v: ";
	for (int n : v) {
		std::cout << n << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::vector<int> v{ 6,6,6,6 };
	
	std::cout << "v的容量：" << v.capacity() << std::endl;
	printVector(v);

	std::cout << "add an element to v..." << std::endl;
	v.push_back(8);
	std::cout << "v的容量：" << v.capacity() << std::endl;
	printVector(v);

	return 0;
}

在Visual Studio上运行

在Visual Studio Code上运行