1.vector的概念
1. vector 是表示可变大小数组的序列容器。2. 就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。3. 本质讲， vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候， vector 并不会每次都重新分配大小。4. vector 分配空间策略： vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。5. 因此， vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。6. 与其它动态序列容器相比（ deques, lists and forward_lists ）， vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起 lists 和forward_lists 统一的迭代器和引用更好。学习方法：使用 STL 的三个境界：能用，明理，能扩展 ，那么下面学习 vector ，我们也是按照这个方法去学习
2.vector的构造函数
2.1构造函数
1.vector<int>()创建一个空的vector(注意尖括号里面的代表类型只要是合法的类型都可以
vector<int>();
2.定义一个具有十个元素的的向量（可以给初始值如果不给初始值默认给缺省值）
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1(10); vector<int>v2(10, 1);//可以给这十个元素初始值 }
?3.用向量v1拷贝给向量v2
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1(10, 1); vector<int>v2(v1); return 0; }
4.将向量v1中0~3共4个元素拷贝给v2同时也支持数组
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1(10, 1); vector<int>v2(v1.begin(), v1.begin() + 4); return 0; }
数组也是可以进行上述操作的：
#include<iostream> #include<vector> using namespace std; int main() { int arr[] = { 1,2,3,4,5,5,6,7,8,8 }; vector<int>v2(arr,arr+4); return 0; }
5.匿名构造法?
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1 = { 1,2,3 }; vector<int>v2 = vector<int>(1);//匿名对象 return 0; }
?3.vector的常用操作
vector中的基本常用操作包括了插入删除变量等等
3.1插入操作
vector的插入操作有两种一种是在尾部插入一种是在任意位置插入
void push_back(x);
iterator insert(iterator pos,x);
我们先来看第一种在尾部插入：
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; v1.push_back(10); v1.push_back(11); v1.push_back(12); for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
运行结果：
2在任意位置之前插入但是值得注意的是这个位置给的是迭代器。?insert有3个版本
?我们先来看第一个在当个位置之前插入：
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; v1.push_back(10); v1.push_back(11); v1.push_back(12); v1.insert(v1.begin() + 1, 14);//在11位置之前插入一个14； for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
运行结果：
?在这里我们只需要会一个就行了
3.2删除操作
删除操作主要有在尾部删除和任意位置删除
我们首先来看尾删
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; v1.push_back(10); v1.push_back(11); v1.push_back(12); v1.pop_back();//将尾部的12删除 for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
运行结果：
在任意位置删除同样的要给迭代器才可以删除
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; v1.push_back(10); v1.push_back(11); v1.push_back(12); v1.erase(v1.begin() + 1);//将11这个元素删除 for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
?3.3vector中获取元素的方式：
1.operator[]
2.对象.at(下标）；
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; v1.push_back(10); v1.push_back(11); v1.push_back(12); cout << v1[0] << " " << v1.at(0) << endl; return 0; }
?运行结果：
那[]和at有什么区别吗？区别就是当这个下标不合法时[]会直接断言终止掉程序而at会抛出异常?
初学者在operator[]非常容易错的地方是operator只能获取已经存在的元素?很有肯能就写出来这样的错误代码
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1; cout << v1[1] << endl;//这是错误的应为v1是一个空对象 return 0; }
vector中还支持直接获取头部元素和尾部元素 。
1.对象.front()?
2.对象.back();
对应代码：
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; cout << v1.front() << " " << v1.back() << endl; return 0; }
3.4vector中的迭代器
vector容器中的迭代器begin ,end,rbegin,rend,cbegin,cend;
?注意在vector中begin指向的是第一个元素而end指向的不是最后一个元素而是最后一个元素的下一个位置
而rbegin()和rend（）则与此正好相反rend指向第一个元素的前一个位置而rbegin指向最后一个位置
3.4vector中的遍历方式：
1.和数组一样通过operator[]遍历或者at
2.通过迭代器遍历
3.通过范围for遍历
4.通过算法中的for_each遍历
?1.和数组一样遍历：
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
2.迭代器方式遍历:
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; auto it = v1.begin(); while (it != v1.end()) { cout << *it << " "; it++; } return 0; }
3.通过范围for遍历
#include<iostream> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; for (auto x : v1) { cout << x << " "; } return 0; }
?方式四：通过for_each遍历：
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; for_each(v1.begin(), v1.end(),[](int val) {cout << val << " "; });//第三个参数可以填仿函数或者lamber表达式 return 0; }
运行结果均为:
注意在范围for中如果要修改vector中的值这样是无法修改的
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; for (auto x : v1) { x -= 1; } for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
?运行结果：
这是为什么了呢？这是因为 范围for中只是将v1中的值赋值给x，x的改变不会v1中值，而x是一个局部变量出了作用域就不在了。如果要想改变v1中的值就要使用引用。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; for (auto& x : v1) { x -= 1; } for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } return 0; }
?运行结果：
迭代器失效
向容器中添加或者删除元素的操作可能会使指向容器元素的迭代器失效，失效的迭代器将不指向任何元素。
一般有两种情况无法通过迭代器++操作遍历整个stl容器;?无法通过迭代器存取迭代器所指向的内存。
vector中常见的迭代器失效
1.删除当前的iterator会使后面所有元素的iterator都失效。这是因为顺序容器内存是连续分配（分配一个数组作为内存），删除一个元素导致后面所有的元素会向前移动一个位置。（删除了一个元素，该元素后面的所有元素都要挪位置，所以，it++，已经指向的是未知内存）。?
2.迭代器在内存连续的容器中插入元素迭代器失效这是因为扩容的过程中可能重新开辟了空间不在是原来那一块空间了，内存非连续得容器插入迭代器不失效。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; auto it = v1.begin(); while (it!=v1.end()) { if (*it % 2 == 0) {//删除偶数 v1.erase(it); } else { it++; } } return 0; }
比如这个我们想要删除所有偶数的程序初学者可能会认为这是没有问题的但是实际上当删除一个偶数时迭代器已经失效了此时层序会崩溃?
?
?如何解决这个问题呢？我们可以利用erase的返回值返回下一个迭代器给it即可
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int>v1{ 1,2,3,4 }; auto it = v1.begin(); while (it!=v1.end()) { if (*it % 2 == 0) { it=v1.erase(it); } else { it++; } } return 0; }
vector中还有一些接口：
size获取数据个数capacity获取容量大小empty判断是否为空resize （重点）改变 vector 的 sizereserve （重点）预留空间?在这里面要注意的是resize是开空间并且初始化而reserve是只开空间
resize的规则：
1.当所给值大于当前的capacity时将capacity扩容到该值，扩容的第二个参数为所给值如果没有给出则默认是T（）即T的缺省值
2.当所给值小于当前size时当size减小到该值即可
reserve的规则：
1.当所给值小于当前capacity则什么都不做
2.当所给值大于当前capacity则扩容到该值即可
?4.vector的模拟实现
一般vector对象中会有三个成员变量_start指向容器中有效位置的头，_finish指向容器中有效位置的尾，_endofstorage指向整个容器的尾
private: iterator _start;//开始 iterator _finish; iterator _endofstorage;//空间的末尾
而iterator是typedef出来的
typedef T* iterator; typedef const T* const_iterator;
?4.1构造函数
默认的构造函数和半缺省构造函数
vector(int Size=0, const T& val=T())// :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { assert(Size >0); _start = new T[Size]; if (_start>=0) { for (int i = 0; i < Size; i++) {//给每一个位置赋值 _start[i] = val; } _finish = _start + Size; _endofstorage = _start + Size; } }
?4.2拷贝构造函数
拷贝构造函数有现代写法和传统写法
传统写法：
vector(const vector<int>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr){ _start = new T[v.capacity()];//开空间 _finish = _start; _endofstorage = _start + v.capacity(); for (int i = 0; i < v.size(); i++) {//赋值 *_finish = v[i]; ++_finish; } }
在这里需要注意的是不要使用memcopy来拷贝数据这是因为memcopy是浅拷贝是按字节拷贝的当vector中的T为string 类型会发生同一块内存析构两次从而使程序崩溃。在这里我们可以通过赋值的方式调用string 中自己的operator=赋值运算符重载?
现代写法：
vector(const vector<int>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { reserve(v.capacity());//先预留和v一样的空间 for (const auto& x : v) { push_back(x);//将v中的数据一个一个尾插过来 } }
?4.3析构函数
~vector() { if (_start) { delete[] _start;//释放空间 _start = _finish = _endofstorage = nullptr; } }
4.4赋值运算符重载
?同样的赋值运算符重载也有现代写法和传统写法
传统写法：
vector<T>& operator=(const vector<T>&v) { if (this != &v) { delete[]_start;//释放旧空间 _start = new T[v.capacity()]; for (int i = 0; i < v.size(); i++) { (_start + i) = v[i];//拷数据 } _endofstorage = _start + v.capacity();//整个容器的尾 _finish = _start + v.size();//有效数据的尾 } return *this;//支持连等 }
现代写法 ：
vector<T>& operator=(vector<T>v) { if (this != &v) {//防止自己给自己赋值 swap(_start, v._start); swap(_finish, v._finish); swap(_endofstorage, v._endofstorage); } return *this;//支持连等 }
利用传参时?拷贝出来的v将v的成员和自己的成员一换即可。注意不要用算法库里面的因为算法库里面的是深拷贝代价极大
4.5swap?
void swap(vector<int>& v) { ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endofstorage, v._endofstorage); }
swap函数的作用是交换两个容器中的数据我们可以直接调用算法库中的swap函数交换各自对应的成员变量即可?
?4.6容量函数
size_t size() const { return _finish - _start; } size_t capacity()const { return _endofstorage - _start; }
利用指针减指针为两个指针之间数据的个数
4.7迭代器
在vector中迭代器实际上底层是原生指针?
?
typedef T* iterator; typedef const T* const_iterator;
const_iterator begin()const { return _start;//返回容器中的首地址 } iterator begin() { return _start;//返回容器中的首地址 } iterator end(){ return _finish;//返回容器中最后一个位置的下一个位置 } const_iterator end()const { return _finish;//返回容器中最后一个位置的下一个位置 }
此处有两个版本的原因是为了让const对象也能调迭代器的接口?
?4.8 reserve
void reserve(int n) { if (n > capacity()) { int len = size(); T* tmp = new T[n];//开空间 if (_start) { memcpy(tmp, _start, sizeof(T) * len);//拷数据 delete[]_start;//释放旧空间 } //指向新空间 _start = tmp; _finish = tmp + len; _endofstorage = tmp + n; } }
4.9尾插push_back（）
void push_back(const T& x) { if (_finish == _endofstorage) {//判断是否需要增容 size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity);//开空间 } *_finish = x; ++_finish; }
???
首先判断是否需要增容然后直接将数据放到_finish即可，在将_finish往后移即可
4.10 resize
我们根据resize的规则?
1.当所给值大于当前的capacity时将capacity扩容到该值，扩容的第二个参数为所给值如果没有给出则默认是T（）即T的缺省值
2.当所给值小于当前size时当size减小到该值即可
void resize(size_t n,const T&val=T()) { if (n < size()) {//n小于当前的size _finish = _start + n; } else { if (n > capacity()) {//判断是否需要增容 reserve(n);//开空间 } while (_finish < _start + n) { *(_finish) = val;//初始化 ++_finish; } } }
4.11判断是否为空对象 empty
bool empty(){ return _start == _finish; }
?4.12?尾删pop_back()
我们只需要将_finish往前移即可?
void pop_back() { assert(_start<_finish); --_finish; }
?4.13 insert
iterator Insert(iterator pos,const T&x) { assert(pos <= _finish); if (_finish == _endofstorage) { size_t n = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity);//扩容 pos = _start + n;//计算pos在新空间中的位置 } iterator end = _finish-1; while (end >= pos) { *(end + 1) = *end;//移动数据 --end; } *pos = x;//将数据放到对应的位置即可 ++_finish;// 后移 return pos;//返回pos所指向元素的位置 }
?4.12 earse
iterator Erase(iterator pos) { assert(pos < _finish); iterator it = pos; while (it< _finish) { *it = *(it + 1);//移动数据将pos位置的数据覆盖 ++it; } --_finish; return pos;//返回pos所指向的位置 }
4.13opeator[]
T&operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i) const{ assert(i < size()); return _start[i]; }
?代码汇总：
#pragma once #include<assert.h> #include<iostream> using namespace std; namespace ksy { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector(int Size=0, const T& val=T())// :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { assert(Size >0); _start = new T[Size]; if (_start>=0) { for (int i = 0; i < Size; i++) {//给每一个位置赋值 _start[i] = val; } _finish = _start + Size; _endofstorage = _start + Size; } } vector<T>& operator=(const vector<T>&v) { if (this != &v) { delete[]_start;//释放旧空间 _start = new T[v.capacity()]; for (int i = 0; i < v.size(); i++) { (_start + i) = v[i];//拷数据 } _endofstorage = _start + v.capacity();//整个容器的尾 _finish = _start + v.size();//有效数据的尾 } return *this;//支持连等 } void swap(vector<int>& v) { ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endofstorage, v._endofstorage); } ~vector() { if (_start) { delete[] _start;//释放空间 _start = _finish = _endofstorage = nullptr; } } vector(const vector<int>& v) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { reserve(v.capacity()); for (const auto& x : v) { push_back(x); } } const_iterator begin()const { return _start; } iterator begin() { return _start; } iterator end(){ return _finish; } const_iterator end()const { return _finish; } iterator Erase(iterator pos) { assert(pos < _finish); iterator it = pos; while (it< _finish) { *it = *(it + 1); ++it; } --_finish; return pos; } void pop_back() { assert(_start<_finish); --_finish; } bool empty(){ return _start == _finish; } iterator Insert(iterator pos,const T&x) { assert(pos <= _finish); if (_finish == _endofstorage) { size_t n = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity);//扩容 pos = _start + n;//计算pos在新空间中的位置 } iterator end = _finish-1; while (end >= pos) { *(end + 1) = *end;//移动数据 --end; } *pos = x;//将数据放到对应的位置即可 ++_finish;// 后移 return pos; } void resize(size_t n,const T&val=T()) { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish < _start + n) { *(_finish) = val; ++_finish; } } } void reserve(int n) { if (n > capacity()) { int len = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * len); delete[]_start; } _start = tmp; _finish = tmp + len; _endofstorage = tmp + n; } } void push_back(const T& x) { if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; Insert(_finish, x); } T&operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i) const{ assert(i < size()); return _start[i]; } size_t size() const { return _finish - _start; } size_t capacity()const { return _endofstorage - _start; } private: iterator _start; iterator _finish; iterator _endofstorage; }; void test_vector() { vector<int>ans(3); for (int i = 0; i < 3; i++) { cout << ans[i]; } } }