免费网站入口2021网站网上推广
一、vector容器的介绍
vector是表示可变大小数组的序列容器。就像数组一样，vector也采用的连续存储空间来存储元素，但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
总结：vector是一个动态数组，能高效的随机下标访问。
二、主要接口
| (constructor)构造函数声明 | 接口说明 |
| vector()（重点） | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
| iterator的使用 | 接口说明 |
| begin + end（重点） | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
| 容量空间 | 接口说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize（重点） | 改变vector的size |
| reserve （重点） | 改变vector的capacity |
| vector增删查改 | 接口说明 |
| push_back（重点） | 尾插 |
| pop_back （重点） | 尾删 |
| find | 查找。（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] （重点） | 像数组一样访问 |
三、模拟实现
1.vector 的对象
iterator _start ： 指向第一个元素的迭代器
iterator _finish: 指向最后一个元素下一个位置的迭代器
iterator _endOfStorage ：指向动态空间最后一个位置的迭代器
namespace N
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endOfStorage = nullptr;};
}模板命名T vector迭代器的本质是指针
【C++11】关于成员对象给缺省，在构造函数调用初始化列表的时候，会选择用上缺省值
2.迭代器成员函数begin()和end()
begin():返回指向容器的起始位置的迭代器（非const）
end():返回指向容器的最后位置的下一个位置迭代器（非const）
cbegin():返回指向容器的起始位置的常属性迭代器（const）
cend():返回指向容器的最后位置的下一个位置常属性迭代器（const）
iterator begin(){return _start;
}iterator end(){return _finish;
}const_iterator cbegin()const {return _start;
}const_iterator cend() const
{return _finish;
}区别：
非const的版本函数返回的迭代器可以用来访问，修改元素
而const版本只能用来访问元素，不准修改
3.容量空间
1)size()：返回数据个数
元素首位迭代器的相减返回个数 （前开后闭返回区间个数）
2）capacity()
元素容量与头元素迭代器的相减
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endOfStorage - _start;
}3）reserve(size_t n) :改变vector的capacity
如果vector 的capacity大于n ，不进行操作
n>=capacity，扩容，拷贝，释放原空间
同时更新_start _finish _endofstorage
void reserve(size_t n)
{if (n <= capacity()){return;}T* tmp = new T[n];size_t sz = size();if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start+n;
}4)resize :改变vector的size
n<size() 改变_finishi
n>=size() reserve空间，size后面的数依次赋值
void resize(size_t n, const T& value = T())
{if (n <= size()){_finish = _start + n;return;}reserve(n);while (_finish < n + _start){*_finish = value;++_finish;}
}关于默认参数 ：
匿名对象T()生命周期只有这一行
const修饰匿名对象 延长生命周期 value销毁时匿名对象才销毁
4.vector增删查改
1）push_back():尾插
检查容量，不够就reserve扩容 _finish位置插入数据 ++_finish
void push_back(const T& x)
{if (_finish == _endOfStorage)//扩容{reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}2)pop_back()：尾删
--_finish
void pop_back()
{_finish--;
}3)insert(): pos位置之前插入val
检查pos合法
检查是否扩容，注意保存pos的位置，(求出pos-_start)
从最后一个数据往前挪动数据，插入val
更新_finish
iterator insert(iterator pos, const T& x)
{assert(pos>=_start);assert(pos <= _finish);int len = pos - _start;if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}pos = _start + len;//移动数据iterator end = _finish-1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}关于迭代器失效：
如果扩容后，原来的空间会被释放掉，那么pos会变成野指针,如果继续使用迭代器，会使用一块已经释放的空间，导致程序可能崩溃。
会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等
4）earse()：删除pos的值
检查pos的合法 _start<=pos<=_finish
从前往后挪数据
更新_finish
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);iterator cur = pos+1;while (cur != _finish){*(cur - 1) = *cur;++cur;}--_finish;return pos;
}涉及迭代器失效问题：
当earse最后一个位置时，迭代器失效，vs上认为使用earse后，不管删除哪个位置迭代器都失效
5）swap ：交换俩个vector的数据空间
如果发生赋值，会极大降低效率，因此在vector容器的交换，交换各自的迭代器对象
void swap(vector<T>& v)
{::swap(_start, v._start);::swap(_finish , v._finish);::swap(_endOfStorage, v._endOfStorage);
}6）operator [ ] ：下标访问修改
返回指定空间的引用
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos)const
{assert(pos < size());return _start[pos];
}关于const版本和非const版本：
const只读不可改，非const版本可读可改
5.(constructor)构造函数声明
1)无参构造函数：
不用写具体内容，因为在C++11支持成员变量给缺省，会自动进入初始化列表
2）vector（size_type n, const value_type& val = value_type()） N个value构造
先开空间，附用reverse函数，尾插
vector(int n, const T& value = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(value);}
}3）vector(InputIterator first, InputIterator last)：迭代器区间构造
定义迭代器模板，依次尾插
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}4)vector (const vector &x)：拷贝构造
开空间，尾插
vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}5）operator =：赋值
拷贝构造临时空间，交换
vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}6）析构函数
释放空间
总结：
源代码：
STL/vector.h · L_may/C++Study - 码云 - 开源中国 (gitee.com)
本文模拟实现vector容器，在insert和erase中涉及迭代器失效的问题，要多加注意。
作者能力有限，希望对大家有所帮助。