---

一、vector的介绍

1、vector是表示可变大小数组的序列容器。
2、vector就像数组一样，也采用的连续空间来存储元素，这也意味着可以采用下标对vector的元素进行访问。
3、vector与普通数组不同的是，vector的大小是可以动态改变的。
4、当vector需要重新分配大小时，其做法是，分配一个新的数组，然后将全部元素移到这个数组当中，并释放原来的数组空间。
5、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因此存储空间比实际需要的存储空间一般更大。不同的库采用不同的策略权衡空间的使用和重新分配，以至于在末尾插入一个元素的时候是在常数的时间复杂度完成的。
6、由于vector采用连续的空间来存储元素，与其他动态序列容器相比，vector在访问元素的时候更加高效，在其末尾添加和删除元素相对高效，而对于不在其末尾进行的删除和插入操作效率则相对较低。

值得注意的是，vector不管在实现方式上还是在用法上和string都非常像，不过它们之间还是有区别的，string类是一个保存字符的动态数组，由于其中有一个接口c_str，可以将其转化成c语言的字符串，要以\0结尾，所以string类最后会有一个\0。
vector<T>是一个保存T类型的动态数组，vector<char>也是保存字符的动态数组，但是，不会以\0结尾，不保存\0。

它们两个的本质都是一个顺序表。头文件iostream中并不包含vector，因此使用时要加头文件<vector>

---

二、常用接口

2.1. 构造函数

默认构造

构造一个某类型的空容器：

explicit vector (const allocator_type& alloc = allocator_type());

缺省参数allocator，它是用于指定要使用的空间配置器的，STL提供的默认的空间配置器，我们基本不用管这个参数，除非是我们自己实现了一个空间配置器，然后希望使用我们自己写的空间配置器。

vector<int> v; //构造int类型的空容器

半缺省构造

构造一个含有n个val（val默认为0）的某类型容器：

explicit vector (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());

vector<int> v2(10, 1); //构造含有10个1的int类型容器

拷贝构造

vector (const vector& x);

迭代器构造

使用迭代器拷贝构造某一段内容：

template <class InputIterator>vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());

该方式也可用于拷贝其他容器的某一段内容，这是因为vector的成员函数是模板函数，只要迭代器解引用后和vector实例化后的类型是一致的就可以进行传参：

string s("hello world");
vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容

2.2. 元素访问方式

[ ]下标访问

vector当中实现了 [ ] 操作符的重载，因此我们也可以通过“下标+[ ]”的方式对容器当中的元素进行访问。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v(10, 1);//使用"[]下标”的方式遍历容器for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;return 0;
}

迭代器和范围for访问

编译器会自动将范围for替换为迭代器的形式，vector是支持迭代器的，所以我们还可以用范围for对vector容器进行遍历：

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v(10, 1);//范围forfor (const auto& e : v){cout << e << " ";}cout << endl;//迭代器vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;return 0;
}

范围for的本质是将v的内容取出来拷贝给e，如果vector是内置类型的消耗很小，但如果其内容是string类型的会发生深拷贝，产生巨大消耗，因此需要引用传参。

2.3. 空间增长函数

size()和capacity()

size()函数获取当前容器中的有效元素个数，通过capacity()函数获取当前容器的最大容量。

reserve()和resize()

void reserve (size_type n);
void resize (size_type n, value_type val = value_type());

通过reserse()函数改变容器的最大容量，resize()函数改变容器中的有效元素个数。

reserve规则：
 1、当所给值大于容器当前的capacity时，将capacity扩大到该值。
 2、当所给值小于容器当前的capacity时，什么也不做。
resize规则：
 1、当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
 2、当所给值小于容器当前的size时，将size缩小到该值。

capacity增容规则

#include <iostream>
#include <vector>
int main()
{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倍增长的。
这是因为vs是PJ版本STL，g++是SGI版本STL。
C++标准委员会只是规定了，一个容器的名称、应该提供哪些接口，并没有规定接口的底层的实现方法。因此，不同的编译器提供的接口底层实现方法有可能是不同的，这是实现者的自由。
至于为什么是扩容1.5倍或2倍，则是因为设计者的考虑。扩容的倍数越高，扩容的频率就越低，同时有可能浪费的空间容量就越大。 如果确定要多少空间，我们可以通过reserve/resize提前将空间给开辟好

2.4. 增删查改的接口

push_back和pop_back

容器的尾插和尾删，值得注意的是，vector并没有提供头插和头删，因为头插和头删的效率比较低（要向后移动元素），不过头插和头删可以采用inset和erase实现。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;v.push_back(1); //尾插元素1v.push_back(2); //尾插元素2v.push_back(3); //尾插元素3v.push_back(4); //尾插元素4v.pop_back(); //尾删元素v.pop_back(); //尾删元素v.pop_back(); //尾删元素v.pop_back(); //尾删元素return 0;
}

insert和erase

//在pos位置插入val，返回val的位置
iterator insert (iterator position, const value_type& val);//在pos位置插入n个val
void insert (iterator position, size_type n, const value_type& val);//在pos位置插入一段区间
template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);

//删除pos位置的元素，返回值是pos位置的下一个元素的迭代器
iterator erase (iterator position);
//删除一段区间，返回值是这段区间的下一个元素的迭代器
iterator erase (iterator first, iterator last);

find函数

template <class InputIterator, class T>InputIterator find (InputIterator first, InputIterator last, const T& val);

find函数共三个参数，前两个参数确定一个迭代器区间（左闭右开），第三个参数确定所要寻找的值。
find函数在所给迭代器区间寻找第一个匹配的元素，并返回它的迭代器，若未找到，则返回所给的第二个参数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在2的位置插入10pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器v.erase(pos); //删除3return 0;
}

swap

swap函数可以交换两个容器的数据空间，实现两个容器的交换。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v1(10, 1);vector<int> v2(10, 2);v1.swap(v2); //交换v1,v2的数据空间return 0;
}

2.5. 迭代器

begin和end

begin()函数返回容器中第一个元素的正向迭代器，end()函数返回容器中最后一个元素的后一个位置的正向迭代器。

rbegin和rend

rbegin()函数返回容器中最后一个元素的反向迭代器，rend()函数返回容器中第一个元素的前一个位置的反向迭代器。

---

三、vector迭代器失效的问题

实例一：

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{v.erase(it);}it++;}return 0;
}

迭代器访问到了不属于容器的内存空间，导致程序崩溃：

不仅如此，而且在迭代器遍历容器中的元素进行判断时，并没有对1、3、5元素进行判断。

除此之外，当原来的空间被释放，原来的迭代器就指向了一块已经被释放的空间。

实例二：

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v(10,0);v[1] = 10;auto pos = find(v.begin(), v.end(),10);v.insert(pos, 0);v.erase(pos); return 0;
}

3.1. 迭代器失效解决方法

每次使用前，对迭代器进行重新赋值就可以解决这个问题。

对于实例一，我们可以接收erase函数的返回值（erase函数返回删除元素的后一个元素的新位置）。并且控制代码的逻辑：当元素被删除后继续判断该位置的元素（因为该位置的元素已经更新，需要再次判断）。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{it = v.erase(it); //删除后获取下一个元素的迭代器}else{it++; //是奇数则it++}}return 0;
}

对于实例二，可以在删除之前再次重新查找一遍。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v(10,0);v[1] = 10;auto pos = find(v.begin(), v.end(),10);v.insert(pos, 0);pos = find(v.begin(), v.end(), 10); //获取值为2的元素的迭代器v.erase(pos); return 0;
}

---

四、vector模拟实现

vector中有三个成员变量：

private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endofStorage; // 指向存储容量的尾

在vector当中有三个成员变量_start、_finish、_endofstorage。
_start指向容器的头，_finish指向容器当中有效数据的尾，_endofstorage指向整个容器的尾。

4.1. 构造函数

默认构造和半缺省构造

vector(int size=0, T val = T()): _start(nullptr), _finish(nullptr), _endofStorage(nullptr)
{assert(size >= 0);if (size>0){_start = new T[size];if (_start){for (size_t i = 0; i < size; ++i)_start[i] = val;}_finish = _start + size;_endofStorage = _start + size;}
}

迭代器构造

template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofStorage(nullptr)
{//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);first++;}
}

拷贝构造函数

拷贝构造函数的传统写法：

//现代写法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofStorage(nullptr)
{reserve(v.capacity()); //开辟与v相同的空间for (auto e : v) //将容器v当中的数据一个个尾插过来{push_back(e);}
}//也可以采用这种写法
//vector(const vector<T>& v)
//:_start(nullptr)
//, _finish(nullptr)
//, _endofStorage(nullptr)
//{//拷贝构造
//	_start = new T[v.capacity()];
//	size_t size = v.size();
//	if (_start)
//	{
//		for (size_t i = 0; i < size; ++i)//不能使用memcpy
//			_start[i] = v._start[i];
//	}
//	_endofStorage = _start + v.capacity();
//	_finish = _start + v.size();
//}

注意这里不能使用memcpy来拷贝数据，因为memcpy是浅拷贝，当vector中的类型为string等数据时，则需要使用深拷贝来完成（这里就是string自己的=赋值运算符重载）。

析构函数

~vector() {if (_start)delete[]_start;_start = _finish = _endofStorage = nullptr;
}

赋值运算符重载函数

vector<T>& operator=(vector<T> v) //拷贝构造一个形参
{swap(v); //交换这两个对象return *this; //支持连续赋值
}//也可以采用这种写法
//vector<T>& operator=(const vector<T>& v)
//{
//	if (this != &v) //防止自己给自己赋值
//	{
//		delete[] _start; //释放原来的空间
//		_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
//		for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
//		{
//			_start[i] = v[i];
//		}
//		_finish = _start + v.size(); //容器有效数据的尾
//		_endofStorage = _start + v.capacity(); //整个容器的尾
//	}
//	return *this; //支持连续赋值
//}

4.2. 迭代器

// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;

begin()和end()

iterator begin()
{return _start; //返回容器的首地址
}
iterator end()
{return _finish; //返回容器当中有效数据的下一个数据的地址
}
const_iterator begin()const
{return _start; //返回容器的首地址
}
const_iterator end()const
{return _finish; //返回容器当中有效数据的下一个数据的地址
}

4.3. 容量函数

size()和capacity()

size_t size()const
{return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{return _endofStorage - _start; //返回当前容器的最大容量
}

reserve

void reserve(size_t n)
{if (n > capacity()) //判断是否需要进行操作{size_t sz = size(); //为了防止_finish失效，先记录当前容器当中有效数据的个数T* tmp = new T[n]; //开辟空间if (_start) //判断是否为空容器{for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中{tmp[i] = _start[i];}delete[] _start; //将容器本身存储数据的空间释放}_start = tmp; //将tmp所维护的数据交给_start进行维护_finish = _start + sz; //容器有效数据的尾_endofStorage = _start + n; //容器的尾}
}

resize

void resize(size_t n, const T& val = T())
{if (n < size()) //当n小于当前的size时{_finish = _start + n; //将size缩小到n}else //当n大于当前的size时{if (n > capacity()) //判断是否需要增容{reserve(n);}while (_finish < _start + n) //将size扩大到n{*_finish = val;_finish++;}}
}

empty

bool empty()const
{return _start == _finish;
}

4.4. 增删查改

push_back

//尾插数据
void push_back(const T& x)
{if (_finish == _endofstorage) //判断是否需要增容{size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容}*_finish = x; //尾插数据_finish++; //_finish指针后移
}

pop_back

//尾删数据
void pop_back()
{assert(!empty()); //容器为空则断言_finish--; //_finish指针前移
}

insert

//插入
iterator insert(iterator pos, const T& x) {if (_finish == _endofStorage) {size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}size_t inpos = pos - _start;//保存一份相对位置，防止迭代器失效pos = _start + inpos;iterator last = _finish;while (last != pos){//往后挪动*last = *(last - 1);last--;}*pos = x;_finish++;return pos;//返回pos指向新插入元素的位置
}

erase

//删除
iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);iterator temp_pos = pos;//保存原来pos的位置while (pos < _finish - 1)//将pos后面的元素往前移{*pos = *(pos + 1);pos++;}_finish--;return temp_pos;//返回原来的位置
}

swap

swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

//交换两个容器的数据
void swap(vector<T>& v)
{//交换容器当中的各个成员变量std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofStorage, v._endofStorage);
}

4.5. 元素访问函数

operator[ ]

T& operator[](size_t i)
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}
const T& operator[](size_t i)const
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}

---

附录

namespace hjl
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//构造和半缺省构造vector(int size=0, T val = T()): _start(nullptr), _finish(nullptr), _endofStorage(nullptr){assert(size >= 0);if (size>0){_start = new T[size];if (_start){for (size_t i = 0; i < size; ++i)_start[i] = val;}_finish = _start + size;_endofStorage = _start + size;}}//迭代器构造template<class InputIterator> //模板函数vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofStorage(nullptr){//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);first++;}}void swap(vector<T>& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofStorage, x._endofStorage);}//拷贝构造vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofStorage(nullptr){_start = new T[v.capacity()];size_t size = v.size();if (_start){for (size_t i = 0; i < size; ++i)_start[i] = v._start[i];}_endofStorage = _start+v.capacity();_finish = _start + v.size();}//重载=vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数{swap(v); //交换这两个对象return *this; //支持连续赋值}~vector() {if (_start)delete[]_start;_start = _finish = _endofStorage = nullptr;}// capacitysize_t size() const {return _finish - _start;}size_t capacity() const {return _endofStorage - _start;}bool empty() const {return _start == _finish;}//重载[]T& operator[](size_t i){assert(i < size());return _start[i];}void reserve(size_t n) {if (n > capacity()) {size_t oldSize = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_endofStorage = _start + n;}}void resize(size_t n,T val=T()) {//调用默认匿名对象的构造函数if (n < size()){_finish = _start + n;}else {if (n > capacity()) {reserve(n);//n比capacity大时先增容}//end ifwhile (_finish < _start + n) {*_finish = val;_finish++;}//end while}//end else}//尾插void push_back(const T& x) {if (_finish == _endofStorage) {size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;_finish++;}//尾删void pop_back() {assert(!empty());_finish--;}//插入iterator insert(iterator pos, const T& x) {if (_finish == _endofStorage) {size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}size_t inpos = pos - _start;//保存一份相对位置，防止迭代器失效pos = _start + inpos;iterator last = _finish;while (last != pos){//往后挪动*last = *(last - 1);last--;}*pos = x;_finish++;return pos;//返回pos指向新插入元素的位置}//删除iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);iterator temp_pos = pos;while (pos < _finish - 1)//将pos后面的元素往前移{*pos = *(pos + 1);pos++;}_finish--;return temp_pos;//返回原来的位置}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endofStorage; // 指向存储容量的尾};}