思维导图（建议收藏，复习小宝贝）
一、vector容器简介
vector是C++标准模板库中的部分内容，中文偶尔译作"容器"，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward_lists统一的迭代器和引用更好
二、vector常用接口
1.vector初始化操作
1.构造函数
void test_vector1() { vector<int> v1; //无参构造 vector<int> v2(10, 8); //用10个8初始化 vector<int> v3(v2.begin(), v2.end()); //迭代器区间初始化 vector<int> v4(v3); //拷贝构造 string s1("hello world"); vector<char> v5(s1.begin(), s1.end()); //用string的迭代器区间初始化 }
2.析构函数
系统会自动调用析构函数
3.赋值重载函数
int main () { std::vector<int> v1 (3,0); std::vector<int> v2 (5,0); //赋值前 cout << int(v1.size()) << '\n'; // v1 = 3 cout << int(v2.size()) << '\n'; // v2 = 5 v2 = v1; //赋值后 cout << int(v1.size()) << '\n'; // v1 = 3 cout << int(v2.size()) << '\n'; // v2 = 3 return 0; }
2.vector容量相关接口
1.基本使用方法
void test_vector3() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(5); v1.size(); // 计算当前数据个数 v1.capacity(); // 计算当前的空间容量 v1.max_size(); // 查看最大容量 v1.empty(); // 判断容器是否为空 v1.reserve(100); // 扩容 v1.resize(100, 5); // 扩容+初始化 或 删除数据 }
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。
2.vector增容机制
//检查容量递增情况 void test_vector4() { size_t sz; std::vector<int> foo; sz = foo.capacity(); std::cout << "making foo grow:\n"; for (int i = 0; i < 100; i++) { foo.push_back(i); if (sz != foo.capacity()) { sz = foo.capacity(); std::cout << "capacity changed: " << sz << '\n'; } } }
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是 PJ 版本STL，g++是 SGI 版本STL。
3.vector访问及遍历操作
这三种遍历方式大致上和string类是一样的
1.元素访问——下标
| 常用函数 | 说明 |
| operator[ ] | 支持下标访问，返回对位于字符串中pos位置的元素的引用。 |
| front | 返回对vector容器中第一个元素的引用。 |
| back | 返回对vector容器中最后一个元素的引用。 |
| at | 支持下标访问，返回对位于字符串中pos位置的元素的引用。 |
void test_vector2() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //方式1 ----- operator[ ] for (size_t i = 0; i < v1.size(); i++) { cout << v1[i] << " ";// v1[i] 等价于 v1.operator[](i) v1[i] += 1;//修改 } cout << endl; for (size_t i = 0; i < s1.size(); ++i) { s1.at(i) += 1; } }
operator[ ] 和 at 的效果是一样的，两者区别在于检查机制：
operator[ ]：当发生越界访问时，会直接assert报错；
at：当发生越界访问时，会直接抛异常
2. 元素访问——迭代器
void test_vector2() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //方式2 ----- 迭代器（在C++中凡是使用迭代器，都是左闭右开区间） vector<int>::iterator it = v1.begin(); while (it != v1.end()) { *it -= 1; cout << *it << " "; ++it; } cout << endl; }
3.元素访问——范围for
void test_vector2() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //方式3 ----- 范围for for (auto e : v1) { cout << e << " "; } cout << endl;; }
4.vector的增删查改
void test_vector3() { vector<int> v1; vector<int> v2(4,8); v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(5); v1.push_back(6); //查找---在vector里没有find函数 vector<int>::iterator ret = find(v1.begin(), v1.end(), 3); //auto ret = find(v1.begin(), v1.end(), 3); if (ret != v1.end()) { cout << "找到了" << endl; v1.insert(ret, 30); //在ret的前面插入30 v1.insert(ret, 3, 40); //在ret的前面插入3个40 v1.insert(ret, v2.begin(), v2.end()); //在ret前面插入v2的迭代器区间 } v1.insert(v1.begin(), 10); //在v1的起始迭代器前插入10（相当于头插） v1.insert(v1.end(), 20); //在v1的末尾迭代器前插入10（相当于尾插） vector<int>::iterator pos = find(v1.begin(), v1.end(), 3); if (pos != v1.end()) { v1.erase(pos); // 删除pos位置的元素 } v1.erase(v1.begin() + 2, v1.end() - 3); // 删除一部分元素 for (auto e : v1) { cout << e << " "; } cout << endl; v1.clear(); //清空数据 }
在vector中并没有find函数，但是在string类当中却有，这是为什么呢？
因为vector本身作为数组，对于查找的需求比较简单，不想string类那样需要查找子串，我们可以直接使用算法库当中的find函数（使用前需要包#include <algorithm>头文件）。
库中的代码实现：
返回范围[first,last]中第一个与val比较相等的元素的迭代器，如果没有找到这样的元素，则返回last。
template<class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val) { while (first!=last) { if (*first==val) return first; ++first; } return last; }
三、牛刀小试
链接：https://leetcode.cn/problems/single-number/
class Solution { public: int singleNumber(vector<int>& nums) { int n = 0; for(auto e : nums) { n ^= e; //让数组中的每个数异或一下，相同的数异或为0 } return n; //或 /* for(int i = 0;i < nums.size();++i) { n ^= nums[i]; } return n; */ } };
本篇博客还一个比较重要的知识点：迭代器试下的问题。将会在下一期的博客中更新，对于vector的相关练习也会陆续更新
