vector(c++)

前言

正式进入学习STL的第一步就是vector容器， vector是一种用于存储可变大小数组的序列容器，就像数组一样，vector也采用的连续存储空间来存储元素。本质上讲，vector使用动态分配数组来存储它的元素。底层是一个顺序表。本文介绍的是gcc使用的STL源码的vector容器，这也是业界比较认可的一种STL版本。后续的vector模拟实现一切都是向这个版本靠齐。

正文

vector使用

class Print
{
public:template<class T>static void printVector(vector<T> v){for (auto e : v){cout << e << " ";}}
};

这里我先把打印封装成一个类，方便后序测试的打印

vector的定义

vector::vector - C++ Reference	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

//vector的定义
void test01()
{//重点//初始化列表初始化(c++11特性) c++98不支持vector<int> v1 = { 1,2,3,4 };vector<int> v2(v1);Print::printVector(v1);cout << endl;Print::printVector(v2);cout << endl;vector<int> v3(10,-1);vector<int> v4(v1.begin(),v1.end());Print::printVector(v3);cout << endl;Print::printVector(v4);
}

这里着重掌握无参构造和拷贝构造，其他的了解即可

vector iterator 的使用

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

//vector iterator 的使用
//正向迭代器和反向迭代器
void test02()
{vector<int> v1 = { 1,2,3,4 };vector<int> v2(v1);vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}cout << endl;auto it2 = v2.rbegin();while (it2 != v2.rend()){cout << *it2 << " ";it2++;}}

这里的迭代器没啥好说的，会使用就行，不过要注意迭代器失效，下面会着重讲。

vector 容量

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity

//vector 容量
void test03()
{vector<int> v1 = { 1,2,3,4 };vector<int> v2(v1);//重点Print::printVector(v2);cout << endl;//大于size()v2.resize(10, -1);Print::printVector(v2);cout << endl;//小于size()v2.resize(3, -1);Print::printVector(v2);cout << endl;//size capacity emptysize_t size = v1.size();size_t capacity = v1.capacity();cout << "v1: " << size << " " << capacity << " " << (v1.empty() ? "true" : "false") << endl;}

和string的容量大差不差，会使用即可

vector 增删查改

vector 增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问

//vector 增删查改
void test04()
{vector<int> v1;//重点v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<int> v2(v1);v1.pop_back();cout << "v1:test: ";for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;cout << "v2:test: ";for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << " ";}cout << endl;//find insert erase swap//...就不测试了 大家自己测试下吧 都是很简单的
}

这里的增删查改和string的差不多，不过要注意vector并没有find接口，这个接口是算法的接口，就是再一段区间找值并返回迭代器而已，很简单。

vector 迭代器失效问题。（重点）

//vector 迭代器失效问题。（重点）
void test05()
{vector<int> v1 = { 1,2,3,4,5,6 };vector<int> v2(v1);auto it1 = v1.begin();while (it1 != v1.end()){if (*it1 % 2 == 0){v1.erase(it1);}else{it1++;}}Print::printVector(v1);auto it2 = v2.begin();while (it2 != v2.end()){if (*it2 % 2 == 0){it2 = v2.erase(it2);}else{it2++;}}Print::printVector(v2);
}

这里才是重点，要了解迭代器失效问题，就要先了解迭代器的原理底层，vector的迭代器底层本质还是指针实现的。所以指针就会涉及拷贝时的一个深浅拷贝，指针指向的地址的问题。由于是深拷贝，所以如果涉及到扩容，我们就会新开辟一块新空间，把原来的数据拷贝到这里。但是，迭代器还是指向原来空间的位置，原来的空间已经被释放掉，所以这里迭代器失效本质上就是一个野指针。那怎么解决这个问题呢？总不能不深拷贝吧？改变下参数吗？参数改变也没啥用呀。我erase是删除迭代器位置的数据，对你还要不要使用这个迭代器我没有义务保证你的安全呀？所以，我们对返回值做文章，返回要删除数据的下一个迭代器。这也是为啥insert会有一个返回值，返回插入位置的迭代器。

这里还涉及一个平台检查问题，下面这段代码在gcc下是可以编译通过的，但是在vs下直接报错

	vector<int> v1 = { 1,2,3,4,5,6 };auto it1 = v1.begin();while (it1 != v1.end()){if (*it1 % 2 == 0){v1.erase(it1);}else{it1++;}}Print::printVector(v1);

因此，这里有一个结论，insert和erase之后我们一致认为你的迭代器是失效，使用它结果是未定义的。

vector的模拟实现

这里才是学习vector的重头戏，只有自己模拟实现一个vector，你才能正真理解这个容器的设计。

成员变量

private:T* _start = nullptr;T* _finish =nullptr;T* _endofstorage = nullptr;

为啥这里不是，size,capacity,_arr呢？咋是什么_finish？这是啥？其实这和STL的设计理念有关，这里从vector开始就几乎基本全面介入迭代器了。vector的迭代器底层就是T*。所以，他的变量要设计成这样也是为了向迭代器靠拢，_start就是数组的起始位置,_finish是 最后一个数据的下一个位置,_endifstorage就是容器的底部的下一个位置。这里我给了初始值(c++11打入的补丁)，所以后面构造函数我没有在初始化值了。

这里先实现下swap函数，方便后续函数的编写。

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

默认成员函数

这里我使用的是直接new delete管理动态内存分配，但是原版STL使用的是空间配置器，其实底层还是包装new delete而已，但不过人家的这个空间配置器效率更高。对于我们初学者，先使用new delete就可以了，如果现在就要你学习空间配置器，让你掌握并使用。那可谓真的是从入门到放弃。一般来说空间配置器是c++很后面才会讲的。

构造 析构

vector()
{}
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(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}

这里构造析构没啥坑，就是正常实现就行。

拷贝构造

	vector(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//解决对象的深拷贝for (size_t i = 0; i < size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}

这里是一个难点，主要是深拷贝的问题，对于内置类型的靠别没有问题。但是如果是自定义类型，使用memcpy就是一个浅拷贝。那如何解决呢？使用for循环，使用它们内部的赋值重载一个个赋值。

赋值重载

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

迭代器

这里我并没有实现反向迭代器

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;
}

容量操作

		void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}//匿名对象当省略值 如果是内置类型 c++会特殊处理 升级成对象 调用无参构造void resize(size_t n, const T& val = T()){if (n < capacity()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;_finish++;}}}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}bool empty(){return size() == 0;}

这里的扩容，和上面拷贝构造函数内部迭代器失效是一个原理，所以我们也要换一下拷贝，不能使用memcpy。

增删查改和访问引用操作

访问引用

	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 erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos;while (end < _finish){*end = *(end + 1);end++;}_finish--;return pos;}iterator erase(iterator first, iterator last){assert(first >= _start && first <= _finish);assert(last >= _start && last <= _finish);assert(first <= _finish);iterator it1 = first, it2 = last;size_t len = last - first;//1 2 3 4 5while (it1 <= last){*it1 = *(it2);it1++;it2++;}_finish -= len;return last;}void push_back(const T& x){if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish); //等于就是尾插和头插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;}

vector实现二维数组

实际上就是一个函数套一个函数而已，那这样岂不是效率很低，放心它会直接升级内联的。和c++讲效率低，你简直是在侮辱它？

void test06()
{vector<vector<int>> arr = { {1,},{1,2},{1,2,3} };//vector<vector<int>>for (auto e : arr){//e : vector<int>for (auto i : e){//i intcout << i << " ";}cout << endl;}
}

源码

#pragma once
#include <stdio.h>
#include <assert.h>
//vector insert和erase之后我们认为迭代器是失效的
//访问结果是未定义的
namespace che 
{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;}vector(){}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(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//解决对象的深拷贝for (size_t i = 0; i < size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}//其他写法~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos;while (end < _finish){*end = *(end + 1);end++;}_finish--;return pos;}iterator erase(iterator first,iterator last){assert(first >= _start && first <= _finish);assert(last >= _start && last <= _finish);assert(first <= _finish);iterator it1 = first, it2 = last;size_t len = last - first;//1 2 3 4 5while (it1 <= last){*it1 = *(it2);it1++;it2++;}_finish-=len;return last;}void push_back(const T& x){if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;}//匿名对象当省略值 如果是内置类型 c++会特殊处理 升级成对象 调用无参构造void resize(size_t n, const T& val = T()){if (n < capacity()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;_finish++;}}}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish); //等于就是尾插和头插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;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}private:T* _start = nullptr;T* _finish =nullptr;T* _endofstorage = nullptr;};
}

总结

相比string的学习，你会发现vector的学习是很轻松的，就是一些基本的顺序表的函数实现，比较难的就是他的迭代器失效问题。会涉及到深浅拷贝以及如何处理的问题，这和他的设计理念是息息相关的。