这篇文章主要介绍C++中STL vector的模拟实现示例，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
更为详细的可以查看vector文档介绍。
vector的嵌套型别定义
typedef _Ty value_type; typedef value_type* iterator; typedef value_type& reference; typedef size_t size_type;
vector的成员变量
private: iterator _start; iterator _last; iterator _end;
vector():_start(nullptr),_last(nullptr),_end(nullptr) {} vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr) { insert(n,value); } vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr) { insert(f,l); } vector(const vector<int>& iv) { reserve(iv.capacity()); iterator it = begin(); iterator vit = iv.end(); while (vit != iv.begin()) { *it++ = *vit--; } }iterator insert(iterator pos,const _Ty& value) { //1.当size()==capacity()时，表明vector已满，再进行插入前需要进行扩容 if(size()== capacity()) { size_type oldpos = pos - begin(); //这里需要防止一种情况：若vector为空的时候，他的capacity为0，这个时候给他直接扩容2倍是行不通的， //因为2*0 = 0，因此就需要进行判断 size_type newcapacity = (capacity() == 0)? 1 : 2*capacity(); reserve(newcapacity); //这里空间发生了变化，pos迭代器会失效，因此需要重新对pos进行设置 //reserve不会使vector的成员变量失效 pos = begin() + oldpos; } //2.当size() < capacity()时，表明vector未满，插入直接在pos的位置进行插入 //需要注意的是插入是在pos指向的位置进行插入，并且插入需要挪动数据， //将pos位置之后的数据全部向后挪动一个,为防止元素被改写，则需要从后向前进行挪动 iterator tail = _last; while(tail > pos) { *tail = *(tail-1); --tail; } //这里要注意的是挪动数据时，因为没有对pos位置进行操作，所以pos位置的迭代器并没有失效， //但是pos位置之后的迭代器全部失效了，但在这里并没有关系，我们并不会用到那些迭代器 *pos = value; //插入完之后，一定要对_last指针+1，因为全部向后挪动了一个元素 ++_last; return pos; } void insert(size_type n,const _Ty& value) { for(int i = 0;i < n; ++i) { insert(end(),value); } } void insert(iterator f,iterator l) { while(f!=l) { insert(end(),*f); ++f; } } iterator erase(iterator pos) { assert(pos >= _start || pos < _last); //1.删除pos位置的元素，就是将[pos,end()]这个区间向前挪动一个即可 iterator it = pos + 1; while(it != _last) { *(it-1) = *(it); ++it; } --_last; return pos; }void reserve(size_type n) { //若 n 的值大于vector的容量，则开辟空间 //若 n 的值小于等于，则不进行任何操作 if(n > capacity()) { //1.新开辟一个空间 size_type oldSize = size(); _Ty* newVector = new _Ty[n]; //2.将原空间的数值赋值到新空间 if(_start) { //注意：这里不能使用memcpy,因为memcpy是一个浅拷贝。 //memcpy(newVector,_start,sizeof(_Ty)*size()); for(size_type i = 0; i < oldSize; ++i) { newVector[i] = _start[i]; } } //3.改变三个指针的指向 //这里直接重新给三个成员进行赋值，所以调用reserve()函数不用担心迭代器失效的问题 _start = newVector; _last = _start + oldSize; _end = _start + n; } } void resize(size_type n,const _Ty& value = _Ty()) { //1.如果n的值小于等于size()的时候，则只需要将_last的指针往前移动即可 if(n <= size()) { _last = _start + n; return; } //2.如果n的值大于capacity()的时候，则需调用reserve()函数，重新设置容量大小 if(n > capacity()) { reserve(n); } //若当n的值大于size()而小于capacity()的时候，只需将_last的指针往后移即可 iterator it = _last; _last = _start + n; while(it != _last) { *it = value; ++it; } //resize()函数也不需要担心迭代器失效的问题 }void push_back(const _Ty& value) { insert(end(),value); } void pop_back() { erase(end()-1); }iterator begin()const { return _start; } iterator end() const { return _last; }size_type size() { return end()-begin(); } size_type capacity()const { return _end-begin(); }bool empty()const { return end() == begin(); } reference operator[](size_type n) { return *(begin() + n); }#include <iostream> #include <assert.h> using namespace std; namespace mytest{ template<class _Ty> class vector { public: typedef _Ty value_type; typedef value_type* iterator; typedef value_type& reference; typedef size_t size_type; public: iterator begin()const { return _start; } iterator end() const { return _last; } size_type size() { return end()-begin(); } size_type capacity()const { return _end-begin(); } bool empty()const { return end() == begin(); } reference operator[](size_type n) { return *(begin() + n); } public: vector():_start(nullptr),_last(nullptr),_end(nullptr) {} vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr) { insert(n,value); } vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr) { insert(f,l); } vector(const vector<int>& iv) { reserve(iv.capacity()); iterator it = begin(); iterator vit = iv.end(); while (vit != iv.begin()) { *it++ = *vit--; } } public: void reserve(size_type n) { //若 n 的值大于vector的容量，则开辟空间 //若 n 的值小于等于，则不进行任何操作 if(n > capacity()) { //1.新开辟一个空间 size_type oldSize = size(); _Ty* newVector = new _Ty[n]; //2.将原空间的数值赋值到新空间 if(_start) { //注意：这里不能使用memcpy,因为memcpy是一个浅拷贝。 //memcpy(newVector,_start,sizeof(_Ty)*size()); for(size_type i = 0; i < oldSize; ++i) { newVector[i] = _start[i]; } } //3.改变三个指针的指向 //这里直接重新给三个成员进行赋值，所以调用reserve()函数不用担心迭代器失效的问题 _start = newVector; _last = _start + oldSize; _end = _start + n; } } void resize(size_type n,const _Ty& value = _Ty()) { //1.如果n的值小于等于size()的时候，则只需要将_last的指针往前移动即可 if(n <= size()) { _last = _start + n; return; } //2.如果n的值大于capacity()的时候，则需调用reserve()函数，重新设置容量大小 if(n > capacity()) { reserve(n); } //若当n的值大于size()而小于capacity()的时候，只需将_last的指针往后移即可 iterator it = _last; _last = _start + n; while(it != _last) { *it = value; ++it; } //resize()函数也不需要担心迭代器失效的问题 } void push_back(const _Ty& value) { insert(end(),value); } void pop_back() { erase(end()-1); } iterator insert(iterator pos,const _Ty& value) { //1.当size()==capacity()时，表明vector已满，再进行插入前需要进行扩容 if(size()== capacity()) { size_type oldpos = pos - begin(); //这里需要防止一种情况：若vector为空的时候，他的capacity为0， //这个时候给他直接扩容2倍是行不通的，因为2*0 = 0，因此就需要进行判断 size_type newcapacity = (capacity() == 0)? 1 : 2*capacity(); reserve(newcapacity); //这里空间发生了变化，pos迭代器会失效，因此需要重新对pos进行设置 //reserve不会使vector的成员变量失效 pos = begin() + oldpos; } //2.当size() < capacity()时，表明vector未满，插入直接在pos的位置进行插入 //需要注意的是插入是在pos指向的位置进行插入，并且插入需要挪动数据， //将pos位置之后的数据全部向后挪动一个,为防止元素被改写，则需要从后向前进行挪动 iterator tail = _last; while(tail > pos) { *tail = *(tail-1); --tail; } //这里要注意的是挪动数据时，因为没有对pos位置进行操作，所以pos位置的迭代器并没有失效， //但是pos位置之后的迭代器全部失效了，但在这里并没有关系，我们并不会用到那些迭代器 *pos = value; //插入完之后，一定要对_last指针+1，因为全部向后挪动了一个元素 ++_last; return pos; } void insert(size_type n,const _Ty& value) { for(int i = 0;i < n; ++i) { insert(end(),value); } } void insert(iterator f,iterator l) { while(f!=l) { insert(end(),*f); ++f; } } iterator erase(iterator pos) { assert(pos >= _start || pos < _last); //1.删除pos位置的元素，就是将[pos,end()]这个区间向前挪动一个即可 iterator it = pos + 1; while(it != _last) { *(it-1) = *(it); ++it; } --_last; return pos; } private: iterator _start; iterator _last; iterator _end; }; }; void Test1() { mytest::vector<int> iv; cout << "iv.size() = " << iv.size() << endl; cout << "iv.capacity() = " << iv.capacity() << endl; iv.push_back(1); iv.push_back(2); iv.push_back(3); iv.push_back(4); cout << "iv.size() = " << iv.size() << endl; cout << "iv.capacity() = " << iv.capacity() << endl; mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl; iv.pop_back(); iv.pop_back(); it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl; } void Test2() { mytest::vector<int> iv(10,2); mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl; } void Test3() { int ar[] = {1,2,3,3,4,5}; mytest::vector<int> iv(ar,ar+6); mytest::vector<int>::iterator it = iv.begin(); while(it != iv.end()) { cout << *it << " "; ++it; } cout << endl; } int main() { // Test1(); // Test2(); Test3(); return 0; }以上是“C++中STL vector的模拟实现示例”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
