0
0

C++打怪升级（十）- STL之vector

~~~~

在这里插入图片描述

前言

本节将要介绍STL容器中的vector的常用接口函数，简单模拟实现一下vector。

1. vector 是什么

vector

是可变大小的顺序容器，类似于数组，存放元素的空间是连续的，所以可以实现类似于数组的随机访问；
相对于其他容器

deque、list、forward_list

，vector的优势：

  • 尾插和尾删操作相对高效，访问元素时也是相当高效；

劣势：

  • 头插和中间插入元素、头删和中间删除元素的操作由于涉及到大量元素的移动，效率很低；
  • vector的空间可以动态的开辟，开辟空间是存在系统资源的消耗的，所以vector不是每新增一个元素就重新开辟空间，而是再空间满时开辟适当的空间，具体开辟多少空间取决于不同版本实现者的考虑。虽然每次开辟的空间没有具体要求，但是需要保证开辟空间是以对数间隔进行的，以便于每次在结束位置插入数据时vector能提供均摊的常数时间复杂度；
  • 与string的元素类型是char不同，vector是一个类模板，这意味着它可以接受任意类型的参数，存放任意类型的元素；

2. 见见vector的常用接口函数吧

构造函数

无参构造函数

函数声明

vector();

例子

vector<int> v;

注意不能写成

vector<int> v();

，定义初始化时，如果是无参构造或是全缺省的构造不加括号

()

，否则编译器会把这句代码识别成无参、返回类型是

vector<int>

的函数声明；只有这句代码并不会报错，但当你把v当做

vector<int>

类型的变量去使用时就会出现问题，因为编译器认为v是一个函数指针；

使用n个val构造

声明

vector(size_t n,const value_type& val =value_type());

eg

vector<char>v1(3,'x');// 结果为 xxx，没有'\0'
vector<int>v2(3,7)// 结果为 777

拷贝构造

声明

vector(const vector& x);

例子

// 5个9构造vector<int>类型对象 v1
vector<int>v1(5,9);

vector<int>v2(v1);

使用迭代器范围构造

声明
两个参数first和last都是迭代器类型，且该函数时函数模板，迭代器类型可以指定，即可以使用其他顺序容器的迭代器构造vector；

template<classInputIterator>vector(InputIterator first, InputIterator last);

eg

vector<int>v1(5,6);// 66666

vector<int>v2(v1.begin(), v1,begin()+3);// 666

初始化形参列表构造

声明
initializer_list是一个类模板，使用由大括号括起来的以逗号分隔的元素构造initializer_list对象；

vector(initializer_list<value_type> il);

eg

vector<int> v1{1,2,3,4,5};// 1 2 3 4 5
vector<int> v2 ={3,4,5,6,7);// 3 4 5 6 7

析构函数

声明
在vector对象销毁之前调用，释放vector对象申请的资源；

~vector();

赋值运算符重载函数

声明

vector&operator=(const vector& x);

eg
直接vector v2 = v1; 使用会被编译器当做定义初始化而调用拷贝构造函数，而不是赋值运算符重载函数；

vector<int>v1(5,6);// 66666
vector<int> v2;

v2 = v1;// 66666

元素访问

[]运算符重载函数访问

声明
[]运算符重载函数会在内部对传入的坐标参数进行严格检查，超出有效坐标范围将会报错，这与系统的抽查不同；
[]运算符重载函数既需要满足读也要满足写，所以实现了非const版本和const版本；

reference operator[](size_type n);
const_reference operator[](size_type n)const;

eg

非const

vector<int> v{1,2,3,4,5};for(int i =0; i < v.size();++i){
    v[i]++;
    cout << v[i]<<" ";// 结果为2 3 4 5 6}
cout << endl;

const

const vector<int> v{1,2,3,4,5};for(int i =0; i < v.size();++i){//v[i]++; 不能修改const对象成员
    cout << v[i]<<" ";// 结果为1 2 3 4 5}
cout << endl;

at函数访问

声明
at也会对传入的坐标参数进行判断，超出坐标范围后会抛异常，而不是报错；

reference at(size_type n);
const_reference at(size_type n)const;

eg

非const

vector<int> v{1,2,3,4,5};for(int i =0; i < v.size();++i){
    v.at(i)++;
    cout << v.at(i)<<" ";}
cout << endl;

const

const vector<int> v{1,2,3,4,5};for(int i =0; i < v.size();++i){
    cout << v.at(i)<<" ";}
cout << endl;

front函数

声明
返回第一个元素的引用

reference front();
const_reference front()const;

eg

vector<int> v{1,2,3,4};
v.first();// 结果为 1

back函数

声明
返回最后一个元素的引用

reference back();
const_reference back()const;

eg

vector<int> v{1,2,3};
v.back();// 结果为 3

迭代器相关

迭代器是像指针一样的类型，使用时需要解引用

*

正向迭代器

定义
包括非const和const迭代器；

返回vector对象内元素起始位置的迭代器

iterator begin()noexcept;
const_iterator begin()constnoexcept;

返回vector对象内元素结束位置的下一个位置的迭代器

iterator end()noexcept;
const_iterator end()constnoexcept;

eg

vector<int> v1{1,2,3,4,5};
vector<int>::iterator it = v1.begin();while(it != v1.end()){
    cout <<*it <<" ";// 结果为 1 2 3 4 5
    it++;}
cout << endl;

const vector<int> v2{6,7,8,9,0};
vector<int>::const_iterator cit = v2.begin();while(cit != v2.end()){
    cout <<*cit <<" ";// 结果为6 7 8 9 0
    cit++;}
cout << endl;

反向迭代器

定义

返回vector对象内最后一个元素的所在位置的迭代器

reverse_iterator rbegin()noexcept;
const_reverse_iterator rbegin()constnoexcept;

返回vector对象内第一个位置的元素的前一个理论位置的迭代器

reverse_iterator rend()noexcept;
const_reverse_iterator rend()constnoexcept;

eg

容量相关

size函数

声明
返回vector对象的元素个数

size_type size()constnoexcept;

eg

vector<int> v{1,2,3,4,5};
v.size();// 结果为 5

capacity函数

声明
返回vector对象的引用

size_type capacity()constnoexcept;

eg

vector<int> v{1,2,3,4,5};
v.capacity();// 结果为 5

empty函数

声明
判断vector对象是否为空，是则返回true；否则返回false

boolempty()constnoexcept;

eg

vector<int> v1;// 空
vector<int>v2(2,3);// 33

v1.empty();// true
v2.empty();// false

reserve函数

声明
参数

size_type n

，表示要申请开辟的容量大小；
改变vector对象的容量capacity，当

n

小于等于当前vector对象的容量capacity时，reserve函数什么也不做；
只有当

n

大于vector对象的容量时，reserve函数才会向系统申请开辟空间；即reserve函数一般只进行扩容处理，不缩容；

voidreserve(size_type n);

eg

vector<int> v{1,2,3,4,5};// capacity为 5

v.reserve(3);// capacity为 5

v.reserve(5);// capacity为 5

v.reserve(10);// capacity为 10

resize函数

声明
参数

size_t n

表示vector对象有效元素的个数；
如果

n

小于vector原有的

size

，相当于删除元素直到size为n；
如果

n

等于vector原有

size

就什么也不做；
如果

n

大于vector原有size且小于等于vector的原有capacity，相当于尾插元素直到size为n；
如果

n

大于vector原有的capacity，相当于先扩容使容量增大，再尾插元素直到size为n；

voidresize(size_type n);voidresize(size_type n,const value_type& val);

eg

vector<int> v2{1,2,3,4,5};
    v2.reserve(10);
    cout << v2.size()<< endl;
    cout << v2.capacity()<< endl;print(v2);

    v2.resize(3);
    cout << v2.size()<< endl;
    cout << v2.capacity()<< endl;print(v2);

    v2.resize(8,1);
    cout << v2.size()<< endl;
    cout << v2.capacity()<< endl;print(v2);

    v2.resize(15,2);
    cout << v2.size()<< endl;
    cout << v2.capacity()<< endl;print(v2);

image.png

增删查改相关

push_back函数

声明
在vector对象内最后一个元素的末尾增加一个元素，增加的元素

参数val

的拷贝；

voidpush_back(const value_type& val);voidpush_back(value_type&& val);

eg

vector<int> v;for(int i =0; i <5;++i){
    v.push_back(i);}// v的内容为 0 1 2 3 4

pop_back

声明
删除vecrot的最后一个元素，但是debug模式下，当vector为空时调用pop_back尾删元素时程序会出错；

voidpush_back(const value_type& val);voidpush_back(value_type&& val);

eg

vector<int> v;for(int i =0; i <5;++i){
    v.push_back(i);}// v的内容为 0 1 2 3 4 for(int i =0; i <5;++i){
    v.pop_back();}// v的内容为 空

assign函数

声明
使用参数

迭代器first和last

表示元素的起始位置和结束位置；
使用迭代器范围内的元素为vector赋值，同时会把vector原先的内容去除；
这个范围是左闭右开的区间

[first, last]

；

// range (1)template<classInputIterator>voidassign(InputIterator first, InputIterator last);

eg

vector<int> v1{1,2,3,4};
vector<int> v2;
v2.assign(v1.begin(), v1.end());// 结果为 1 2 3 4

声明
使用

size_t类型的n

个

value_type类型的val

为vector赋值；

// fill (2)    voidassign(size_type n,const value_type& val);

eg

vector<int> v1{1,2,3,4};
vector<int> v2;
v2.assign(3,5);// 结果为 555

声明
使用初始化列表对vector对象进行赋值

// initializer list (3)    voidassign(initializer_list<value_type> il);

eg

vector<int> v2;
v2.assign({1,2,3,4,5});// 结果为 1 2 3 4 5

insert函数

声明
参数

const_iterator pos

是vector内的元素对应位置的迭代器；
参数

const value_type

是待插入的值；
在迭代器位置

pos

之前插入一个元素，该元素是

val

的拷贝；

// single element (1)
iterator insert(const_iterator pos,const value_type& val);

eg

vector<int> v3{1,2,3,4,5}; 
v3.insert(v3.begin()+3,9);// 结果为 1 2 3 9 4 5

声明
参数

const_iterator pos

是vector内的元素对应位置的迭代器；
参数

size_type n

是插入元素的个数；
参数

const value_type

是待插入的值；
在迭代器位置

pos

之前插入

n

个元素；

// fill (2)    
iterator insert(const_iterator pos, size_type n,const value_type& val);

eg

vector<int> v3{1,2,3,4,5}; 
v3.insert(v3.begin()+3,5，9);// 结果为 1 2 3 9 9 9 9 9 4 5

声明
参数

const_iterator pos

是vector内的元素对应位置的迭代器；
参数

first、last

是迭代器范围，first是起始位置，last是结束位置；
在迭代器pos位置之前依次插入

[first, last)

范围内的所有元素；

// range (3)    template<classInputIterator>
iterator insert(const_iterator pos, InputIterator first, InputIterator last);

eg

vector<int> v1{1,2,3,4,5};

vector<int> v2{1,2,3,4,5};
v4.insert(v2.begin()+4, v1.begin(), v1.begin()+3);// 结果为 1 2 3 4 1 2 3 5

声明

// initializer list (5)    
iterator insert(const_iterator pos, initializer_list<value_type> il);

eg

vector<int> v{1,2,3,4};
v.insert(v.begin(),{2,3,3});// 结果是 1 2 3 2 3 3 4

erase函数

声明
参数

const_iterator pos

表示vector内元素所在位置的迭代器；
删除

pos

位置的元素；

iterator erase(const_iterator pos);

eg

vector<int> v{1,2,3,4,5};
v.erase(v.begin()+2);

声明
参数

first

是待删除范围的起始元素的位置；
参数

last

是待删除范围的最后一个元素的下一个位置；
删除迭代器范围内的所有元素；

iterator erase(const_iterator first, const_iterator last);

eg

vector<int> v{1,2,3,4,5};
v.erase(v1.begin()+1, v.begin()+4);

clear函数

声明
清空vector对象，删除所有元素；

voidclear()noexcept;

eg

vector<int> v2{9,9,9,9,9};// size = 5, capacity = 5

v2.clear();// size = 0, capacity = 5

swap函数

声明
与另一个vector对象进行内容的交换，也包括size和capacity；

voidswap(vector& x);

eg

vector<int> vv1{1,2,3,4,5};// size=5, capacity=5;
vector<int> vv2{6,6,6};// size=3, capacity=3;

vv1.swap(vv2);// vv1 -> 内容：6 6 6       size=3, capacity=3; // vv2 -> 内容：1 2 3 4 5   size=5, capacity=5

emplace函数

声明
参数

pos

是vector的元素对应位置的迭代器
参数

args

是待插入的元素
在

pos

位置之前插入元素，类似于insert

template<class... Args>
iterator emplace(const_iterator pos, Args&&... args);

eg

vector<int> vvv1{1,2,3,4,5};
vvv1.emplace(vvv1.begin()+3,233);// 1 2 3 233 4 5
vvv1.emplace(vvv1.end(),1145);// 1 2 3 233 4 5 1145

非成员函数 - 关系运算符重载函数

==

声明
比较两个vector对象

v1, v2

的内容是否相同；
比较过程：先比较

v1和v2

的size是否相等，不相等直接不相等；相等就继续顺序比较二者的元素，如果存在一对不相等的元素就是不相等；元素都相等时才是相等；
不比较二者的cappacity；

template<classT>booloperator==(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 == v2;// true
v1.reserve(10);
v1 == v2;// true
v1.resize(3);
v1 == v2;// false

image.png

!=

声明

template<classT>booloperator!=(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 != v2;// false

<

声明

template<classT>booloperator<(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 < v2;// false

<=

声明

template<classT>booloperator<=(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 <= v2;// true

>

声明

template<classT>booloperator>(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 > v2;// false

>=

声明

template<classT>booloperator>=(const vector<T>& v1,const vector<T>& v2);

eg

vector<int> v1{1,2,3,4,5};
vector<int> v2{1,2,3,4,5};
v1 >= v2;// true

非成员函数 - 其他函数

swap函数

声明
与另一个vector对象进行内容的交换，也包括size和capacity；
与成员函数swap相比，第一个参数不再是隐式的this了；

template<classT>voidswap(vector<T>& x, vector<T>& y);

eg

vector<int> v1{6,6,6,6};// size=4, capacity=4
vector<int> v2{1,2,3,4,5}// size=5, capacity=5swap(v1, v2);// v1 -> 1,2,3,4,5  size=5, capacity=5// v2 -> 6,6,6,6    size=4, capacity=4

3. 揭开vector的真面目-模拟实现吧

底层成员变量

vector类模板的底层设计中包含三个

T

类型的指针：

_start

指向空间的起始地址，也是第一个元素的地址；

_finish

指向最后一个元素的下一个位置；

_end_of_storage

指向空间的结尾位置的下一个位置；

template<classT>classvector{public:private:
    T* _start;
    T* _finish;
    T* _end_of_storage;};

image.png

构造函数

默认无参构造

不传参数时把三个指针都初始化为

nullptr

；

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

使用n个val构造

new申请的空间大小是

n*sizeof(T)

，别忘记类型T的大小；

vector(size_t n,const T& val =T()){
    _start =new T[n *sizeof(T)];
    _end_of_storage = _finish = _start + n;for(int i =0; i < _finish - _start;++i){
        _start[i]= val;}}

与上面的函数都是使用n个val构造，只是上面函数

n

的类型是

size_t

，而本函数

n

的类型是

int

；
对于

vector<int> v(5, 1)

这句代码，编译器将会调用

vector(InputIterator first, InputIterator last)函数

，而不是

vector(size_t n, const T& val = T())

；
首先模板参数T实例化为

int

，而

5和1

默认作为int

类型

参数处理，两个参数类型一致，编译器会把

vector(InputIterator first, InputIterator last)的InputIterator模板参数

实例化为int，即

vector(int first,int last)

从而更符合参数

5和1

的类型，但是

5和1

不是迭代器范围，编译时报错；
所以需要额外实现函数

vector(int n, const T& val = T())

可以直接匹配

5和1

参数；
对于

vector<int> v(5, 'a')等

情况则仍将会正常调用

vector(size_t n, const T& val)

函数的；

vector(int n,const T& val =T()){
    _start =new T[n *sizeof(T)];
    _end_of_storage = _finish = _start + n;for(int i =0; i < _finish - _start;++i){
        _start[i]= val;}}

使用迭代器范围构造

template<classInputIterator>vector(InputIterator first, InputIterator last){
    size_t n = last - first;reserve(n);
    iterator it =begin();while(first != last){(*it)=(*first);
        it++;
        first++;}
    _finish = _start + n;}

拷贝构造函数

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());
    iterator it =begin();
    const_iterator cit = v.begin();while(cit != v.end()){*it =*cit;++it;++cit;}
    _finish = it;}

image.png

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){
    T* tmp =new T[v.capacity()];for(int i =0; i < v.size();++i){
        tmp[i]= v[i];}
    _start = tmp;
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();}

赋值运算符重载

现代写法，提高了代码书写效率
开空间交给了拷贝构造函数，而不是我们再次实现；

vector<T>&operator=(vector<T> v){swap(v);return*this;}

传统写法

vector<T>&operator=(const vector<T>& v){// 不能自己给自己赋值if(*this!= v){
        T* tmp =new T[v.capacity()];for(int i =0; i < v.size();++i){
            tmp[i]= v[i];}//delete[] _start;
        _start = tmp;
        _finish = _start + v.size();
        _end_of_storage = _start + v.capacity();}return*this;}

析构函数

~vector(){if(_start){delete[] _start;
        _start = _finish = _end_of_storage =nullptr;}}

迭代器相关

迭代器的实现 - 原生指针

typedef T* iterator;typedefconst T* const_iterator;

迭代器的返回类型，传值返回还是传引用返回？
对于非const版本，都可以，一般传值返回即可；
对于const版本，只能传值返回；因为引用返回会导致权限的放大，

this指针类型是vector<T>*const

，是指针常量，const修饰时变为

vector<T> const * const

，常量指针常量，函数返回类型

const_iterator&

即

const T* &

，返回指针变量

_start

是this指针指向的内容，故类型是

T* const

，所以由

T*const

到

const T *

将会出错；

正向迭代器

非const版本

begin返回指向开始元素的迭代器，即

_start

end返回指向最后一个元素的下一个位置的迭代器，即

_finish

image.png

iterator begin(){return _start;}
iterator end(){return _finish;}

const版本

const_iterator begin()const{return _start;}
const_iterator end()const{return _finish;}

元素访问

operator[]

访问pos位置的元素，注意需要对pos进行检查，防止越界访问；

非const版本

T&operator[](size_t pos){assert(pos <size());return _start[pos];}

const版本

const T&operator[](size_t pos)const{assert(pos <size());return _start[pos];}

容量相关

size函数

vector没有直接记录元素个数的变量，通过

_finish - _start

指针相减计算；

size_t size()const{return _finish - _start;}

capacity函数

vector没有直接记录空间容量的变量，通过

_finish - _start

指针相减计算；

size_t capacity()const{return _end_of_storage - _start;}

reserve函数

改变vector对象的容量capacity,
当

n

小于等于当前vector对象的容量capacity时，reserve函数什么也不做；
只有当

n

大于vector对象的容量时，reserve函数才会向系统申请开辟空间；即reserve函数一般只进行扩容处理，不缩容；

voidreserve(size_t n){if(n <=capacity())return;
    T* tmp =new T[n];for(int i =0; i <size();++i){
        tmp[i]= _start[i];}// 保存旧空间，防止_start更新后直接调用size()函数导致计算错误，// 此时_start是新的，而_finish还是旧的；int oldsize =size();delete[] _start;
    _start = tmp;
    _finish = _start + oldsize;
    _end_of_storage = _start + n;}

resize函数

如果

n

小于vector原有的

size

，相当于删除元素直到size为n，

_finish

更新为

_start + n

即可；
如果

n

等于vector原有

size

就什么也不做；
如果

n

大于vector原有size且小于等于vector的原有capacity，相当于尾插元素直到size为n，即每次把

val

拷贝给

_finish

指向位置的元素，再

++_finish

直到

_finish

等于

_start+n

；
如果

n

大于vector原有的capacity，相当于先扩容使容量增大，再尾插元素直到size为n；

voidresize(size_t n,const T& val =T()){// 小于 if(n <size()){
        _finish = _start + n;}elseif(n <capacity()){while(_finish < _start + n){*_finish = val;++_finish;}}else{reserve(n);while(_finish < _start + n){*_finish = val;++_finish;}}}

empty函数

boolempty()const{returnsize()==0;}

增删查改相关

push_back函数

dd

voidpush_back(const T& val){if(_finish == _end_of_storage){int newcapacity = _end_of_storage - _start ==0?4:2*(_end_of_storage - _start);reserve(newcapacity);}*_finish = val;
    _finish++;}

insert函数

再pos迭代器位置之前插入元素

插入一个元素

image.png

iterator insert(iterator pos,const T& val){assert(pos >= _start && pos < _finish);int len = pos - _start;if(_finish == _end_of_storage){int newcapacity =capacity()==0?4:2*capacity();reserve(newcapacity);}// update pos
    pos = _start + len;// move
    iterator end = _finish;while(end > pos){*end =*(end -1);
        end--;}*pos = val;++_finish;return pos;}
insert的迭代器失效问题

例子引入

vector<int>v(4,3);
vector<int>::iterator pos = v.begin()+1;
v.insert(pos,9);(*pos)++;// 野指针

vector<int>v(4,3);
vector<int>::iterator pos = v.begin()+1;
pos = v.insert(pos,9);(*pos)++;// 正确访问

传值传入插入位置的迭代器变量

pos

，在

insert

内部

vector

对象会先进行容量检查：

  • 如果容量满了就会进行扩容，这将会导致_start指向的空间变为扩容后新申请的空间，而pos还是指向旧空间的位置，此时pos是野指针，我们不能使用旧的pos了，需要pos指向新空间对应元素的位置后，再使用pos才能正确访问到元素；而外部调用insert函数后，作为参数的外部pos也失效了，其也指向了旧空间的位置，直接使用就是访问已经释放的空间，是非法访问内存，解决方法是外部pos接受insert的返回值新pos；
  • 如果容量没满就无需扩容，内部pos不会失效，外部pos也不会失效；

为什么

insert

函数的参数

iterator pos

不使用引用类型

iterator& pos

？

  • 诚然，使用引用后，外部的pos可以随着内部pos的更新而更新，不会失效了；但是此时形参pos只能是iterator的引用，遇到匿名对象等具有常性的迭代器时就会报错，导致权限放大问题即iterator 引用了 const_iterator对象，于是乎前人考虑的种种情况下，选择了insert更新后的pos作为返回值为外部提供，这样当外部想继续使用pos之前需要接收insert的参数即可。
插入多个元素
iterator insert(iterator pos, size_t n,const T& val){assert(pos >= _start && pos < _finish);int len = pos - _start;if(size()+ n >2*capacity()){// 2}elseif(size()+ n >capacity()){}
    pos = _start + len;// move
    iterator end = _finish;while(end > pos){*(end + n -1)=*(end -1);
        end--;}

    iterator begin = pos;while(begin < pos + n){*begin = val;++begin;}
    _finish += n;return pos;}

erase函数

删除pos位置的元素

iterator erase(iterator pos){assert(pos >= _start && pos < _finish);
    iterator begin = pos +1;while(begin < _finish){*(begin -1)=*begin;
        begin++;}
    _finish--;return pos;}
erase的迭代器失效问题

例子引入：

vector<int> v ={1,2,3,4};//
vector<int>::iterator pos1 = v.end()-1;
v.erase(pos1);(*pos1)++;// 

vector<int>::iterator pos2 = v.begin();
v.erase(pos2);(*pos2)++;//

这个例子的容器v分别执行了

erase

操作之后，迭代器

pos1

和

pos2

你是否认为失效了呢？
这在g++和vs2019编译器下有着不同的结果：

  • g++编译器认为没有失效，erase操作之后pos2仍然指向第二个位置，此时该位置的元素是3，g++版本的STL的vector底层实现上迭代器是一个原生的指针即typedef T* iterator，即使我们使用了失效的迭代器也无法检查出来；
  • vs编译器会对迭代器进行强制检查，认为pos2是失效的，程序会直接报错。这是因为vs下STL的实现方式更加复杂，对于vector容器的迭代器来说，不是一个原生的指针，而是被进一步封装为一个类，在使用迭代器时会先进行检查是否失效，如果失效了程序就会报错，反之就正常执行； 当前我们实现的版本更加接近g++的vector版本，是一个原生的指针，也就是说我们实现的版本在erase操作之后也无法对失效的迭代器进行有效检查；

那么到底该不该认为

erase

操作之后的迭代器失效呢？

  • 我的答案是不管编译器是否认为erase之后的迭代器是否失效，都认为迭代器是失效的，即每次erase之后及时更新迭代器，这样不管在g++编译器还是vs编译器下我们写的程序都是统一能跑的。

assign函数

为vector对象分配一个新值

一个迭代器范围[first, last)作为参数

template<classInputIterator>voidassign(InputIterator first, InputIterator last){assert(first);assert(last);assert(first < last);if(_start)delete[] _start;
    _start = _finish = _end_of_storage =nullptr;while(first != last){push_back(*first);
        first++;}}

n

个

val

作为参数；
有两个版本，功能完全相同，只有参数

n

的类型不同，目的是为了防止特殊情况下导致的问题：
如

传入(5, 1)

时期望是用5个

int

类型的1赋值给vector对象，但是在没有

assign(int,const T&)

函数时将会优先匹配

assign(InputIterator first, InputIterator last)

函数导致其内部解引用产生非法访问内存错误。

voidassign(size_t n,const T& val){
    vector<T>tmp(n, val);swap(tmp);}voidassign(int n,const T& val){
    vector<T>tmp(n, val);swap(tmp);}

非成员函数 - swap函数

交换两个vector对象的内容

template<classT>voidswap(vector<T>& x, vector<T>& y){
    x.swap(y);}

4. vector的一些深拷贝问题

reserve

函数是进行扩容的函数，其中涉及到开辟新空间，再把旧空间内容拷贝到新空间，最后释放旧空间的过程。
对于把内容从旧空间拷贝到新空间的方式，对于内置类型进行值拷贝就行；对于自定义类型特别是涉及资源管理的自定义类型来说，不能简单的进行值拷贝

如使用memcpy函数

，而是需要进行深拷贝，

调用赋值运算符重载函数

，前提是该自定义类型内部已经显式实现了深拷贝功能。
image.png
使用

memcpy

函数拷贝包含资源管理的自定义类型时发生的问题
以vector类为例，string类内部包含的指针指向了堆上的可变的字符数组，是需要管理的空间资源。其作为vector的元素在扩容时将会涉及到vector本身的深拷贝和string内部的深拷贝，也就是两层深拷贝。
image.png
image.png
image.png
image.png
解决方法：赋值操作，当是自定义类型时将会调用该自定义类型的赋值运算符重载函数完成深拷贝操作
image.png

结语

本节主要介绍了

STL

容器部分的

vector

，对于接口函数的学习先使我们整体了解

vector

如何使用。之后深入探究

vector

底层的实现方式，对比的是

SGI

版本，其中需要着重注意的是使用

insert

和

erase

导致的迭代器失效问题，实现

vector

的

resere

函数时考虑到涉及到资源管理的自定义类型需要深拷贝的情况。

      T 
     
    
      h 
     
    
      e 
     
    
   
     The 
    
   
 The 
  
   
    
    
      E 
     
    
      n 
     
    
      d 
     
    
   
     End 
    
   
 End
标签： c++ 开发语言
本文转载自: https://blog.csdn.net/weixin_64904163/article/details/134321855
版权归原作者 re怠惰的未禾 所有， 如有侵权，请联系我们删除。
登录后发布评论

“C++打怪升级（十）- STL之vector”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航