vector

vector的说明文档

1. vector是表示可变大小数组的序列容器(动态顺序表)。
2. 就像数组一样，vector也采用连续的存储空间来储存元素。这就意味着可以用下标对vector的元素进行访问，和数组一样高效。与数组不同的是，它的大小可以动态改变——由容器自动处理。
3. 底层而言，vector使用动态分配的数组来存储元素。当新元素插入时，这个数组可能需要被重新分配大小(扩容)。其做法为，分配一个新的数组，然后将所有元素移到这个新数组。就时间成本而言，这是一个代价较高的行为，因此不会在每次向容器添加元素时都重新分配大小。
4. vector会分配一些额外的空间以应对可能需要的扩容，因此容器的实际容量大小可能大于容纳其元素所必须的存储空间的大小。不同的库采用不同的策略来权衡空间的使用(usage)与重新分配(reallocation)。但在任何情况下，重新分配都应该只发生在对数增长的大小间隔上，以使得尾插一个元素的时间复杂度为常数。
5. 因此，相较于数组，vector占用了更多的存储空间以获得管理存储空间的能力，并以一种高效率的方式动态增长。
6. 与其它动态序列容器相比（deque(双端队列),lists(双链表),forward_lists(单链表)）， vector在访问其元素时非常高效(就像数组一样)，而且从其末端添加或删除元素时也相对高效。对于在末端以外的位置插入或删除元素的操作，它的效率较低。而且与list和forward_lists相比，它的迭代器与引用不太一致。

string是负责管理字符类型的数组，而vector是负责管理任意类型的数组 。
string相比vector有太多冗余的接口，vector的设计相对更合理些。

vector构造函数

vector构造函数	接口说明
vector()（重点）	无参构造
vector (const vector& x); （重点）	拷贝构造
vector（size_type n, const value_type& val = value_type())	构造并初始化n个val
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

vector容量管理

接口	接口说明
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空

1. capacity的代码在vs和g++下分别运行可以发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。vector每次增容增多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
2. reserve只负责开辟空间。如果明确知道需要用多少空间，可使用reserve来缓解vector增容代价较高的问题。
3. resize在开空间的同时还会进行初始化，影响size。

vector增删查改

接口	接口说明
push_back	（重点） 尾插
pop_back	（重点） 尾删
operator[]	（重点） 像数组一样访问
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间

vector迭代器

接口	接口说明
begin +end（重点）	获取第一个元素位置的iterator/const_iterator， 获取最后一个元素的下一位的iterator/const_iterator
rbegin + rend	获取最后一个元素位置的reverse_iterator，获取第一个元素前一位的reverse_iterator

vector 迭代器失效问题(重点)

1. 迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际上就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。
2. 而迭代器失效，实际上就是迭代器底层所对应的指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果便是程序崩溃(即，若继续使用已经失效的迭代器，程序可能会崩溃)。

===
对于vector，可能会导致其迭代器失效的操作有：
1.会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

2.指定位置元素的删除操作–erase

3.注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

-SGI STL中，迭代器失效后，代码不一定会崩溃，但运行结果肯定不
对。若it不在begin和end范围内，肯定会崩溃。

4.与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

模拟实现vector

#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>
using namespace std;namespace my_vector {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;vector(){}vector(size_t n, const T& val = T()) /*由于要兼容所有类型，缺省值不能为0，而是调默认构造函数构造匿名对象*/{reserve(n);for (size_t i = 0; i < n; ++i) {push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; ++i) {push_back(val);}}//复用实现深拷贝/*vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}*///原生方式实现深拷贝vector(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//memcpy是浅拷贝，不适用于自定义类型for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}template<class InputIterator>//允许类的成员函数本身是函数模板vector(InputIterator first, InputIterator last)/*迭代器区间 [first,last)*/{while (first != last) {//这里不能比较大小，有的结构，如链表，前后节点的地址大小关系并不确定push_back(*first);++first;}}~vector() {delete[] _start;_start = _finish = _end_of_storage = nullptr;}iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const {return _start;}const_iterator end() const {return _finish;}void resize(size_t n, T val = T()) {//由于要兼容所有类型，缺省值不能为0，而是调默认构造函数构造匿名对象 if (n < size()) {_finish = _start + n;//等效于删除数据}else {if (n > capacity()) {reserve(n);while (_finish != _start + n) {*_finish = val;++_finish;}}}}void reserve(size_t n) {if (n > capacity()) {size_t sz = size();//提前记录sizeT* tmp = new T[n];if (_start) {//memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝，不适用于自定义类型for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;//size()返回的是_finish - _start ,这里用size()的话会变成_finish=_start+_finish-_start ,_finish会变成0 ,只能用提前记录的sz_end_of_storage = _start + n;}}size_t capacity() const {return _end_of_storage - _start;}size_t size() const {return _finish - _start;}bool empty() {return _start == _finish;}T& operator[](size_t pos) {assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];}void push_back(const T& x) {if (_finish == _end_of_storage) {//容量检查reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back() {assert(!empty());//确保非空--_finish;}iterator insert(iterator pos, const T& val) {assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage) {//容量检查size_t len = pos - _start;//为防迭代器失效，需要在扩容前记录pos到_start的相对距离，以便在扩容后更新pos位置。reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//扩容后用记录的相对距离更新pos位置，避免pos位置错误导致的迭代器失效(野指针型)}iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos) {assert(pos >= _start);assert(pos < _finish);//pos不能等于_finishiterator start = pos + 1;while (start != _finish) {//挨个往前挪*(start - 1) = *start;++start;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};//===========类分隔线===========void func(const vector<int>& v) {cout << endl;for (size_t i = 0; i < v.size(); ++i) {cout << v[i] << " ";}cout << endl;vector<int>::const_iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;cout << endl;}void test_vector1() {vector<int> v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);func(v1);for (size_t i = 0; i < v1.size(); ++i) {cout << v1[i] << " ";}cout << endl;v1.pop_back();v1.pop_back();vector<int>::iterator it = v1.begin();while (it != v1.end()) {cout << *it << " ";++it;}cout << endl;for (auto e : v1) {cout << e << " ";}cout << endl;}template<class T>void f() {T x = T();cout << x << endl;}void test_vector2() {//虽然内置类型理论上没有构造函数，但为兼容模板，一般支持像自定义类型一样用构造函数//int i = int();//会初始化为0//int j = int(1);//会初始化为1f<int>();f<int*>();f<double>();}void test_vector3() {vector<int> v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);v1.resize(3);func(v1);}void test_vector4() {vector<int> v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);//v1.push_back(4);//*v1.insert(v1.begin(), 9);auto pos = find(v1.begin(), v1.end(), 2);if (pos != v1.end()) {//pos = v1.insert(pos, 50);v1.insert(pos, 50);}//insert后的pos默认看作已失效(野指针)，不能再使用，因为位置关系变了for (auto e : v1) {cout << e << " ";}cout << endl;}void test_vector5() {vector<int> v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1) {cout << e << " ";}cout << endl;auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.end()) {v1.erase(pos);}//类似于insert后，erase后pos也视作失效(野指针),因为位置关系也变了//(比如pos指向最后一个元素，erase这个元素后pos就指向了_finish，不再指向合法位置)//(*pos)++;//vs下会被检查到然后报错，linux下g++不检查但还是可能会出问题(行为结果未定义，与具体编译器实现有关)//string也会有迭代器失效的情况，但string的erase和insert更常用下标而不是迭代器，故问题不算明显。for (auto e : v1) {cout << e << " ";}cout << endl;}void test_vector6() {vector<int> v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1) {cout << e << " ";}cout << endl;//删除所有偶数:迭代器适合删除vector<int>::iterator it = v1.begin();while (it!=v1.end()){if (*it % 2 == 0) {it = v1.erase(it);//迭代器erase后失效，接收返回值以更新pos}else {++it;//迭代器未失效，正常++}}for (auto e : v1) {cout << e << " ";}cout << endl;}void test_vector7() {//vector<int> v1(10u, 5);//u表示无符号vector<int> v1(10, 5);for (auto e : v1) {cout << e << " ";}cout << endl;vector<int> v2(v1.begin() + 1, v1.end() - 1);for (auto e : v2){cout << e << " ";}cout << endl;std::string s1("hell word");vector<int> v3(s1.begin(), s1.end());for (auto e : v3){cout << e << " ";}cout << endl;int arr[] = {1,2,60,3,4,5};vector<int> v4(arr, arr + 4);for (auto e : v4){cout << e << " ";}cout << endl;v1.insert(v1.begin(), 8);for (auto e : v1){cout << e << " ";}cout << endl;sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : arr){cout << e << " ";}cout << endl;sort(arr, arr + sizeof(arr) / sizeof(int), greater<int>());//sort默认升序。除了能对迭代器的区间排序，还可以对数组排序。for (auto e : arr){cout << e << " ";}cout << endl;}void test_vector8(){vector<int> v1(10, 5);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1);for (auto e : v2){cout << e << " ";}cout << endl;vector<std::string> v3(3, "123456789123456789");for (auto e : v3){cout << e << " ";}cout << endl;vector<std::string> v4(v3);for (auto e : v4){cout << e << " ";}cout << endl;v4.push_back("1111111111");v4.push_back("2222222222");v4.push_back("3333333333");for (auto e : v4){cout << e << " ";}cout << endl;}}