1.c++stl库
目录
vector的介绍及使用
1.1vector的介绍
1. vector 是表示可变大小数组的序列容器。
2. 就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲， vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
4. vector 分配空间策略： vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此， vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（ deque, list and forward_list ）， vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list 和 forward_list统一的迭代器和引用更好。
使用 STL 的三个境界：能用，明理，能扩展 ，那么下面学习 vector ，我们也是按照这个方法去学习。
1.2vector的使用
vector的学习可在官网查看文档。vector在实际中非常的重要，在实际中我们熟悉常用地接口就可以，下面列出了哪些接口是要重点掌握的。
1.2.1vector的定义
1.2.2vector iterator的使用
1.2.3vector空间增长问题
1.capacity 的代码在 vs 和 g++ 下分别运行会发现， vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的 。
2.这个问题经常会考察，不要固化的认为， vector 增容都是 2 倍，具体增长多少是根据具体的需求定义 的。vs 是 PJ 版本 STL ， g++ 是 SGI 版本 STL 。
3.reserve 只负责开辟空间，如果确定知道需要用多少空间， reserve 可以缓解 vector 增容的代价缺陷问 题。
4.resize 在开空间的同时还会进行初始化，影响 size 。
1.2.4vector增删查改
1.2.5vector迭代器失效问题（重点）
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装 ，比如： vector 的迭代器就是原生态指针 T* 。因此 迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间 ，造成的后果是程序崩溃 ( 即 如果继续使用已经失效的迭代器， 程序可能会崩溃 ) 。
对于 vector 可能会导致其迭代器失效的操作有：
1. 会引起其底层空间改变的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、 assign、 push_back等。
2. 指定位置元素的删除操作 - -erase
erase删除 pos 位置元素后， pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代 器不应该会失效，但是：如果pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是 没有元素的，那么pos 就失效了。因此删除 vector 中任意位置上元素时， vs 就认为该位置迭代器失效了。
3.与vector 类似， string 在插入 + 扩容操作 +erase 之后，迭代器也会失效。
迭代器失效解决办法：
在使用前，对迭代器重新赋值即可。
2.vector的模拟实现源码
#include<iostream>
using namespace std;
namespace fish
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator cbegin() {
return _start;
}
const_iterator cend() const {
return _finish;
}
vector() {
}
vector(int n, const T& value = T()) {
resize(n, value);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
if (first <= last) {
reserve(last - first);
for (InputIterator i = first;i < last;i++) {
push_back(*i);
}
}
}
vector(const vector<T>& v) {
reserve(v.capacity());
for (size_t i = 0;i < v.size();i++) {
_start[i] = v._start[i];
_finish++;
}
}
vector<T>& operator= (vector<T> v) {
vector<T> tmp(v);
return tmp;
}
~vector() {
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
size_t size() const {
return _finish - _start;
}
size_t capacity() const {
return _endOfStorage - _start;
}
void reserve(size_t n) {
size_t sz = size();
if (n > sz) {
T* tmp = new T[n];
for (size_t i = 0;i < size();i++) {
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& value = T()) {
reserve(n);
for (size_t i = 0;i < n;i++) {
_start[i] = value;
_finish++;
}
}
T& operator[](size_t pos) {
return _start[pos];
}
const T& operator[](size_t pos)const {
return _start[pos];
}
void push_back(const T& x) {
if (size() == capacity())
reserve(capacity() == 0 ? 4 : 2 * capacity());
*_finish = x;
_finish++;
}
void pop_back() {
if (size() > 0) {
_finish--;
}
}
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
iterator insert(iterator pos, const T& x) {
size_t l = pos - _start;
if (size() == capacity())
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + l;
if (pos <= _finish) {
for (iterator i = _finish;i > pos;i--) {
*i = *(i - 1);
}
_finish++;
}
*pos = x;
return pos;
}
iterator erase(iterator pos) {
if (pos < _finish) {
iterator i = pos;
while (i + 1 < _finish) {
*i = *(i + 1);
i++;
}
_finish--;
}
return pos;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endOfStorage = nullptr;
};
};
源码实现了常用的增删查改操作和比较，模拟实现有助于进一步理解stl库中底层代码的实现。