C++_STL之vector篇

一、vector的常见用法

        注：C++中若使用vector需包含头文件<vector>.

1.vector的构造函数

	int n = 10,ret=1;vector<int> nums(n,ret);	//n表示vector初始的容量 ret表示vector中初始化的值for (auto e : nums)cout << e << " ";

扩展：vector<type>可以放入任意类型

如vector<vector<int> >,vecotr<string>,vector<pair<int,int> >等，效果是一样的；

2.迭代器

在现在的大多数编译器中是支持vector使用迭代器的，如图所示

3.拷贝构造

        vector的拷贝构造具有很好的实用性，需要创建一个原数组的临时变量时，这个函数就极大减少了我们创建新vector进行赋值的时间，与此同时，我们还可以对其中一项vector进行赋值操作,如下面注释内容中v=nums（此处的 = 为我们的运算符重载）。

	int n = 4,m=5,ret=6;vector<vector<int>> nums(n,vector<int>(m,ret));	//n,m表示vector初始的容量 ret表示vector中初始化的值vector<vector<int> > v(nums);		//将nums内容拷贝到v上//常见写法vector<vector<int> > v；//v=nums;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cout << v[i][j] << " ";}cout << endl;}

4.reserve(size_t n)函数

        reserve函数是一个预扩容函数，可以为vector对象重新扩容，从而提高了vector的性能，在后面的insert函数和push_back等函数中会用到reserve这个函数。

5.resize(size_t n, const T& val = T())

        resize的功能就是重置数组的大小。功能效果如图所示

6.push_back(const T& x)

        push_back的功能就是在vector后面插入一个数据x，vector长度会自动+1，capacity(容量)不足时会自动扩容（注：这里的扩容量不定，是由编译器内部实现决定的）。效果图如下：

7.pop_back()

        这个函数的功能就是删除vector中最后一项元素，vector长度-1。效果图如下:

8.[size_t pos]运算符重载

        该函数的功能是返回vector容器中pos位置元素的值（引用返回），因此这里我们就既可以查看pos位置的值也可以修改pos位置的值；效果图：

9.insert(iterator pos, const T& x)

        功能在pos位置（此处的pos为迭代器插入方式应为nums.insert(nums.begin()+pos,x) ）插入x值，由于每次插入一般都需移动vector时间成本高，所以在算法题中比较少见。（算法中常用push_back()）；用法如图所示：

10.erase(iterator pos)

        功能在pos位置（此处的pos为迭代器插入方式应为nums.erase(nums.begin()+pos) ）删除x值，由于每次删除一般都需移动vector时间成本高，所以在算法题中比较少见。（算法中常用pop_back()）；用法如图所示：

11.size()

        这个函数非常实用无论是在算法题上，还是在自己敲代码时实现某些功能时这个函数都很常见，功能就是得到vector的长度。效果图：

12.capacity()

        这个函数在做算法题时不怎么常用，但还是需要了解一下。显而易见，功能就是得到vector的容量大小。效果图：

二、vector的模拟实现

由STL库中可见，vector内部是由三个指针来实现的：

        _start所在位置为vector起始位置;

        _finish所在位置为vector长度终止位置及size+1处；

        _endofstorage所在位置为vector容量终止位置。

1.vector内部值初始化

namespace lwf 
{template <class T>class vector{public:typedefy T* iterator;typedefy const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstoage = nullptr;};
}

2.vector的构造函数

        vector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}

3.迭代器

		iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//迭代器的实现template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

4.拷贝构造

		//拷贝构造vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v._size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector operator=(vector<T> v){swap(v);return *this;}

5.reserve(size_t n)函数

		void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}

6.resize(size_t n, const T& val = T())

		void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}

7.push_back(const T& x)

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

8.pop_back()

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

9.[size_t pos]运算符重载

		T& operator[](size_t pos){assert(pos < size());return _start[pos];}//const 类型const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

10.insert(iterator pos, const T& x)

		iterator insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);if (_finish == _endofstorage){size_t len = pos-_start;size_t newcapacity= capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//解决迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}

11.erase(iterator pos)

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

12.size()

		size_t size(){return _finish - _start;}

13.capacity()

		size_t capacity(){return _endofstorage - _start;}

14.析构函数

		~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = 0;}}

三、整体的实现

        整体的代码仅供参考，只是为了加强自己的记忆力和代码能力，从而个人实现了vector的一些基础的功能

#pragma once#include <assert.h>namespace lwf
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}size_t capacity(){return _endofstorage - _start;}size_t size(){return _finish - _start;}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(){}//拷贝构造vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v._size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = 0;}}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){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& val = T()){if (n > size()){reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());}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){assert(pos <= _finish && pos >= _start);if (_finish == _endofstorage){size_t len = pos-_start;size_t newcapacity= capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//解决迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos + 1;while (pos != _finish){*(pos - 1) = *pos;++pos;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};}

四、感言

        由于一些学业上的原因断更了半个学期，在这里感谢各位大佬和友友们的支持，不介意的话给我点个赞再走吧！