C++ Vector的模拟实现

vector的介绍
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的一些接口：

namespace MyVector
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin();iterator end();const_iterator cbegin() const;const_iterator cend() const;   // 初始化vector();// 析构~vector();vector(int n, const T& value = T());vector(size_t n, const T& val = T());//类模板的成员函数可以是函数模板template<class InputIterator>vector(InputIterator first, InputIterator last);vector(const vector<T>& v);vector<T>& operator= (vector<T> v);size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& value = T());T& operator[](size_t pos);const T& operator[](size_t pos)const;bool empty();void push_back(const T& x);void pop_back();void swap(vector<T>& v);iterator insert(iterator pos, const T& x);iterator erase(iterator pos);private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr;// 指向存储容量的尾};
}

iterator begin()

        iterator begin(){return _start;}

iterator end()

        iterator end(){return _finish;}

const_iterator cbegin()

        const_iterator cbegin(){return _start;}

const_iterator cend() const

        const_iterator cend() const{return _finish;}

四个比较简单的迭代器

vector()

        vector():_start(nullptr),_finish(nullptr), _endOfStorage(nullptr){}

~vector()

        ~vector(){delete[] _start;_start = _finish = _endOfStorage;}

初始化与析构

        //类模板的成员函数可以是函数模板template<class InputIterator> // InputIterator定义的一个迭代器类型vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}

vector<T>& operator= (vector<T> v)

        vector<T>& operator= (vector<T> v){swap(v);return *this;}

        // v1 = v3

size_t size() const

        size_t size() const{return _finish - _start;}

        // 有效数据的尾减去数据块的开始就是元素个数

size_t capacity() const

        size_t capacity() const{return _endOfStorage - _start;}

        // 开辟空间的容量

void reserve(size_t n)

        void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i]; // 深拷贝}delete[] _start;_start = tmp; // 老的_start已经失效，更新一下_finish = tmp + old_size;_endOfStorage = tmp + n;}}

void resize(size_t n, const T& value = T())

        void resize(size_t n, const T& value = T()){if (n > size()) // 超过就扩容{reserve(n);while (_finish < _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}

vector(const vector<T>& v)

        vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

        // v2(v1) 用已经存在的 v1 去初始化 v2

T& operator[](size_t pos)

const T& operator[](size_t pos)const

        T& operator[](size_t pos){assert(pos < size()); // 保证下标为有效数据return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

iterator insert(iterator pos, const T& x)

        iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}

iterator erase(iterator pos)

        iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;--it;}--_finish;return pos;}

vector(int n, const T& value = T())

        vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}

vector(size_t n, const T& val = T())

        vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

bool empty()

        bool empty(){return _start == _finish;}

void push_back(const T& x)

        void push_back(const T& x){insert(end(), x);}

void pop_back()

        void pop_back(){erase(end() - 1);}

void swap(vector<T>& v)

        void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}

完整代码：

#pragma once#include <assert.h>namespace bit
{template<class T>class vector{public:// Vector的迭代器是一个原生指针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;}// construct and destroyvector():_start(nullptr),_finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//类模板的成员函数可以是函数模板template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endOfStorage;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endOfStorage = tmp + n;}}void resize(size_t n, const T& value = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}bool empty(){return _start == _finish;}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}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){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;--it;}--_finish;return pos;}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr;// 指向存储容量的尾};}

测试代码：

#include <iostream>
#include<algorithm>
#include<vector>#include "Vector.h"using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;cout << v.capacity() << endl;for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;v.reserve(30);cout << v.capacity() << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;vector<int> v1(v);v1.push_back(100);v1.push_back(200);v1.pop_back();for (auto e : v1){cout << e << " ";}
}