vector的简单介绍:
头文件:
#include<vector>
vector是属于STL的一员,虽然vector的英文意思是向量,但是vector就是一个顺序表;
对于vector来说,面对string的设计的复杂和冗余,vector就简洁很多了;
vector就是一个标准的模板,作为类模板,vector只能是显式实例化;
vector的使用:
构造:
(constructor) 构造函数声明 | 接口说明 |
---|---|
vector() (重点) | 无参构造 |
vector ( size_type n, const value_type&val = value_type()) | 构造并初始化 n 个 val |
vector (const vector& x); (重点) | 拷贝构造 |
vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
//对于类模板是要显式实例化的<type_name>
//无参构造
vector<int> v1;
//初始化一个数组,数组有10个1
vector<int> v2(10, 1);
//用迭代器的区间进行初始化
vector<int> v3(++v2.begin(), --v2.end());
//用其他容器的迭代器初始化
//........
迭代器:
iterator 的使 用 | 接口说明 |
---|---|
begin + end (重点) | 获取第一个数据位置的 iterator/const_iterator , 获取最后一个数据的下一个位置的iterator/const_iterator |
rbegin + rend | 获取最后一个数据位置的 reverse_iterator ,获取第一个数据前一个位的reverse_iterator |
vector 空间增长问题:
容量空间 | 接口说明 |
---|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize (重点) | 改变 vector 的 size |
reserve (重点) | 改变 vector 的 capacity |
vector 增删查改:
vector 增删查改 | 接口说明 |
---|---|
push_back (重点) | 尾插 |
pop_back (重点) | 尾删 |
find | 查找(注意这个是算法模块实现,不是 vector 的成员接口) |
insert | 在 position 之前插入 val |
erase | 删除 position 位置的数据 |
swap | 交换两个 vector 的数据空间 |
operator[] (重点) | 像数组一样访问 |
vector没有提供find,但是在算法中有提供find(函数模板),因为string不仅要find一个字符,还要find一个字符串,所以不用算法里面的find,string比较特殊,所以自己实现
int x;
cin >> x;
auto pos = find(v.begin(), v.end(), x);
C++要求:传迭代器区间都要传左闭右开
迭代器失效:
迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对 指针进行了封装 ,比如: vector 的迭代器就是原生态指针 T* 。因此 迭代器失效,实际就是迭代器底 层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间 ,造成的后果是程序崩溃 ( 即 如果继续使用已经失效的迭代器,程序可能会崩溃 )
会引起其底层空间改变的操作,都有可能是迭代器失效
比如:resize、reserve、insert、assign、push_back等。
1.类似于野指针:
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}}
void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}
问题出现在pos还指向在原来的空间,没有跟着变换到新的空间,所以,解决该问题的方法就是还原pos的相对位置:
void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}
另外:insert以后pos就实效了,不要去访问:因为pos还是指向旧的空间,其实就是形参的改变不影响实参,pos依旧是指向原来的位置,形参的改变并没有影响到实参,但是严格来说也不能加引用,这样就把带有常性的临时对象和普通引用放到一起了,权限放大了 ,如果const的话,那就不能修改了:(实在要访问修改的话,库中有说明,要访问就更新这个失效的迭代器的值)
int x;
cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{/*v.insert(p, 40);(*p) *= 10;*/p = v.insert(p, 40);(*(p + 1)) *= 10;
}
print_vector(v);
更新这个失效的迭代器的值:
iterator insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}
总之:还是不要访问的好 ,本质就是类似野指针。(空间扩容)
2.位置意义已经发生改变:
在没有发生扩容的时候,pos位置并没有跟随数据的向后移动而跟随,整体来说,pos已经不是指向原来数据,位置意义也已经发生改变,这种情况也可以称为迭代器失效(上面情况是空间扩容带来的类似野指针的行为)
3. 注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端:
// 1. 扩容之后,迭代器已经失效了,程序虽然可以运行,但是运行结果已经不对了
int main()
{vector<int> v{ 1,2,3,4,5 };for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;auto it = v.begin();cout << "扩容之前,vector的容量为: " << v.capacity() << endl;// 通过reserve将底层空间设置为100,目的是为了让vector的迭代器失效v.reserve(100);cout << "扩容之后,vector的容量为: " << v.capacity() << endl;// 经过上述reserve之后,it迭代器肯定会失效,在vs下程序就直接崩溃了,但是linux下不会// 虽然可能运行,但是输出的结果是不对的while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
//程序输出:
//1 2 3 4 5
//扩容之前,vector的容量为: 5
//扩容之后,vector的容量为 : 100
//0 2 3 4 5 409 1 2 3 4 5
// 2. erase删除任意位置代码后,linux下迭代器并没有失效
// 因为空间还是原来的空间,后序元素往前搬移了,it的位置还是有效的
#include <vector>
#include <algorithm>
int main()
{vector<int> v{ 1,2,3,4,5 };vector<int>::iterator it = find(v.begin(), v.end(), 3);v.erase(it);cout << *it << endl;while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
//程序可以正常运行,并打印:
//4
///4 5
// 3: erase删除的迭代器如果是最后一个元素,删除之后it已经超过end
// 此时迭代器是无效的,++it导致程序崩溃
int main()
{vector<int> v{ 1,2,3,4,5 };// vector<int> v{1,2,3,4,5,6};auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}for (auto e : v)cout << e << " ";cout << endl;return 0;
}
========================================================
// 使用第一组数据时,程序可以运行
[sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11
[sly@VM - 0 - 3 - centos 20220114]$ . / a.out
1 3 5
======================================================== =
// 使用第二组数据时,程序最终会崩溃
[sly@VM - 0 - 3 - centos 20220114]$ vim testVector.cpp
[sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11
[sly@VM - 0 - 3 - centos 20220114]$ . / a.out
Segmentation fault
4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效
#include <string>
void TestString()
{string s("hello");auto it = s.begin();// 放开之后代码会崩溃,因为resize到20会string会进行扩容// 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了// 后序打印时,再访问it指向的空间程序就会崩溃//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式写,运行时程序会崩溃,因为erase(it)之后// it位置的迭代器就失效了// s.erase(it);++it;}
}
vector的模拟实现:
要时常注意浅拷贝带来的问题:
代码:直接在类里面实现了_and_测试代码:(放在了头文件)
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<list>
using namespace std;
namespace home
{template<class T>class vector{public:typedef T* iterator;//模板typedef const T* const_iterator;//vector()//{}//写不写都会走初始化列表,有缺省值给到了(初始化)//C++11后//强制生成默认构造vector() = default;vector(const vector<T>& v){reserve(v.size());//提高效率,避免下面的扩容for (auto& e : v)//给引用,减少想string的拷贝{push_back(e);}}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=(const vector<T>& v)//类里面可以用类名替换类型,类外面不行vector& operator=(vector& v){//现代:swap(v);return *this;}//迭代器区间构造//类模板的成员函数,还可以继续是函数模板//这就可以是任意类型的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}void clear(){_finish = _start; }const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}size_t size()const{return _finish - _start;//左闭右开,相减得size数}size_t capacity()const{return _end_of_storage - _start;}void reserve(size_t n){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//对于string像这种数据深拷贝类型的,对于内置类型就没什么问题,memcpy会出问题,memcpy按字节拷贝,之前的被delete,变为随机值//解决:需要深拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];//调用赋值:释放旧空间,拷贝新空间}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}bool empty(){return _start == _finish;}void push_back(const T& x){if (_finish == _end_of_storage){//空间满了reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back(){assert(!empty());--_finish;}//迭代器失效iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}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);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}void resize(size_t n, const T val = T())//用默认构造去构造一个匿名对象,再去拷贝构造,但是编译器优化后是直接构造的,以后大概就是这种形式来给缺省值,但是在之前内置类型并没有构造,后来出现了模板,也有了内置类型的构造,析构概念{//n<size:删除//size<n<capacity:少的补val//n>capacity:开足够空间,少的补valif (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i)const{assert(i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage;};template<class T>void print_vector(const vector<T>& v){//编译器编译到这的时候,类模板是还没有被实例化的,并不知道vector<T>是什么,//类模板有一个原则://类模板没有被实例化的时候不敢到里面去取东西,因为里面的东西也有可能有各种的坑,分不清楚到底是类型还是静态成员变量//需要在前面+:typename(这就是于class的区别)//->规定:没有实例化的类模板里面取东西,编译器不能区分这里const_iterator是类型还是静态成员变量//还有一种解决方案:用autoauto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}//写成模板,打印各种容器(更通用)template<class Container>void print_container(const Container& v){auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.pop_back();for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;print_vector(v);vector<double> vd;vd.push_back(1.0);vd.push_back(2.2);vd.push_back(3.2);vd.push_back(4.2);vd.push_back(5.2);print_vector(vd);}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_vector(v);v.insert(v.begin() + 2, 30);print_vector(v);int x;cin >> x;auto p = find(v.begin(), v.end(), x);if (p != v.end()){/*v.insert(p, 40);(*p) *= 10;*/p = v.insert(p, 40);(*(p + 1)) *= 10;}print_vector(v);}void test_vector3(){int i = int();int j = int(1);int k(2);vector<int> v;v.resize(10, 1);v.reserve(20);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;v.resize(15, 2);print_container(v);v.resize(5);print_container(v);}void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);vector<int> v1 = v;print_container(v);vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v = v2;//v1之前的空间释放掉print_container(v);vector<int> v3(v.begin()+1, v.end()-1);print_container(v3);//模板价值//任意容器迭代器初始化//要求类型是匹配的list<int> lt;lt.push_back(12);lt.push_back(22);lt.push_back(32);vector<int> v4(lt.begin(), lt.end());print_container(lt);printf("\n");print_container(v4);vector<string> v5(10,"1111111");print_container(v5);//会报错,因为有模板的选择,匹配不上/*vector<int> v6(10, 1);print_container(v6);*///解决://指定访问最后这个vector<int> v6(10u, 1);print_container(v6);//再给一个更佳的选择(现成)vector<int> v7(10, 2);print_container(v7);}void test_vector5(){vector<string> v;v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");print_container(v);v.push_back("11111");print_container(v);}
}