前言：vector类也可以叫作顺序表，他同样也在STL库中的容器模块中，我还是主要讲常用的几个成员函数和成员变量，同时它晚于string类，所以在设计上没有string冗余。
vector类是一个和数组类似的容器，它属于随机迭代器的容器可以支持++,+,--,-。正常理解就是只要是一段连续的空间就可以使用+和-
单向迭代器:只支持单方向移动也就是++，如单链表
双向迭代器:它比单向多了一个功能向后移动，支持++和--,但不能够随机访问数据，如双向链表，树
随机迭代器:除了包含以上两个迭代器都有的功能以外还可以通过索引访问就像数组一样，如stirng类和vector类
我比较喜欢依靠注释讲解，如有解释不到位的，望包含
目录
1.对容量有关的成员函数和成员变量
2.迭代器相关的函数 （begin和end）
3.vector类的构造函数和析构函数及拷贝构造
4. vector对象的元素操作
(1)插入元素 ,push_back,insert>
(2)删除一个元素或一段区间,erase>
(3) operator=(运算符重载)和swap(交换)
(4) 比较小的函数(clear,find)
5.元素访问和修改
vector类的详细接口传送门：vector - C++ Reference (cplusplus.com)
迭代器相关（iterator）
begin //返回顺序表的起始位置的迭代器
end //返回结尾位置下一位的迭代器
对容量有关的
size //返回有效个数
capacity //容量
empty //判空
reserve //扩容
元素访问
operator[] //重载方括号“[]”
front //访问起始位的元素
back //访问最后的元素
vector对象的修改操作
push_back //尾插
pop_back //尾删
insert //在迭代器pos的位置上插入一个元素
erase //删除元素
swap //交换
clear //初始化
查找(find)在文档里好像是没有，但这个也是可以自己实现的
find //返回一个下标或者当前数据位置的迭代器都可以
1.对容量有关的成员函数和成员变量
vector类的成员变量不再是单独一个指针而是变为三个iterator（迭代器），他们分别是指向开始的_start(开始位置),_finish(有效元素的下一位)，_end_of_storage(容量的极限位置)三个指针
同时需要将常用的成员函数实现出来后面会经常调用这些函数，除了reserve(扩容)函数以外，其他比较简单可以直接通过代码实现来学习
size_t size()const //返回有效元素个数 { return _finish-_start; //结束位置减去起始位置得到个数 } size_t capacity()const //返回容量大小 { return _end_of_storage - _start; //容量极限位置减去起始位置得到容量大小 } bool Empty()const //判空 { return _start == _finish; }现在来讲一下reserve(扩容)函数的特殊情况：
正常扩容空间只需要申请一个比原来大的空间，然后进行空间拷贝，更新指向空间的指针即可(比如:string类)
string类可以通过下标来进行索引数据，vector类也可以，但是vector成员变量是三个迭代器，所以在原来的空间被释放后，迭代器的数据也需要更新，否则会出现迭代器失效的情况
迭代器失效：
一个迭代器因为扩容原因或者移动数据导致当前指向的迭代器和后续的迭代器全部无效化，如下图：
在申请新空间后需要对旧空间进行释放，_start会指向新空间，但另外的两个迭代器却还指向旧空间，所以需要进行数据更新，否则就会出现迭代器失效(_finish失效,_end_of...失效)，更新数据只要提前记录有效元素个数后面加上即可
注意：string类同样也会有迭代器失效的情况
void Reserve(size_t n) //扩容 { if (n > capacity()) //进行深拷贝 { size_t old_size = size(); //获取有效元素个数 iterator newnode=new T[n]; //申请新空间 memcpy(newnode,_start,sizeof(T)*old_size); //拷贝 delete[] _start; //释放旧空间 _start=newnode; //_start指向新空间 _finish=_start+old_size; //_start加上有效个数old_size更新_finish _end_of_storage=_start+n; //_start加上新的容量大小n更新_end_of_storage { }
2.迭代器相关的函数 （begin和end）
这两个函数都比较简单，他们分别负责返回起始位置的迭代器和有效元素结束位置的下一位的迭代器，而我们的成员变量就是这两个迭代器，直接调用返回即可
注意：
1.const迭代器(const_iterator)和普通迭代器(iterator)只有名字区别，分别对应被const修饰类型和普通类型
2.因为*this指针不会(也不能)显式出现在参数列表中，需要对*this指针进行const修饰时在函数声明“()”的后面加const就可以修饰*this指针了
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 //const迭代器 { return _start; } const_iterator end()const { return _finish; } private: //... }
3.vector类的构造函数和析构函数及拷贝构造
比较常用的构造方式有4种(要调用容量扩容函数)：
<1>无参数构造
<2>迭代器区间构造(需要调用插入函数)
<3>开N个空间，用T类型填充(需要调用插入函数)
<4>给一个数组或者一组元素进行初始化
注意：
1.在第四种初始化中需要使用initializer_list类来初始化，一组数据或者数组进行传参时会强转成该类对象，它能自动识别类型，并含有迭代器，主要目之一是为了简化初始化
2.开N个空间，用T类型填充初始化需要一个int类型作为第一个参数的函数重载，是为了避免开N个空间用int类型填充时，因为按需实例化会选择最符合要求的那个构造，所以在没有实现int作为参数的重载前开N个空间用int类型填充会选择模板构造，模板推导两次后为两个int最符合要求，导致对int解引用报错：非法访问
开N个空间，用int类型初始化：int作为第一个参数>模板>size_t作为第一个参数
template <class T> class Vector { public: typedef T* iterator; //普通迭代器 typedef const T* const_iterator; //const迭代器 void Reserve(size_t n) //... Vector() = default; //C++11支持前置生成默认构造 Vector(int n, const T& t = T()) //这两个构造都是开N个空间，T类型填充 { Reserve(n); //重载 for (int i = 0; i < n; i++) { Push_back(t); } } Vector(size_t n,const T& t = T()) { Reserve(n); for (int i = 0; i < n; i++) //开n个空间 { Push_back(t); //插入数据 } } template <class InputIterator> //迭代器区间构造需要使用模板，因为可以是任意类型 Vector(InputIterator first, InputIterator last) { auto it = first; while (it!=last) //使用迭代器遍历插入 { Push_back(*it); it++; } } vector(initializer_list<T> vl) //数组或一组数据会强转成该类对象 { Reserve(vl.size()); //开空间 for (auto ch : vl) //使用迭代器遍历插入 { Push_back(ch); } } private: //... }析构就直接使用delete[]释放空间即可，然后三个迭代器全部给空(nullptr)即可
~Vector() { delete[] _start; //释放空间 _start=_finish=_end_of_storage=nullptr; }
4. vector对象的元素操作
(1)插入元素 <resize,push_back,insert>
这里是vector类的增加数据的成员函数，内容比较简单，就是移动数据，然后插入
resize:将元素减少至N个，或者扩大元素个数到N个，不足的用T的无名对象填充（需要调用扩容函数）
push_back:尾插一个数据；可以通过复用insert函数减少代码段,只需要把_finish和要插入的元素传过去就可以了
void Resize(size_t n, const T& t = T()) { if (n < size()) //判断是否缩小 { _finish = _start + n; //直接更新_finish } else { Reserve(n); //扩容 while (_finish < _start + n) //填充数据 { *_finish=t; _finish++; } } } void Push_back(const T& t) { //非复用 /*if (_finish == _capacity) { Reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = t; _finish++；*/ //复用insert Insert(_finish,t); }insert:在pos位置上插入一个数据或者一个迭代器区间(区间我按照文档里的声明实现，也可以不使用模板)
注意：插入也会出现pos(插入位置)迭代器失效的情况，这个失效会因为容量不足扩容导致，所以要提前储存里起始位置的距离，扩容结束后更新pos位置
void Insert(iterator pos, const T& t) { assert(pos >= _start); //保证迭代器有效 assert(pos <= _finish); if (_finish == _end_of_storage) //判断是否需要扩容 { size_t size_old = pos - _start; Reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + size_old; } iterator end = _finish - 1; //找到尾巴的有效元素 while (end >= pos) //开始后移元素 { *(end + 1) = *end; end--; } *pos = t; //pos位置插入 _finish++; //更新_finish return pos; //返回插入的元素的迭代器 } template <class InputIterator> //迭代器区间删除 iterator Insert(iterator pos, InputIterator begin, InputIterator end) { assert(pos >= _start); //保证迭代器有效 assert(pos <= _finish); size_t newsize =end-begin; //计算一共要移动几个元素 if (size() + newsize >capacity()) //现有元素加上要移动的元素是否超过容量 { size_t size_old = pos - _start; //这里依旧是为了避免迭代器失效 Reserve(size() + newsize < capacity() * 2 ? size() + newsize : capacity() * 2); pos = _start + size_old; } iterator tail = _finish + newsize-1; //移动有效元素，-1不能忘 while (tail >= pos+newsize) { *(tail) = *(tail - newsize); tail--; } auto it = begin; while (it != end) //插入元素 { *pos = *it; pos++; it++; } _finish += newsize; //记得更新_finish return pos; //返回pos位置的迭代器 }
(2)删除一个元素或一段区间<pop_back,erase>
删除元素也是移动数据，不管是迭代器区间删除还是pos位置删除都只需要移动数据然后更新_finish即可
注意：我实现的迭代器区间删除遵从左闭右开的结构所以它并不会删除区间中最右边迭代器位置上的数据，如果需要删除则在esize(删除元素个数)上加1即可
下面是效果图和实现加注释讲解:
void Pop_back() //尾删除一个元素 { assert(!Empty()); //判空后直接更新_finish即可 _finish--; } void Erase(iterator pos) //删除一个数据 { assert(pos >= _start); //保证迭代器有效 assert(pos <= _finish); for (iterator i = pos + 1; i <= _finish; i++) //移动数据 { *(i - 1) = *i; } _finish--; //更新 _finish } void Erase(iterator begin,iterator last) { assert(pos >= _start); //保证迭代器有效 assert(pos <= _finish); size_t esize = last - begin; //计算删除的个数 for(iterator i = begin+size; i <=_finish; i++) //移动数据 { *(i - (size)) = *i; } _finish-=size; //更新 _finish }
(3) operator=(运算符重载)和swap(交换)
swap函数对于自定义类型来说最好是自己实现，可以避免多次拷贝构造降低效率。运算符=重载可以通过调用swap来提高效率
void swap(vector<T>& v) //直接交换成员变量 { std::swap(_start,v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector<T>& operator=(vector<T> v) //传参触发拷贝构造 { swap(v); //与临时对象交换迭代器 return *this; //函数结束自动释放临时对象 }
(4) 比较小的函数(clear,find)
clear(初始化)：这个和析构相似，只要把_start释放后与_finish一起置空(nullptr)即可
find(查找)：直接迭代器遍历查找，请根据自己需要调整返回类型
void clear() { delete[] _start; //释放空间 _start = _finish = nullptr; //将这俩个迭代器重新置空 } size_t Find(const T& t) //这里是返回它的下标位置 { //可以根据需要调整返回类型 assert(!empty()); iterator it = begin(); while (it != end()) { if (*it == t) { return it - _start; } it++; } return -1; }
5.元素访问和修改
首先就是熟悉的operator[]：它重载了方括号，我们将重新定义它的内容
修改数据只需要同过Find找到下标或者迭代器位置就可以直接“对象[X]”修改即可
front的作用：返回起始位置的数据
back的作用：返回结束位置的数据
下面直接看实现理解即可：
const T& operator[](size_t i)const { assert(i < size()); //判断是否超过有效数据个数 //return *(_start+i); return _start[i]; //这里的方括号和解引用的效果一样 } T& front() //返回起始位置数据 { return *_start; //对起始位置解引用返回即可 } T& back() //返回末尾数据 { return *(_finish-1); //减1找到末尾数据解引用返回 }
本篇文章的主要内容到这里讲完了，如有错误望指出我会及时修改，希望能为你提供帮助，感谢阅读
下面是代码实现和测试用例：
namespace cool
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector() = default;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
bool empty()const
{
return _start == _finish;
}
void Reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
iterator newstart = new T[n];
memcpy(newstart, _start, sizeof(T) * old_size);
delete[] _start;
_start = newstart;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
vector(initializer_list<T> il)
{
Reserve(il.size());
for (auto ch : il)
{
Push_back(ch);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
auto it = first;
while (it!=last)
{
Push_back(*it);
it++;
}
}
vector(size_t n,const T& t = T()) //单参数构造和无参构造
{
Reserve(n);
for (int i = 0; i < n; i++)
{
Push_back(t);
}
}
vector(int n, const T& t = T())
{
Reserve(n);
for (int i = 0; i < n; i++)
{
Push_back(t);
}
}
vector(const vector<T>& t)
{
Reserve(t.size());
for (auto ch : t)
{
Push_back(ch);
}
}
~vector()
{
delete[] _start;
_start = _finish = _finish = nullptr;
}
void Push_back(const T& t)
{
Insert(_finish, t);
}
template <class InputIterator>
iterator Insert(iterator pos, InputIterator begin, InputIterator end)
{
assert(pos >= _start);
assert(pos <= _finish);
size_t newsize =end-begin;
if (size() + newsize >capacity())
{
size_t size_old = pos - _start;
Reserve(size() + newsize < capacity() * 2 ? size() + newsize : capacity() * 2);
pos = _start + size_old;
}
iterator tail = _finish + newsize-1;
while (tail >= pos+newsize)
{
*(tail) = *(tail - newsize);
tail--;
}
auto it = begin;
while (it != end)
{
/*T newval =*it*/;
*pos = *it;
pos++;
it++;
}
_finish += newsize;
return pos;
}
void Insert(iterator pos, const T& t)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t size_old = pos - _start;
Reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + size_old;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = t;
_finish++;
}
size_t Find(const T& t)
{
assert(!empty());
iterator it = begin();
while (it != end())
{
if (*it == t)
{
return it - _start;
}
it++;
}
return 0;
}
void Pop_back()
{
assert(!empty());
_finish--;
}
void Erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
assert(!empty());
for (iterator i = pos + 1; i <= _finish; i++)
{
*(i - 1) = *i;
}
_finish--;
}
void Erase(iterator begin,iterator last)
{
assert(!empty());
size_t size = last - begin;
for (iterator i = begin+size; i <=_finish; i++)
{
*(i - (size)) = *i;
}
_finish-=size;
}
T& operator[](size_t pos)
{
assert(!empty());
return *(_start + pos);
}
void swap(vector<T>& v)
{
std::swap(_start,v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
void Resize(size_t n, const T& t = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
Reserve(n);
while (_finish < _start + n)
{
*_finish=t;
_finish++;
}
}
}
void Clear()
{
delete[] _start;
_start = _finish = nullptr;
}
T& Front() //返回起始位置数据
{
return *_start;
}
T& Back() //返回末尾数据
{
return *(_finish-1);
}
private:
iterator _start=nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template <class T>
void printcontainer(const T& t)
{
for (auto ch : t)
{
cout << ch << " ";
}
}
//构造测试
void test()
{
vector<int>v({1,2,3,4,5,6,7});
printcontainer(v);
cout << endl;
vector<int> v1(5,1);
printcontainer(v1);
cout << endl;
vector<string> v2(5, "2");
printcontainer(v2);
cout << endl;
vector<int>v3(v1);
printcontainer(v3);
cout << endl;
vector<int> v4(v1.begin(),v1.end()-2);
printcontainer(v4);
cout << endl;
vector<int> v5(5, 3);
v4 = v5;
printcontainer(v4);
cout << endl;
vector<int> v6;
v6.Resize(5, 9);
printcontainer(v6);
cout << endl;
int arr[] = { 16,2,77,29 };
vector<int>v7(arr, arr + sizeof(arr) / sizeof(int));
printcontainer(v7);
cout << endl;
vector<int>v8({1,2,3,4,6});
printcontainer(v8);
cout << endl;
}
//插入删除 测试
void test2()
{
vector<int> v1;
for (int i = 5; i > 0; i--)
{
v1.Push_back(i);
}
printcontainer(v1);
cout << endl;
vector<int> v2(5, 4);
v1.Insert(v1.begin(),v2.begin()+1,v2.end()-1);
printcontainer(v1);
cout << endl;
v1.Insert(v1.begin(), 4);
printcontainer(v1);
cout << endl;
v1.Erase(v1.begin(),v1.begin() + 3);
printcontainer(v1);
cout << endl;
v1.Erase(v1.begin());
printcontainer(v1);
cout << endl;
}
//修改和查找数据测试
void test3()
{
vector<int> v1(5, 1);
for (auto& ch : v1)
{
ch *=10;
}
printcontainer(v1);
cout << endl;
v1[3] *= 10;
printcontainer(v1);
cout << endl;
size_t i = v1.Find(100);
cout << v1[i] << endl;
}
}
