C++ --- vector

前言

这次学习vector的使用，vector（矢量）就是数据结构中的顺序表。
其大体用法和string类似，没有string类的冗杂，可以说vector是string的精简。

vector是一个类模板，使用它时要指定其实际类型，例如：vector< int > v1;

1、构造函数

上述构造现在除开第五个右值引用不讲，下文讲述其他的构造。
参数列表的 const allocator_type& alloc = allocator_type() 是空间配置器（STL的六大组成之一），也就是内存池，只在极少数的情况下我们会自己去传递此参数，绝大多数情况就是使用底层实现好的内存池即可，所以不用管他，给定缺省值即可。

1.1默认构造

	// 构造一个空对象vector<int> v1;

1.2n个val值构造

	// 开5个空间大小的vector，没有第二个参数则使用0进行初始化vector<int> v2(5);// 开10个空间大小的vector，使用2进行初始化vector<int> v3(10, 2);

1.3迭代器区间构造

	// 使用v3对象的迭代器区间进行构造vector<int> v4(v3.begin(), v3.end());

1.4拷贝构造

	// 拷贝构造vector<int> v5(v4);

1.4初始化列表构造

	// 初始化列表构造 --- 支持下面三种写法vector<int> v6({ 10,20,30,40 });vector<int> v6 = { 10,20,30,40 };      // 最常见的写法vector<int> v6{ 10,20,30,40 };

这是C++11新引入的新特性。

在这里介绍一下它：
initializer list 是一个类模板，使得STL容器能够使用一对 { } 来初始化对象。

通过typeid可以观察这一表示方法的实际类型：

所以引申至vector，也可以使用一对 { } 来构造对象，而上述最常见的写法是一个单参数的隐式类型转化，先构造一个initializer list，再拷贝构造临时对象，最后编译器会对此过程优化，成为直接构造。

2、遍历方式

2.1[ ] + 下标

因为vector底层也是一个数组，所以它也可以和string一样使用"[ ] + 下标"的形式遍历对象。

	//（1）[ ] + 下标cout << "[]+下标：";for (size_t i = 0; i < v.size(); i++){cout << v[i] ;}cout << endl;

2.2迭代器

迭代器和string一模一样，begin指向首元素的位置，end指向最后一个元素的下一个位置，也就是一个左闭右开区间：[begin,end)，它俩相减就是此区间内的元素个数。

	//（2）迭代器cout << "正向迭代器：";vector<int>::iterator it1 = v.begin();vector<int>::iterator it2 = v.end();while (it1 != it2){cout << *it1;++it1;}cout << endl;cout << "反向迭代器：";vector<int>::reverse_iterator it3 = v.rbegin();vector<int>::reverse_iterator it4 = v.rend();while (it3 != it4){cout << *it3;++it3;}cout << endl;// const正向迭代器// const反向迭代器

此外还有const正向迭代器和const反向迭代器，使用于const修饰的对象。

2.3范围for

范围for底层就是迭代器，支持迭代器也就支持范围for。

	//（3）范围for// 对于内置类型，不用加引用cout << "范围for：";for (auto e : v){cout << e;}cout << endl;// 对于自定义类型，比如string类型，要使用引用vector<string> vs;// push操作...for(auto& e : vs){cout << e;}

为什么对于内置类型不用加引用，而自定义类型要加引用呢？
因为首先范围for的底层是迭代器，是讲对象的迭代器类似于拷贝给给e，提到拷贝，对于内置类型进行浅拷贝（拷贝成本低，是否使用引用影响不大），而对于自定义类型是进行的深拷贝，为了减少不必要的深拷贝操作，所以需要加上引用，若不是使用引用，则会调用拷贝构造，增加不必要的操作。

3、常用方法或重载

（1）增

push_back()

功能：在顺序表尾部插入一个元素。
例：

	vector<int> v;// push_back()// 功能：在顺序表的末尾添加一个元素v.push_back(1); v.push_back(10);v.push_back(100);v.push_back(1000);v.push_back(10000);// 打印对象：for (auto e : v){cout << e << " ";}cout << endl;

打印结果：

insert()

功能：在任意pos位置（迭代器）之前插入一个元素。
例：

	// insert()// 功能：在pos位置之前插入元素// 在pos位置之前插入一个元素(1)：		iterator insert(iterator position, const value_type & val);// 在pos位置之前插入 n个元素(2)：     void insert(iterator position, size_type n, const value_type & val);// 在pos位置之前插入一段迭代器区间(3)：//		template <class InputIterator>//			void insert(iterator position, InputIterator first, InputIterator last);vector<int> v1;size_t j = 0;for (int i = 20; i <= 40; i+=2){v1.push_back(i);cout << v1[j++] << " ";}// (1)在40位置之前插入39v1.insert(v1.end() - 1, 39);// (2)在22位置之前插入3个0v1.insert(v1.begin() + 1, 3, 0);// (3)在30位置之前插入v的迭代器区间v1.insert(v1.begin() + 8, v.begin(), v.end());for (auto e : v1){cout << e << " ";}cout << endl;cout << "--------------------------------------------------------" << endl;

运行结果：

这里的迭代器加减常数是确定插入的位置，begin()是首元素的迭代器，自然就是下标为0的位置，加几就是在那个位置之前插入插入数据，例如（3），由于（2）的原因，在30的数据之前又新插入了3个数据，所以下标从原来的5 -> 8，所以要在30之前插入数据，begin() + 8即可，
end()也是如此。

assign()

功能：填充顺序表或者替换现有顺序表内容。
例：

	// asign()// 功能：填充顺序表或者替换现有内容// 插入一段迭代器区间(1)：//		template <class InputIterator>//			void assign(InputIterator first, InputIterator last);// 增加n个val(2)：		void assign(size_type n, const value_type & val);vector<int> v4;// 向空的对象增加数据v4.assign(5, 3);                 // n个val v4.assign(v.begin(), v.end());   // 迭代器区间cout << endl;cout << "--------------------------------------------------------" << endl;

运行结果：

对于assign()接口，对一个空的对象使用则是添加数据，上述两种方式都可以，但是若此对象不是空对象，则会变成替换功能，也就是先清空数据，再添加数据。例如上述代码中的assign()，第一次是对v4对象初始化，后面的一次assign()是对v4对象的内容进行替换。

（2）删

erase()

功能：删除pos位置（迭代器）的元素。
例：

	// evase()// 功能：删除pos位置（迭代器）的元素。// 删除pos位置的数据：iterator erase(iterator position);// 删除一段迭代器区间：iterator erase(iterator first, iterator last);vector<int> v2;for (int i = 0; i < 10; i++){v2.push_back(i);}// 删除pos位置的数据 --- 参数使用迭代器vector<int>::iterator it1 = v2.begin();v2.erase(it1 + 5);   // 删除5for (auto e : v2){cout << e << " ";}// 删除一段迭代器区间 --- 参数使用迭代器vector<int>::iterator it1 = v2.begin();vector<int>::iterator it2 = v2.end();v2.erase(it1 + 6 ,it2);   // 删除6~9for (auto e : v2){cout << e << " ";}// 最常用方法： 结合find删除指定元素// vector<int>::iterator pos = find(v2.begin(), v2.end(), 5);auto pos = find(v2.begin(), v2.end(), 5);v2.erase(pos);for (auto e : v2){cout << e << " "; }

运行结果：

删除5：

删除6~9：

结合find()删除元素5：

vector和string有些不同，find()接口是调用的算法库里面的find方法，vector自身模板类是没有实现find接口的，下面介绍一下算法库的find()：
std::find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
参数列表是迭代器区间和一个目标值，返回值是一个此目标值的迭代器。

clear()

功能：清除对象的整个资源，不删除空间。
例：

	// 功能：清空资源，不是删除空间v2.clear();

pop_back()

功能：删除顺序表的最后一个元素。
例：

	// pop_back()// 功能：删除顺序表的最后一个元素vector<int> v3;v3.push_back(1);v3.push_back(2);v3.push_back(3);v3.push_back(4);v3.push_back(5);cout << "删除前：";for (auto e : v3){cout << e;}cout << endl;v3.pop_back();cout << "删除后：";for (auto e : v3){cout << e;}

运行结果：

（3）查

operator[ ]

功能：返回指定下标位置的元素。
例：

	// operator[ ]// 功能：返回指定下标位置的数据vector<int> v4;v4.push_back(1);v4.push_back(2);v4.push_back(3);v4.push_back(4);v4.push_back(5);// 对下标为0的元素加1cout << ++v4[0] << endl;          // 1 -> 2

此重载对于非法位置进行访问时会进行assert断言检查错误。

越界操作：

程序会直接崩溃。

at()

功能：返回指定下标位置的元素。
例：

	vector<int> v4;v4.push_back(1);v4.push_back(2);v4.push_back(3);v4.push_back(4);v4.push_back(5);// 对下标为4的元素加1cout << ++v4.at(4) << endl;          // 5 -> 6

注意，此方法对于越界操作的检查是使用抛异常，和[ ] 不一样。

越界操作：

会抛出 invalid vector subscript 也就是无效向量下标的异常。

front() 与 back()

功能：返回对象首元素和返回对象尾元素。
例：

	// front()// 功能：返回对象的首元素cout << v4.front() << endl;            // 1// back()// 功能：返回对象的尾元素。cout << v4.back() << endl;             // 5

data()

功能：返回对象底层指向数组的指针。
例：

	// data()// 功能：返回底层指向数组的指针。cout << v4.data();

（4）大小与容量

size()

功能：查看顺序表对象的大小
例：

	//（1）size()// 功能：查看顺序表对象的大小vector<int> v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);cout << v.size();          // size = 5

resize()

功能：调整对象的大小。
例：

	//（6）resize()// 功能：调整对象的大小vector<int> v5 = { 1,2,3,4,5,6,7 };// n < size --- 缩小至给定大小，并且多余数据也会同步删除v5.resize(3);// n > size --- 扩大至给定大小，若没有第二个参数，则默认为0，有则使用指定的值v5.resize(10);        // 未指定v5.resize(10, 8);     // 指定

调试观察：

n < size：

n > size，指定val：

n > size，未指定val：

注意，当 n < capacity时，容量大小不会变化，而当 n > capacity时，capacity也会相应的增加到指定的n值。

empty()

功能：检查对象的大小是否为空。
例：

	//（5）empty()//功能：检查对象的大小是否为空，为空则返回真（true），反之返回假（false）vector<int> v4;// 对空对象bool b1 = v4.empty();cout << b1 << endl;        // 1 --- true// 对非空对象v4.push_back(1);bool b2 = v4.empty();cout << b2 << endl;        // 0 --- false

capacity()

功能：查看顺序表对象此时的容量大小。
例：

	//（2）capacity()// 功能：查看顺序表对象此时的容量大小vector<int> v2;// 记录起始的容量大小size_t temp = v2.capacity();for (size_t i = 0; i < 100; i++){// 向空对象push数据v2.push_back(i);// != 则说明扩容了 --- 输出它观察if (temp != v2.capacity()){cout << v2.capacity() << endl;// 再将扩容后大小赋值给给temp，重复操作temp = v2.capacity();}}

运行结果：

综上运行结果，可以观察出vector的底层扩容机制是1.5倍扩容，这和string的底层扩容是一样的。

reserve()

功能：只会扩容，会将容量扩至给定的大小，不会缩容。
例：

	//（3）reserve()// 功能：进行扩容，会将容量扩至给定的大小。vector<int> v3 = { 1,2,3,4,5 };cout << "扩容前：" << v3.capacity() << endl;v3.reserve(100);cout << "扩容后：" << v3.capacity() << endl;

运行结果：

注意，此接口和string的reserve就不一样了，若给定的容量值小于capacity时，vector是不会进行缩容的，它只有扩容的功能，尽管string面对给定的容量值小于capacity时，是一个不受约束力的请求，没有vector这样限制死。

shrink_to_fit

功能：进行缩容，缩至适应的大小。
例：

	//（4）shrink_to_fit()// 功能：缩容。v3.shrink_to_fit();     // 对于上述reserve后的v3进行缩容

运行结果：

但是缩容的代价是很大的，并不是直接对原空间进行缩小容量，而是在同一空间区域内找到符合缩容后的空间，将原空间内的数据拷贝进新空间，再将原空间释放，不怎么推荐使用此接口。

（5）其他

operator =

功能：拷贝。
例：

	// operator =// 功能：拷贝// 拷贝同类型对象(1)：		vector& operator= (const vector & x);// 初始化列表(3)：			vector& operator= (initializer_list<value_type> il);vector<int> v;vector<int> v1;v = v1;v = { 1,2,3,4,5 };

常用的就是使用初始化列表进行构造。

~vector< type > - - - (析构)

功能：清理对象的资源，不是销毁空间。

全局函数swap与成员函数swap

功能：交换两个对象，使用谁效果都差不多。

关系运算符重载

功能：对两个对象进行大小比较。

emplace()与emplace_back()

功能：emplace()和insert()相似，emplace_back()和push_back()相似。
在功能上两者没有什么较大的区别，但是在底层的实现上emplace与emplace_back要复杂的多。
所以在这里只演示怎么使用，不讲述底层机制。
例：

	// emplace() 与 emplace_back()// 功能：emplace()和insert()相似，//       emplace_back()和push_back()相似// 在功能上两者没有什么较大的区别，但是在底层的实现上emplace与emplace_back要复杂的多。// 所以在这里只演示怎么使用，不讲述底层机制。struct A
{// 构造函数A(int a1, int a2):_a1(a1),_a2(a2){cout << "A(int a1, int a2)" << endl;}// 拷贝构造A(const A& aa):_a1(aa._a1),_a2(aa._a2){cout << "A(const A& aa)" << endl;}int _a1;int _a2;
};vector<A> v3;A aa1(1, 3);cout << "-----------" << endl;// 使用有名对象v3.push_back(aa1);v3.emplace_back(aa1);cout << "-----------" << endl;// 使用匿名对象v3.push_back(A(3, 3));v3.emplace_back(A(3, 3));cout << "-----------" << endl;// 使用多参数的隐式类型转化v3.push_back({ 3,3 });          // 多参数需要使用{ }//v3.emplace_back({ 3, 3 });      // 对于emplace_back这种写法是不行的cout << "-----------" << endl;// 但是可以这样：// 直接传构造成员的参数，这种效率较高v3.emplace_back(3, 3); 

运行结果：

除了最后一种用法，其余用法效率上和push_back()是差不多的。

并且对于上述多成员变量的类型，遍历的时候也是有一些不同的。
例：

	// C++11 --- 范围forfor (auto& e : v3){cout << e._a1 << "," << e._a2 << endl;}// C++17 --- 结构化绑定for (auto& [x,y] : v3){cout << x << "," << y << endl;}

由于上述第一种写法是将v3的迭代器指向的元素拷贝给给e，中间进行了一次拷贝构造，所以这里可以加上引用，代表e是v3迭代器指向的元素的别名，不用经历中间的拷贝操作。并且e是数组的元素，元素是A类型的数据，所以遍历需要访问其中的成员。

上述第二种写法是C++17里面的结构化绑定，其实机理和C++11的e是差不多的，能够将其对象的参数直接写在[ ]内，进行拷贝，从而遍历对象直接输出[ ]内部的参数（此参数名称可随便取）即可，由于中间也有拷贝操作，所以也需要加上引用，以减少拷贝操作。