目录
- 一、vector的介绍及使用
- 1.1 介绍vector
- 1.2 vector的使用
- 1.2.1 构造
- 1.2.2 遍历访问
- 1.2.3 容量空间
- 1.2.4 增删查改
- 二、vector的模拟实现
- 2.1 成员变量
- 2.2 迭代器相关函数
- 2.3 构造-析构-赋值重载
- 2.3.1 无参构造
- 2.3.2 有参构造1
- 2.3.3 有参构造2
- 2.3.4 拷贝构造
- 2.3.5 赋值重载
- 2.3.6 析构
- 2.4 容量操作
- 2.4.1 size和capacity
- 2.4.2 reserve
- 2.4.3 resize
- 2.5 插入与删除
- 2.5.1 尾插
- 2.5.2 尾删
- 2.5.3 pos位置插入
- 2.5.3 pos位置删除
- 2.6 遍历访问
- 2.7 全部代码
- 2.7.1 vector.h
- 2.7.2 test.cpp
一、vector的介绍及使用
1.1 介绍vector
vector是一个可变大小数组的容器,与数组一样,vector也是一块连续的空间,可以像数组一样对元素进行高效的遍历访问,但是普通数组的大小是不变的,vector可以改变自身大小。vector是采用动态分配数组来存储数据,即插入新元素时要改变存储空间大小,往往要分配一个新的数组,然后把原来数组的元素转移到新的空间里。vector的尾插尾删效率高,中间插入和删除效率较低。
1.2 vector的使用
1.2.1 构造
1️⃣无参
vector()
vector<int> v;
2️⃣构造并初始化n个val
vector(size_type n, const value_type& val = value_type())
vector<int> v(10, 7);
3️⃣拷贝构造
vector (const vector& x)
vector<int> v1{ 1,2,3,4 };vector<int> v2(v1);
4️⃣使用迭代器进行初始化构造
vector (InputIterator first, InputIterator last)
vector<int> v1{ 5,6,7,8};vector<int> v2(v1.begin(), v1.end());
1.2.2 遍历访问
1️⃣begin+end
vector<int> v{ 1,2,3,4,5 };auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
获取数组第一个元素的位置,像指针一样遍历整个数组,直到最后一个元素结束。auto是自动推导类型。
2️⃣下标:operator[ ]
vector<int> v{ 1,2,3,4,5 };for (int i = 0; i < 5; i++){cout << v[i] << " ";}cout << endl;
3️⃣范围for
vector<int> v{ 1,2,3,4,5 };for (auto e : v){cout << e << " ";}cout << endl;
1.2.3 容量空间
1️⃣获取元素个数
vector<int> v{ 1,2,3,4,5 };cout << v.size() << endl;//5
2️⃣获取容量大小
vector<int> v{ 1,2,3,4,5 };cout << v.capacity() << endl;//5
3️⃣判断是否为空
vector<int> v;cout << v.empty() << endl;
4️⃣改变vector的size
void resize (size_type n, value_type val = value_type());
vector<int> v{ 1,2,3,4,5 };for (auto e : v){cout << e << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;v.resize(10, 9);cout << endl;for (auto e : v){cout << e << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;
如果超出原来的存储空间,那么capacity也会改变
5️⃣改变vector的capacity
void reserve (size_type n);
vector<int> v{ 1,2,3,4,5 };for (auto e : v){cout << e << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;v.reserve(10);cout << endl;for (auto e : v){cout << e << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;
1.2.4 增删查改
1️⃣尾插
vector<int> v{ 1,2,3,4,5 };v.push_back(9);for (auto e : v){cout << e << " ";}cout << endl;
2️⃣尾删
vector<int> v{ 1,2,3,4,5 };v.pop_back();for (auto e : v){cout << e << " ";}cout << endl;
3️⃣查找
注意查找不是vector的接口,是算法模块实现的。
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
vector<int> v{ 1,2,3,4,5 };auto it = find(v.begin(), v.end(), 2);cout << *it << endl;//2
4️⃣交换
void swap (vector& x);
vector<int> v1{ 1,2,3,4,5 };vector<int> v2{ 6,7,8,9,10 };v2.swap(v1);
5️⃣在pos位置插入
iterator insert (iterator position, const value_type& val);
vector<int> v{ 1,2,3,4,5 };auto pos = find(v.begin(), v.end(), 2);v.insert(pos, 10);for (auto e : v){cout << e << " ";}cout << endl;
6️⃣在pos位置删除
iterator erase (iterator position);//指定位置删除
iterator erase (iterator first, iterator last);//指定范围删除
有两种写法:
// 一:vector<int> v{ 1,2,3,4,5 };auto pos = find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout << e << " ";}cout << endl;
// 二:vector<int> v{ 1,2,3,4,5 };v.erase(v.begin() + 1, v.end() - 1);for (auto e : v){cout << e << " ";}cout << endl;
注意:insert 和 erase 一般只使用一次,重复使用可能导致迭代器失效。
二、vector的模拟实现
2.1 成员变量
vector的迭代器是一个原生指针,它的三个成员变量分别是:
typedef T* iterator;typedef const T* const_iterator;//————————iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;
这里在声明时先给成员变量缺省值为空指针,声明时给缺省值是给初始化列表的,后续写的时候就比较方便。
2.2 迭代器相关函数
begin函数返回空间的起始位置,end函数返回空间的最后一个有效元素的下一位。
// 通过迭代器访问元素时可修改iterator begin(){return _start;}iterator end(){return _finish;}// 通过迭代器访问元素时不可修改const_iterator begin() const {return _start;}const_iterator end() const{return _finish;}
2.3 构造-析构-赋值重载
2.3.1 无参构造
没有传参数
vector(){}
2.3.2 有参构造1
代码:
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{reserve(last - first);//复用扩容函数while (first != last)//判断条件{push_back(*first);//复用尾插函数++first;//尾插一次后加1}
}
这个函数看起来有些奇怪,为啥还要套一层模板呢?使用这里就不说了,其实这个构造函数的作用是:只要传进来的是迭代器就可以初始化该迭代器的内容,前提是该迭代器是指向连续物理空间的指针。比如用vector定义了一个v1,v1已经是构造好的,有具体的元素;再定义一个v2,我想让v2的内容跟v1是一样的,就可以使用这个函数,传的迭代器指向的是v1的头和尾,它就会构造出和v1一样的内容。前面的使用方法有代码。不仅可以vector传vector,还可以list传vector,只要是迭代器即可。
2.3.3 有参构造2
vector(size_t n, const T& x = T())
{resize(n, x);//复用修改元素个数函数
}
vector(int n, const T& x = T())
{resize(n, x);//复用修改元素个数函数
}
该构造函数是初始化为n大小的空间,每个元素是x。可以直接复用resize函数,下面会介绍。这里写了两个构造函数唯一的区别是size_t 和int ,因为如果只有size_t 类型的那个构造函数,构造时不会调用该函数,会调用前面的构造函数(有参构造1),这与函数模板的匹配调用原则有关。假如传进来的n不是size_t 类型,那么它就要发生隐式类型转换,但是编译器想,隐式类型转换感觉麻烦,就使用有模板的那个函数。
为了防止出现以上情况,同时是模拟实现,要尽可能像标准库里面的vector,所以多重载了一个函数,它的参数n是int 类型的,这样的话传进来的参数n是int 类型,那么它就会直接调用这个构造函数,避免了以上情况。
2.3.4 拷贝构造
拷贝构造要注意深浅拷贝问题
1️⃣写法1
vector(const vector<T>& v)
{_start = new T[v.capacity()];//开一样大的空间memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据_finish = _start + v.size();_endofstorage = _start + v.capacity();
}
与string的拷贝构造类似,开一块新空间,拷贝数据后,指向这个新空间,这样防止两个指针指向同一块空间。
写法1还要注意memcpy的深浅拷贝问题,与元素的类型有关,这个在后面会具体介绍,现在假设统一使用的元素类型先是 int 类型。
1️⃣写法2
vector(const vector<T>& v)
{reserve(v.capacity());//复用扩容函数for (const auto& e : v)//范围for循环直接放入数据即可{push_back(e);//复用尾插函数}
}
先开与参数v一样大的空间,然后使用范围for直接放入数据,只要参数v里面有元素,都可以把元素一个一个的尾插到要构造的空间里面,同时也不影响v,最终完成拷贝构造。
2.3.5 赋值重载
1️⃣写法1
vector<T>& operator=(const vector<T>& v)
{if (this != &v)//相同就不用赋值{T* tmp = new T[v.capacity()];//临时空间memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据delete[] _start;//清理旧空间_start = tmp;//指向新空间_finish = _start + v.size();//_endofstorage = _start + v.capacity();}return *this;
}
1️⃣写法2
与string的是一样的,直接代码:
vector<T>& operator=(vector<T> v)
{swap(v);//复用交换函数return *this;
}
//交换
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
2.3.6 析构
如果空间里有元素才清理,让3个指针置空;没有元素本来就是空指针不能清理。
~vector()
{if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;//}
}
2.4 容量操作
2.4.1 size和capacity
根据三个指针的指向,可以确定有效元素个数和容量的区间
//返回个数
size_t size() const
{return _finish - _start;
}
//返回容量
size_t capacity() const
{return _endofstorage - _start;
}
2.4.2 reserve
如果存储的元素超出原来的空间大小要扩容,扩容要开辟一块新空间,然后拷贝数据到新空间里,再让指针重新指向这块新空间。
代码:
//扩容
void reserve(size_t n)
{if (n > capacity())//满了要扩容{size_t old = size();//记录当前元素个数T* tmp = new T[n];//新空间if(_start){//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝for (size_t i = 0; i < old; i++){tmp[i] = _start[i];//深拷贝}delete[] _start;//释放就空间}_start = tmp;//指向新空间_finish = _start + old;//防止迭代器失效_endofstorage = _start + n;}
}
问题1:为什么要定义变量old
开空间拷贝数据后,旧空间被释放,指向新空间,_finish等于_start 加上元素个数,注意,如果没有old前面先记录元素个数的值,加上的是调用size函数返回的元素个数,那么就会出现迭代器失效问题。因为_start已经指向新的空间,而_finish还是指向旧空间的某个位置,那个不同空间相减就出问题了。
所以这里提前用变量old记录好元素的个数,_finsih等于_start+old,就不会出现以上情况。
问题2:memcpy是浅拷贝
元素类型是int 等内置类型没关系,如果是自定义类型,比如string,这里就会出现浅拷贝的问题。
深拷贝的做法是以赋值的形式逐个把旧空间的字符串给新空间:
2.4.3 resize
该函数可通过参数n修改元素个数,超出容量也会扩容。主要分为以下3点:
1.n小于等于元素个数
2.n大于元素个数且小于等于容量
3.n大于容量
代码:
void resize(size_t n, const T& x = T())
{if (n <= size()){_finish = _start + n;//修改_finish指向即可}else//n>size(){size_t len = n - size();//n与元素个数的差值if (n > capacity())//n大于容量要扩容{reserve(n);//复用扩容函数}while (len--)//插入len个x,只要n大于size()都要插入{*_finish = x;++_finish;}}
}
2.5 插入与删除
2.5.1 尾插
void push_back(const T& x)
{if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;++_finish;
}
尾插数据,_finish 指向同_endofstorage说明空间内数据已满,要扩容。然后插入在_finish指向的位置插入数据,_finish往后移。
2.5.2 尾删
void pop_back()
{assert(size() > 0);//有元素才能删--_finish;
}
2.5.3 pos位置插入
首先断言pos的位置是否合理,然后凡是插入数据,都要检查是否需要扩容。接着挪动数据,在pos位置插入新的元素。
iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);//检查pos位置是否合理size_t len = pos - _start;//记录pos与开始位置差值if (_finish == _endofstorage)//满了要扩容{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;
}
这里唯一要注意的是如果有发生扩容,pos的位置要进行更新。
2.5.3 pos位置删除
判断pos位置是否合理,然后挪动数据往前覆盖一个元素。
iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;
}
2.6 遍历访问
遍历访问有两种实现方式,一种是迭代器,前面已经写过了,另一种是方括号重载运算符,即我们常见的下标。
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}
2.7 全部代码
2.7.1 vector.h
#include <iostream>
#include <assert.h>
using namespace std;namespace yss
{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;}//构造1vector(){}//构造2vector(size_t n, const T& x = T()){resize(n, x);}vector(int n, const T& x = T()){resize(n, x);}//构造3template<class InputIterator>vector(InputIterator first, InputIterator last){reserve(last - first);while (first != last){push_back(*first);++first;}}//拷贝构造//写法1//vector(const vector<T>& v)//{// _start = new T[v.capacity()];//开一样大的空间// memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据// _finish = _start + v.size();//// _endofstorage = _start + v.capacity();//}//写法2vector(const vector<T>& v){reserve(v.capacity());for (const auto& e : v){push_back(e);}}//赋值重载//写法1//vector<T>& operator=(const vector<T>& v)//{// if (this != &v)// {// T* tmp = new T[v.capacity()];//临时空间// memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据// delete[] _start;// _start = tmp;// _finish = _start + v.size();//// _endofstorage = _start + v.capacity();// }// return *this;//}//写法2vector<T>& operator=(vector<T> v){swap(v);return *this;}//析构~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;//}}//返回个数size_t size() const{return _finish - _start;}//返回容量size_t capacity() const{return _endofstorage - _start;}//交换void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//扩容void reserve(size_t n){if (n > capacity())//满了要扩容{size_t old = size();//记录当前元素个数T* tmp = new T[n];//新空间if(_start){//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝for (size_t i = 0; i < old; i++){tmp[i] = _start[i];//深拷贝}delete[] _start;//释放就空间}_start = tmp;//指向新空间_finish = _start + old;//防止迭代器失效_endofstorage = _start + n;}}//改变元素个数void resize(size_t n, const T& x = T()){if (n <= size()){_finish = _start + n;}else{size_t len = n - size();if (n > capacity()){reserve(n);}while (len--){*_finish = x;++_finish;}}}//尾插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(){assert(size() > 0);--_finish;}//pos位置插入iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);size_t len = pos - _start;//记录pos与开始位置差值if (_finish == _endofstorage){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;}//pos位置删除iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}//下标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:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
2.7.2 test.cpp
#include"vector.h"int main()
{/*yss::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;*//*yss::vector<int> v(10);for (auto e : v){cout << e << " ";}cout << endl;*//*yss::vector<int> v1(5, 99);yss::vector<int> v2(v1.begin(), v1.end());for (auto e : v2){cout << e << " ";}cout << endl;*//*yss::vector<int> v1(5, 55);yss::vector<int> v2(v1);for (auto e : v2){cout << e << " ";}cout << endl;*//*yss::vector<int> v1(7, 44);yss::vector<int> v2 = v1;for (auto e : v2){cout << e << " ";}cout << endl;*//*yss::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);auto pos = find(v.begin(), v.end(), 2);v.insert(pos, 99);for (auto e : v){cout << e << " ";}*//*yss::vector<int> v;v.push_back(1);v.push_back(22);v.push_back(43);v.push_back(64);v.push_back(85);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;*/return 0;
}