当前位置: 首页 > article >正文

STL——vector

目录

1 vector介绍

2 vector使用

2.1 vector的定义

2.1.1 无参构造

2.1.2 构造并初始化N个Val

2.1.3 拷贝构造

2.1.4 使用迭代器初始化构造

2.1.5 使用大括号初始化构造

2.2 vector的迭代器

2.2.1 const 迭代器

2.3 vector的空间增长

2.4 vector的增删改查

2.5 vector的迭代器失效(重点)

2.5.1 会引起其底层空间改变的操作,都有可能是迭代器失效

2.5.2 erase引起的迭代器失效 

3 vector访问

3.1 下标法

3.2 迭代器

3.3 范围for


1 vector介绍


vector是序列容器,表示大小可以变化的数组。vector可以有效地在末尾添加或删除元素 
  • STL库中的vector需要引入头文件:
#include <vector>
  • 类模板原型:
template < class T, class Alloc = allocator<T> > class vector; // generic template

模板参数

  • T:元素的类型
  • Alloc:vector底层存储数据的内存是从空间配置器申请的,如果需要可以⾃⼰实现内存池,传给第二个参数

2 vector使用


2.1 vector的定义

2.1.1 无参构造

vector();

vector<int> v; //定义了一个名为a的一维数组,数组存储int类型数据

2.1.2 构造并初始化N个Val

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

vector<int> v(n); //定义一个长度为n的数组,初始值默认为0,下标范围[0, n - 1] 
vector<int> v(n, 10); //v[0] 到 v[n - 1]所有的元素初始值均为10 
vector<Test> v(n); //定义一个长度为n的数组,将调用Test的构造函数初始化,下标范围[0, n - 1]

模板参数:

  • n:初始容器大小
  • val:对于内置类型,会进行默认初始化,对于自定义类型,会调用相对应的构造函数进行初始化

2.1.3 拷贝构造

vector (const vector& x);

vector<int> v1(10); 
vector<int> v2(v1); //两个数组中的类型必须相同,v1和v2都是长度为10,初始值都为0的数组

2.1.4 使用迭代器初始化构造

类模板的成员函数,也可以是一个函数模板。这样设计的好处在于不限于只使用vector的容量进行初始化,还可以使用其他容器进行初始化。比如:list、string、deque等

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

vector<int> v1; 
list<int> l1; 
deque<int> d1; 

vector<int> v2(v1.begin(),v1.end()); 
vector<int> v3(l1.begin(),l1.end()); 
vector<int> v4(d1.begin(),d1.end());

2.1.5 使用大括号初始化构造

vector (initializer_list<T> il);

首先要明确,这种初始化方式只支持C++11以后的标准

initializer_list是C++11新加入的一种容量,这个容器支持迭代器访问。它的原理与使用大括号创建数组很相似cplusplus.com/reference/initializer_list/initializer_list/

auto il = {1,2,3,4,5}; 
int arr[] = {1,2,3,4,5};

//vector使用大括号初始化的原理就是,先将其转化为initializer_list容器,然后调用相应的构造函数进行初始化
vector<int> v{1, 2, 3, 4, 5}; //数组v中有五个元素,数组长度就为5

2.2 vector的迭代器

迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装

接口

时间复杂度

接口说明

begin()

O(1)

获取第一个数据位置的iterator/const_iterator

end()

O(1)

获取最后一个数据的下一个位置的iterator/const_iterator

rbegin()

O(1)

获取最后一个数据位置的reverse_iterator

rend()

O(1)

获取第一个数据前一个位置的reverse_iterator

注意:

  • end() 返回的是最后一个元素的后一个位置的地址,不是最后一个元素的地址,所有STL容器均是如此

vector<int> v{1,2,3,4,5,6,7,8,9}; 
for(auto it = v.begin(); it != v.end(); it++) 
{ 
    cout << *it << endl; 
} 

for(auto it = v.rbegin(); it != v.rend(); it++) 
{ 
    cout << *it << endl; 
}

2.2.1 const 迭代器

当我们想创建被const修饰的vector容器迭代器时,不可以直接在迭代器前加const

vector<int> v; 
const vector<int>::iterator it = v.begin();

以上的写法是不可以的,他不能达到it所指向的内容不能被修改,实际是it它本身不可以被修改

它会转换为:

int* const it = v.begin();

示例:

int main()
{
    vector<int> v;
    v.push_back(1);
    cout << *v.begin() << endl;
    const vector<int>::iterator it = v.begin();
    *it = 2;
    cout << *v.begin() << endl;
    return 0;
}

因此这里需要使用 const_iterator,const_iterator 就是 const T* 的重定义

typedef const T* const_iterator;

vector<int> ::const_iterator it2 = v.begin(); 
*it2 = 2;

此时的迭代器就是指向的内容不可以被改变

2.3 vector的空间增长

接口

时间复杂度

接口说明

size()

O(1)

获取数据个数

capacity()

O(1)

获取容量大小

empty()

O(1)

判断是否为空

resize()

O(N)

改变容量的数据个数

reserve()

O(N)

改变容量的容量大小

resize的增长逻辑:

  1. 小于当前容器元素个数:删除至n个元素
  2. 大于当前容器元素个数,小于当前容器容量:填充指定元素
  3. 大于当前容器容量:扩容至n个元素,并且填充指定元素

reserver的增长逻辑(不同平台会有差异):

  1. 大于当前容量就扩容
  2. 小于当前容量默认不改变容量

2.4 vector的增删改查

接口

时间复杂度

接口说明

push_back()

O(1)

尾插

pop_back()

O(1)

尾删

insert()

O(N)

指定位置前插入

erase()

O(N)

指定位置删除

swap()

O(1)

交换两个容器的数据空间

operator[]

O(1)

像数组一样访问

2.5 vector的迭代器失效(重点)

迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)

2.5.1 会引起其底层空间改变的操作,都有可能是迭代器失效

比如:resize、reserve、insert、assign、push_back

int main()
{
    vector<int> v1(10, 1);
    //迭代器
    auto it = v1.begin();
    //将有效元素个数增加到1000个,多出的位置使用1填充,操作期间底层会扩容
    v1.resize(1000, 1);
    //此处导致非法访问
    cout << *it << endl;
    return 0;
}

出错原因:

以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的空间,而引起代码运行时崩溃

解决方式:

在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新赋值即可

2.5.2 erase引起的迭代器失效 

int main()
{
    vector<int> v1(10, 1);
    //迭代器
    auto it = v1.begin();
    //删除指定位置的元素
    v1.erase(it);
    //此处导致非法访问
    cout << *it << endl;
    return 0;
}

出错原因:

erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效

但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了

我们不能依赖于某种特定的结果,因此删除vector中任意位置上元素时,默认认为该位置迭代器失效了

解决方式:

erase设有返回值,返回的是删除元素的下一个元素位置,再次给it重新赋值即可

3 vector访问


3.1 下标法

vector容器对 [] 运算符进行了函数重载,因此可以使得vector的访问可以于普通数组一样访问

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

3.2 迭代器

与类似指针,迭代器就是充当指针的作用

int main()
{
    vector<int> v{1,2,3,4,5};
    //获取迭代器
    auto it=v.begin();
    while(it!=v.end())
    {
        cout<<*it<<" ";   
        it++;    
    }
    return 0;
}

3.3 范围for

这是C++的一个语法糖,其用法的本质就是将其替换为迭代器的形式进行访问

int main()
{
    vector<int> v{1,2,3,4,5};
    for(auto e:v)
    {
        cout<<e<<" ";          
    }
    return 0;
}


http://www.kler.cn/a/589753.html

相关文章:

  • openai 标准化协议 Structured Outputs 具体示例教程
  • [蓝桥杯 2024 国 A] 最长子段
  • 虚幻基础:GAS
  • 2.4 python网络编程
  • Matlab 单球机器人动力学与LQR控制研究
  • 2025年03月11日Github流行趋势
  • 深入理解C++编程:从内存管理到多态与算法实现
  • 国密系列加密技术及其在爬虫逆向中的应用研究
  • JDK15开始偏向锁不再默认开启
  • 求职招聘网站源码,找工作招工系统,支持H5和各种小程序
  • 13个问题
  • Java概述
  • Ubuntu22.04虚拟机里安装Yolov8流程
  • Oracle GoldenGate (OGG) 安装、使用及常见故障处理
  • SpringBoot集成ElasticSearch实现支持错别字检索和关键字高亮的模糊查询
  • 分治(2)——快速搜索算法
  • 51单片机学习记录
  • 时间序列分析的军火库:AutoTS、Darts、Kats、PaddleTS、tfts 和 FancyTS解析
  • 【小项目】四连杆机构的Python运动学求解和MATLAB图形仿真
  • 机器学习--卷积神经网络原理及MATLAB回归实现