C++STL系列之vector
前言
vector是变长数组，有点像数据结构中的顺序表，它和list也是经常被拿出作对比的， vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小，如果扩容，因为要开一个新数组把旧元素挪过来，消耗很大，所以扩容一般是扩二倍或者1.5倍。
vector的模拟也可以像string一样来实现，但是SGI下源码用的是三个迭代器，后面会具体讲。
一、vector类以及常用接口和函数
1.构造函数
和string基本一样
2.迭代器
发现也一样，因为双向迭代器在C++11后都是四个迭代器，具体使用也没啥说的，简单示范一下，遍历容器：
vector<int> v = {1,2,3,4};
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << ' ';it++;
}
有模板以后，类名不再是类型名，vector< T >才是类型名
3.容量方面
和string基本一样。
vs下是1.5倍扩容，而g++下是2倍扩容，vs是PJ版本STL，g++是SGI版本STL。
4.重要函数
一眼瞅过去和string基本一样，这里emplace系列在C++11中已经讲完了不再提。主要改变是insert和erase，从string之后，所有的insert和erase基本上都只支持迭代器插入/删除。
返回值也是迭代器，解决迭代器失效的问题，后面谈。
5.二维数组
vector<vector<int>> vv;//这就是一个二维数组。每一维放的是vector<int>
二、迭代器失效问题
想知道这个先知道一个问题：vector的迭代器是什么样的？和string类似，
typedef T* iterator;
typedef const T* const_iterator;
先看迭代器失效的一些场景：
erase掉偶数
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){v.erase(it);}++it;
}
在一个位置反复insert
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
int n = 10;
while (n--)
{v.insert(it, 10);
}
这两份代码在vs下都崩溃了。
只要涉及到底层空间的改变都有可能会导致迭代器失效。
为什么会失效呢？
以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，下一步使用时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。
关于erase
erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
Linux下检查和处理都没有vs更加严格和极端，可能不会崩溃，但是结果都是未定义的，所以我们要学会正确的使用迭代器。
解决方案：
库里的实现均带有返回值，返回最新位置的迭代器，想上面那么使用就可以拿it重新接受。
it = v.erase(it);
it = v.insert(it,30);
三、模拟实现
SGI下没有使用像string一样的 T * arr和size和capacity,他使用了三个迭代器（T*类型的三个指针),这样处理更加的方便，扩容方面，指针的计算也更有效率。
_start --充当T * arr;
_finish size()
_end_of_storage capacity();
构造：
push_back
看完这个push_back()就会明白很多，if判断是判断size等不等于capacity,++finish相当于++_size。
rerserve：
这个更加清晰，n是新的capacity的大小，start指向开始，finish指向tmp+size(),end_of_storage指向空间的结束。
OK，知道这些就好自己手搓了。
size和capacity
size_t capacity()const
{return _end_of_storage - _start;
}
size_t size()const
{return _finish - _start;
}
reserve
void reserve(size_t n)
{if (capacity() < n){size_t sz = size();//注意保存一下size，因为后面还需要计算finishT* tmp = new T[n];if (_start){for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}//memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}
迭代器：
iterator begin()
{return _start;
}
const_iterator begin()const
{return _start;
}
const_iterator end()const
{return _finish;
}
iterator end()
{return _finish;
}
insert：
后面的容器基本上都是写完insert之后复用insert，比如push_back，就是insert(end(),x);
insert的注意事项：就是扩容之后迭代器位置的改变，因为要返回新插入元素的迭代器。挪动数据这些都小菜一碟。
iterator insert(iterator pos,const T& x)
{assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage){size_t dx = pos - _start;size_t _capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(_capacity);//迭代器失效，reserve需要开一个新的空间再把原来的空间释放，finish和start都转移了//过去，但是pos还在原空间，变成了野指针pos = _start + dx;}//1 6 4 8 10//1 2 6 4 8 10iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}
erase：
iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}--_finish;return pos;
}
pop_back和push_back复用insert和erase即可。
resize
void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n;}//_size = 4,_capacity = 7 , 6 8else{reserve(n);for (size_t i = size(); i < n; ++i){_start[i] = val;}_finish = _start + n;}
}
各种构造：
vector(size_t n, const T& val = T())
{resize(n, val);
}
vector(int n, const T& val = T())
{resize(n, val);
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}
vector(std::initializer_list<T> il)
{T* tmp = new T[il.size()];for (size_t i = 0; i < il.size(); ++i){tmp[i] = *(il.begin() + i);}_start = tmp;_end_of_storage = _finish = _start + il.size();
}
vector(const vector<T>& ot)
{T* tmp = new T[ot.size()];for (size_t i = 0; i < ot.size(); ++i){tmp[i] = ot[i];}_start = tmp;_finish = _end_of_storage = _start + ot.size();
}
vector(vector<T>&& ot):_finish(nullptr),_start(nullptr),_end_of_storage(nullptr)
{swap(ot);
}
注意：拷贝构造通常只拷贝到size处，并非拷贝整个容量。
这里你可能会疑问，为什么用n个T元素构造vector有两个版本？一个传的size_t,一个int，正常不就是size_t吗，看下面这种情况：
10和3都是int类型，编译器会默认走最匹配的，这里InputIterator first, InputIterator last是一个类型更加匹配导致了编译错误，所以开一个vector(int n, const T& val = T())来防止这种情况的发生。
赋值运算符重载
operator = 的现代写法（string里面类似）
就是复用拷贝构造之后swap一下
vector<T>& operator=(const vector<T>& ot)
{if (&ot == this){return *this;}vector<T> tmp(ot);swap(tmp);return *this;
}
[]
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos)const
{assert(pos < size());return _start[pos];
}
个人gitee
四、浅拷贝的问题
如果你移动元素用的是memcpy，此时可能一些情况下程序就会崩溃。
分析：
- memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
所以：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
使用等于就可以，因为自定义类型会调用operator =，比如string类型就会调用operator=达到深拷贝的效果。
五、优缺点
vector主要对比的对象就是list
优点：
1.vector支持下标访问（[] 和 at），O(1)拿到元素，效率高
2.尾插效率很高
3.连续内存布局使 CPU 缓存命中率高，遍历速度快。
4.内存开销较list小，因为list内部需要存指针
缺点：
1.中间插入或者删除很低效，需要挪动数据。
2.迭代器插入和删除涉及到失效的问题
3.每次扩容开销很大
总结
vector用的也不少，需要多加练习。
关于反向迭代器，这个会在stack和queue的那篇博客来讲，因为他们的思想一样
明天更新list,stack,queue