初阶7 vector

本章重点

vector的介绍
vector的使用
vector的模拟实现

1.vector的介绍

vector就类似数据结构中的顺序表

vector是表示可变大小数组的序列容器。

就像数组一样，vector也采用的连续存储空间来存储元素。
意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理

本质讲，vector使用动态分配数组来存储它的元素。
当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小

vector分配空间策略:vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大

vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长

与其它动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效 ,对于其它不在末尾的删除和插入操作，效率更低

2. vector的使用

2.1 常见构造

请添加图片描述

无参构造一个空的容器
构造并初始化 n 个 val 容器
拷贝构造某类型容器
使用迭代器进行初始化构造

//1）无参构造一个空的容器
vector<int> v1; //构造一个int类型的空容器//2）构造并初始化 n 个 val 容器 
vector<int> v2(10, 1); //构造含有10个1的int类型容器//3）拷贝构造某类型容器
vector<int> v3(v2); //拷贝构造int类型的v2容器//4）使用迭代器进行初始化构造
vector<int> v4(v2.begin()+1, v2.end()-1); //使用迭代器拷贝构造v2容器的某一段内容//当然也可以用使用迭代器(不止自己的)构造其他类型的容器，string s("hello world");vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容int a[]={1,2,3};vector<char> v5(a,a+3);

2.2 vector的迭代器

请添加图片描述

2.2.1 begin 和 end

通过 begin 函数可以得到容器中第一个元素的正向迭代器

通过 end 函数可以得到容器中最后一个元素的后一个位置的正向迭代器

左闭右开

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//正向迭代器遍历容器vector<int>::iterator it = v.begin();//也可以用auto来自动识别：auto it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}return 0;
}

2.2.2 rbegin 和 rend

通过 rbegin 函数可以得到容器中最后一个元素的反向迭代器

通过 rend 函数可以得到容器中第一个元素的前一个位置的反向迭代器

左开右闭

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//反向迭代器遍历容器vector<int>::reverse_iterator it = v.rbegin();//也可以用auto来自动识别：auto it = v.rbegin();while (it != v.rend()){cout << *it << " ";it++;}return 0;
}

2.2.3 补充:sort算法

头文件:#include <algorithm>
用法:

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
using namespace std;int main () {int myints[] = {32,71,12,45,26,80,53,33};vector<int> myvector (myints, myints+8);//部分升序32 71 12 45 26 80 53 33sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33sort (myvector.begin(), myvector.end()); //全部升序(12 26 32 33 45 53 71 80)sort (myvector.rbegin(), myvector.rend());//全部降序return 0;
}

2.3 vector的遍历方式

2.3.1 [ ] + 下标

vector 对 [ ] 运算符进行了重载，所以我们可以直接使用 [ ]+下标访问或修改对象中的元素

int main()
{vector<int> v1; // 定义容器v1// 尾插5个数据v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);// 使用下标访问数据for (size_t i = 0; i < v1.size(); ++i){cout << v1[i] << " ";}cout << endl;// 使用下标修改数据for (size_t i = 0; i < v1.size(); ++i){v1[i] += 3;cout << v1[i] << " ";}cout << endl;return 0;
}

2.3.2 通过迭代器进行访问：

begin 获取一个字符的迭代器， end获取最后一个字符下一个位置的迭代器

int main()
{vector<int> v2; // 定义容器v2// 尾插5个数据v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);// 使用迭代器访问数据vector<int>::iterator it1 = v2.begin();while (it1 != v2.end()){cout << *it1 << " ";it1++;}cout << endl;// 使用迭代器修改数据vector<int>::iterator it2 = v2.begin();while (it2 != v2.end()){*it2 += 1;cout << *it2 << " ";it2++;}return 0;
}

2.3.3 范围for：

int main()
{vector<int> v3; // 定义容器v3// 尾插5个数据v3.push_back(1);v3.push_back(2);v3.push_back(3);v3.push_back(4);v3.push_back(5);// 使用范围for访问数据for (auto a : v3){cout << a << " ";}cout << endl;// 使用范围for修改数据for (auto& a : v3){a += 4;cout << a << " ";}return 0;
}

2.4 vector的容器

请添加图片描述

主要了解：

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

2.4.1 reserve

reserve函数用来改变vector的最大容量

不多强调,只注意:

int main()
{vector<int> v3; // 定义容器v3v3.reverse(10)for (size_t i = 0; i < 10;i++){v3[i]=i;}return 0;
}

错误
因为[]的重载在assert中规定i<a_size
而reserve变大了capacity,但size不变
所以此处应用resize

2.4.2 resize

resize 函数改变容器中的有效元素个数

int main()
{vector<int> v1(6, 3);v1.reserve(20);cout << v1.capacity() << endl;cout << v1.size() << endl << endl;v1.resize(10);cout << v1.capacity() << endl;cout << v1.size() << endl;return 0;
}

reserve 只负责开辟空间，如果确定知道需要用多少空间，可以用 reserve 缓解 vector 扩容代价，reserve不会影响size
resize 在开空间的同时还会进行初始化，会影响 size。

2.5 vector 的增删改查

请添加图片描述

push back:尾插
pop back:尾删
insert:可以在所给迭代器位置插入一个或多个元素

1）插入一个值：

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//在容器头部插入9v.insert(v.begin(), 9);//在位置2插入6v.insert(v.begin()+2, 6);//打印for (auto e : v) {cout << e << " ";}return 0;
}

2）插入多个值：

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//在容器头部插入2个4v.insert(v.begin(), 2, 4);//打印for (auto e : v) {cout << e << " ";}return 0;
}

erase:用来删除所给迭代器位置的元素，或者删除所给迭代器区间内的所有函数（左闭右开）

1）删除一个值

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//头删v.erase(v.begin());//尾删v.erase(v.end()-1); //因为是左闭右开区间，所以end-1才能删掉‘5’//打印for (auto e : v) {cout << e << " ";  //结果：2 3 4 }return 0;
}

2）删除一个区间的值

int main()
{vector<int> v;v.push_back(0);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);v.push_back(8);v.push_back(9);//删除在该迭代器区间内的元素（左闭右开]v.erase(v.begin()+3, v.end() - 3);//打印for (auto e : v) {cout << e << " ";//结果：0 1 2 7 8 9}return 0;
}

find

由于 vector 没有 find 函数，如果我们要用的话，我们需要去调用算法库里面的一个函数接口：find

使用 std:: find 需要包头文件 #include <algorithm>
可以看到 find 共有三个参数，前两个确定迭代器的区间，第三个参数确定所要寻找的返回值

函数在所给迭代器区间内寻找，
若找到，返回第一个匹配的元素，并返回它的迭代器
若未找到，返回第二个参数
int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 假设我要3的前面插入600//vector<int>::iterator pos = find(v.begin(), v.end(), 3);//上面的类型可以直接用auto去推算：auto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){cout << "找到" << endl;v.insert(pos, 600);}else{cout << "未找到" << endl;}for (auto e : v) {cout << e << " "; //结果： 1 2 600 3 4 5 6}return 0;
}

sort

sort 函数和 find 函数一样，在vector里面没有明确给出，需要用std库里面的：

也需要包头文件

1）默认升序：
int main()
{vector<int> v;v.push_back(7);v.push_back(1);v.push_back(0);v.push_back(-1);v.push_back(9);v.push_back(3);// 默认排升序sort(v.begin(), v.end());// 打印for (auto e : v){cout << e << " ";}return 0;
}
2）降序

排降序需要用到仿函数，就要包仿函数的头文件： #include <functional>
int main()
{vector<int> v;v.push_back(7);v.push_back(1);v.push_back(0);v.push_back(-1);v.push_back(9);v.push_back(3);// 排降序，需要包上仿函数的头文件 #include <functional> sort(v.begin(), v.end(), greater<int>());for (auto e : v){cout << e << " ";}return 0;
}
或用反向迭代器rbegin与rend

3.vector的模拟实现

请添加图片描述

#pragma once
#include<assert.h>
#include <string.h>
# include<iostream>
using namespace std;namespace ymz
{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():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){ }vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){/*_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();*/reserve(v.capacity());for (auto e : v){push_back(e);}}vector(size_t n, const T& val = T()){resize(n, val);}//vector<int> v(10,0); 会与下面的InputIterator冲突 //所以再次写一个重载vector(int n, const T& val = T()){resize(n, val);}//[first,last)template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}void swap(vector<T> v){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//会导致非内置类型(如:string)的浅拷贝//memcpy(tmp, _start, sizeof(T) * size()); //调用非内置类型自己的赋值运算for (size_t i = 0; i < n; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}void push_back(const T& x){/*if (_finish == _end_of_storage){size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);}*_finish = x;_finish++;*/insert(end(), x);}void pop_back(){erase(--end());}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}T& operator[](size_t pos){assert(pos < size());//return *(_start + pos); 与下面写法完全等价return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());//return *(_start + pos); 与下面写法完全等价return _start[pos];}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start; //避免迭代器失效,记录pos相对位置size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);pos = _start + len;			//更新pos位置,(这只能解决内部的迭代器失效)}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}