1.vector的介绍及使用
1.1 vector的介绍
vector是STL容器中的一种常用的容器，和数组类似，由于其大小(size)可变，常用于数组大小不可知的情况下来替代数组。
vector也是一种顺序容器，在内存中连续排列，因此可以通过下标快速访问，时间复杂度为O(1)。但是，连续排列也意味着大小固定，数据超过vector的预定值时vector将自动扩容。
1.2 vector的使用
在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。
1.2.1 vector的定义
| (constructor)构造函数声明 | 接口说明 |
|---|---|
| vector()（重点） | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
举例：
#include<iostream> #include<vector> using namespace std;int main() {vector<int>v1;vector<int>v2(5,5);vector<int>v3(v2);vector<int>v4(v2.begin(), v2.end());return 0; }结果：
1.2.2 vector iterator 的使用
| iterator的使用 | 接口说明 |
|---|---|
| begin + end（重点） | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下 一个位置的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置 的reverse_iterator |
举例：
void test2() {vector<int>v2(5, 5);vector<int>::iterator it = v2.begin();while (it != v2.end()){cout << *it << " ";it++;} }结果：
1.2.3 vector 空间增长问题
| 容量空间 | 接口说明 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
a）capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2 倍增长的。不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
通过下面一段代码来演示：
void test3() {size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}} }vs下的结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
g++运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
b）reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
举例：
void test4() {vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}} }结果：
c）resize在开空间的同时还会进行初始化，影响size。
1.2.3 vector 增删查改
| vector增删查改 | 接口说明 |
|---|---|
| push_back（重点） | 尾插 |
| pop_back （重点） | 尾删 |
| find | 查找。（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] （重点） | 像数组一样访问 |
push_back和pop_back演示：
void test5() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl;v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl; }结果：
find（这个是算法里面的函数，需要配合迭代器使用）演示：
void test6() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;vector<int>::iterator pos=find(v.begin(), v.end(), 3);cout << pos-v.begin() <<endl; }结果：
find函数第一个参数是迭代器的起始位置，第二参数是结束位置，第三个是寻找的对象，找到则返回第一次找到该对象位置的迭代器，否则返回结束位置。
insert和erase演示：
void test7() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;v.insert(v.begin() + 2, 10);for (auto& e : v){cout << e << " ";}cout << endl;v.erase(v.end()-1);for (auto& e : v){cout << e << " ";}cout << endl; }结果：
这个第一个参数都是需要传迭代器来确定需要插入，或删除的位置。
swap演示：
void test8() {vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2;v2.push_back(5);v2.push_back(4);v2.push_back(3);v2.push_back(2);v2.push_back(1);cout << "v1:";for (auto& e : v1){cout << e << " ";}cout << endl;cout << "v2:";for (auto& e : v2){cout << e << " ";}cout << endl;v1.swap(v2);cout << "v1:";for (auto& e : v1){cout << e << " ";}cout << endl;cout << "v2:";for (auto& e : v2){cout << e << " ";}cout << endl; }结果：
operator[]演示：
void test9() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl; }结果：
2.vector深度剖析及模拟实现
vector在底层实现中，其实类里面并不是像小编之前数据结构中，那样有三个成员：T* arr，size_t size，size_t capacity，而是T* _start,T* _finish,T* end_of_storage。
_start表示有效元素开始的迭代器位置，_finish表示有效元素结束下一个迭代器位置，_end_of_storage表示空间大小结束下一个迭代器位置。
2.1实现默认构造函数
这里为了和STL库里面的vector区分用命名空间进行隔离，这里利用缺省参数，初始化列表进行初始化：
namespace iu
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(){}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage= nullptr;};
}2.2析构函数
~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}2.3元素个数size(),空间大小capacity()
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}2.4迭代器实现begin(),end()
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}这里需要重载const修饰的类型，如果是元素类型是const例如：const T，以及范围for使用时对象是const修饰时，就需要重载这种const的end(),begin(),才能使用。
2.5重载[]
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}这里也需要重载const修饰的类型，和上面begin(),end()实现的原因是一样的。
2.6 开辟空间大小void reserve(size_t n)
void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];//注意这里不能使用memcpy(tmp,_start,sizeof(T)*oldsize)来赋值for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}这里首先判断n是否大于capacity()，如果小于就不做处理，大于就需要扩容，这里需要保存size()大小，如果将tmp赋给_start时，这是_start已经更新，再利用size()去确定_finish就会有问题。
其次就是不能用memcpy来赋值
用下面的例子来解释：
int main() {iu::vector<string> v1;v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");for (const auto& e : v1){cout << e << endl;}cout << endl;return 0; }结果：
这里是为什么？这里空间大小不够，所以要扩容，其实是memcpy浅拷贝导致的，这里delete[]释放空间之后，但是浅拷贝，还是指向原来的释放的空间，再去访问就是野指针，就出错了。
2.7 控制元素个数void resize(size_t n,const T& val=T())
void resize(size_t n,const T& val=T())
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}
}首先判断是否小于size()，小于就直接将_finish位置向前调整即可，大于就需要先扩容，因为在前面实现的reserve中有判断是否需要扩容，所以这里直接将n传给reverse，自然会判断，然后再将增加的元素个数，初始化为val，调整_finish位置。
2.8 插入元素iterator insert(iterator pos, const T& x)
iterator insert(iterator pos, const T& x)
{assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage)//更新迭代器{size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;return pos;
}这里首先判断空间是否已满，满了需要扩容，再插入，这里和前面reserve有相同的问题，扩容之后，_start指向一块新的空间，但pos还是指向原来释放掉的空间，所以需要更新迭代器，确定原来len，再更新pos，在将pos及之后的数据依次向后移动一位，再插入x,返回pos位置。
2.9 删除元素iterator erase(iterator pos)
iterator erase(iterator pos)
{assert(pos <= _finish && pos >= _start);auto it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}--_finish;return pos;
}直接将pos+1位置的数据都向前移动一位，实现数据覆盖，然后_finish--就相当于删除pos位置元素，返回pos位置。
2.10 尾插void push_back(const T& val = T())，尾删void pop_back()
void push_back(const T& val = T())
{insert(end(), val);
}
void pop_back()
{assert(size() > 0);--_finish;
}这里尾插直接复用insert函数，第一个参数直接传end()位置的迭代器，第二传插入的元素，尾删直接_finish--就行了。
2.11 拷贝构造函数
vector(const vector<T>& v)
{reserve(v.size()); for (auto e : v){push_back(e);}
}this开辟和v一样大的元素个数相等的空间大小，再将v中的元素，依次尾插到this中。
2.12 赋值运算符重载
void swap(vector<int>& v)
{std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}这里利用前面（string）中讲的现代写法，利用swap函数,注意这里形参，不能传引用，如果传引用，交换后会影响实参，这里传参走拷贝构造给v，出了作用域会销毁，不会影响实参。
2.13 其他几种构造函数
2.13.1vector(int n, const T& value = T())
vector(int n, const T& value = T())
{resize(n, value);
}这里直接调用resize，就可以了，resize里面有扩容，并赋值操作，直接复用就行了。
2.13.2 vector(InputIterator first, InputIterator last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{size_t i= 0;while(first!=last){push_back(*first);first++;}
}这是利用迭代器初始化，将frist到last位置，依次尾插到this即可。
举例：
void test6() {iu::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto& e : v1){cout << e << " ";}cout << endl;iu::vector<int>v2(v1.begin()+2,v1.end());for (auto& e : v2){ cout << e << " ";} }结果：
2.13.3 vector(std::initializer_list<T> it)
vector(std::initializer_list<T> it)
{reserve(it.size());for (auto e : it){push_back(e);}
}首先this开辟和it一样大的元素个数相等的空间大小，再将it中的元素，依次尾插到this中。这个initializer_list类型，可以类似于数组。
举例：
void test6() {iu::vector<int>v1 = {1,2,3,4,5,6};for (auto& e : v1){cout << e << " ";}cout << endl; }结果：
3.迭代器失效问题讨论
3.1插入
看下面这段代码：
int main() {std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);auto it = v1.begin() + 2;// insert以后，默认迭代器都失效了，不要使用v1.insert(it, 10);cout << *it << endl; }结果：
注意这里问题是，空间大小为4，再插入就需要扩容，扩容之后，it还指向原来的位置，但扩容之后，_start位置已经改变，相当于it为野指针，就失效了，但如果不扩容的话，有些编译器可以通过，可能正确，但不能去以编译器为准，就默认insert之后迭代器就失效了，要再用就重新初始化。
3.2 删除
看下面这段代码：（删除所有的偶数）
void test9() {std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (const auto& e : v1){cout << e <<" ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl; }结果：
这里编译器vs会直接报错，因为在vs下检查非常严格，只要是erase，insert之后编译器直接就失效了，虽然vs下并不会缩容，但也会报错，如果在要缩容的编译器下，那肯定也是失效了，这里需要更新迭代器。
改进后：
void test9() {iu::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (const auto& e : v1){cout << e <<" ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it=v1.erase(it);//每删除一次就更新一次迭代器}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl; }结果：
![[Computer Vision]实验二：图像特征点提取](https://i-blog.csdnimg.cn/direct/48c56455f7ec47d886e045a0e1e0a251.png)