-
2020-05-07 10:21:50
摘自胡凡的《算法笔记》,仅作记录用!
前言:
如果要使用vector,则需要添加vector头文件,即#include<vector>
,除此之外,还需要添加using namespace std;
一、vector的定义
- 单独定义一个vector,可以使用
vector<typename> name;
其实相当于一个一维数组,只不过长度可变,能够节省空间。如果使用vector<typename> v(n)
方法,则定义的是一个长度为n的数组,相当于固定了数组的长度。
- 和一维数组一样,这里的typename可以是任何基本类型,如int,double,char,结构体等,也可以是STL标准容器,如vector,set,queue等
- 值得注意的是,如果typename也是一个STL容器,定义的时候要记得在>>符号之间加上空格,因为一些使用C++11之前标准的编译器会把它视为移位操作,导致编译错误。
- 定义vector数组
vector<vector<int> > name;
,两个维都可变长的二维数组。vector<typename> Arrayname[arraySize];
,这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是一个vector容器
二、vector容器内元素的访问
- 通过下标访问
- 和访问普通的数组是一样的,对一个定义为
vector<typename> v
的vector容器,直接使用v[index]
访问即可,其中 i n d e x ∈ [ 0 , v . s i z e ( ) − 1 ] index\in[0,v.size()-1] index∈[0,v.size()−1]
- 通过迭代器访问
- 迭代器可以理解为一种类似指针的东西
vector<typename>::iterator it;
定义迭代器,得到了迭代器it之后,可以通过*it
来访问vector中的元素
v[i]
和*(v.begin()+i)
是等价的。- 迭代器来实现了两种自加操作和自减操作。
- begin()函数的作为是为取v的首元素地址,end()函数并不是为了取v的尾元素地址,而是取尾元素地址的下一个地址。它作为迭代器末尾标志,不储存任何元素。
- 在常用STL容器中,只有在vector和string中,才允许使用
v.begin()+3
这种迭代器加上整数的写法。
三、vector常用函数
- push_back(),时间复杂度为 O ( 1 ) O\left(1\right) O(1)
push_back(x)
就是在vector后面添加一个元素x
- pop_back(),时间复杂度为 O ( 1 ) O\left(1\right) O(1)
pop_back()
用于删除vector的尾元素
- size(),时间复杂度为 O ( 1 ) O\left(1\right) O(1)
- size()用来获得vector中元素的个数,返回的是unsigned类型,不过一般来说用%d不会出很大问题。这一点对所有STL容器都是一样的。
- clear(),时间复杂度为 O ( N ) O\left(N\right) O(N)
- 用来清空vector中的所有元素
- insert(),时间复杂度为 O ( N ) O\left(N\right) O(N)
insert(it,x)
用来向vector的任意迭代器it处插入一个元素x
- erase(),时间复杂度为 O ( N ) O\left(N\right) O(N)
- 删除单个元素,
erase(it)
即删除迭代器为it处的元素。 - 删除一个区间内的所有元素,
erase(first,last)
即删除[first,last)
内的所有元素 - 清空vector也可以使用
v.erase(v.begin(),v.end())
;
四、vector的常见用途
- 存储数据
- 用邻接表存储图
更多相关内容 - 单独定义一个vector,可以使用
-
stl之vector带注释
2017-07-17 20:03:08SGI STL之vector源码,带注释 -
cpp代码-C++ STL之vector动态数组
2021-07-16 16:08:32cpp代码-C++ STL之vector动态数组 -
C++ STL之vector详解
2022-01-04 15:08:56本文介绍了STL的vector的常用操作以及相关的注意事项返回主目录
⭐️vector(动态数组)⭐️
1️⃣介绍1️⃣
vector为可变长数组(动态数组),定义的vector数组可以随时添加数值和删除元素.
在局部函数中开vector数组,是在堆空间里面开的,与开全局变量比较类似,所以经常见到在局部函数中开大容量数组
- 头文件
#include < vector >
-
初始化
-
一维初始化
vector<int>num; //定义了一个名为num的存int数据的一维数组 vector<double>num;//定义了一个名为num的存double数据的一维数组 vector<node>num;//node是结构体类型
指定长度和初始值的初始化
vector<int> v(n);//定义一个长度为n的数组,动态定义 vector<int> v(n,0);//所有的元素均为0 //注意:指定数组长度之后(指定长度后的数组就相当于正常的数组了) //就不能使用push_back()操作了(此操作见下文)
初始化中有多个元素
vector<int> a{1, 2, 3, 4, 5};// 数组a中有五个元素
拷贝初始化
vector<int> a(n + 1, 0); vector<int> b(a);//两个数组中的类型必须相同,a和b都是长度为n+1,所有值都为0的数组
-
二维初始化
定义第一维固定长度为5
,第二维可变化的二维数组vector<int>num[5];//定义可变长二维数组 //注意:行是不可变的(只有5行),而列可变可以在指定行添加元素 //第一维固定长度为5,第二维长度可以改变
行列均可变
//初始化二维均可变长数组 vector<vectot<int> >num;//定义一个行和列均可变的二维数组
行列长度均固定
n + 1
行m + 1
列初始值为0vector<vector<int> > a(n + 1, vector<int>(m + 1, 0));
c++17或者c++20支持的形式(我也不太清楚😭)
vector a(n + 1, vector(m + 1, 0));
-
⭐️初始化技巧⭐️
⭐️简单访问⭐️
//方式一:单个访问,假设num数组中已经有了5个元素 cout << num[4] << "\n"; //输出第五个数据 //一二维可变数组和普通数组的访问方法一样 //方式二:遍历 for(int i = 0; i < num.size(); i++) cout << num[i] << " ";//下标范围在[0,num.size()),前开后闭 //方式三:智能指针 for(auto i : num) cout << i << " ";
2️⃣ 方法函数2️⃣
知道了如何定义初始化可变数组,下面就需要知道如何添加,删除,修改数据。
相关方法函数如下:
c指定为数组名称
代码 含义 c.front() 返回第一个数据 c.pop_back() 删除最后一个数据 O(1) c.push_back(element) 在尾部加一个数据 O(1) c.size() 返回实际数据个数(unsigned类型) O(1) c.clear() 清除元素个数 O(N),N为元素个数 c.resize(n,v) 改变数组大小为n,n个空间数值赋为v,如果没有默认赋值为0 c.insert(it,x) 向任意迭代器it插入一个元素x O(N) 例:c.insert(c.begin()+2,-1) 将-1插入c[2]的位置 c.erase(first,last) 删除[first,last)的所有元素 c.begin() 返回首元素的迭代器(通俗来说就是地址) c.end() 返回最后一个元素后一个位置的迭代器(地址) c.empty() 判断是否为空,为空返回真,反之返回假 注意: end()返回的是最后一个元素的后一个位置的地址,不是最后一个元素的地址,所有容器均是如此
以上 O(n),O(1)说的是时间复杂度
3️⃣注意点3️⃣
1. 排序
使用sort排序要:
sort(c.begin(),c.end());
对所有元素进行排序,如果要对指定区间进行排序,可以对sort()里面的参数进行加减改动。
2. 访问
数组访问:
上面有简单的访问演示,下面进行扩充并复习
下标法: 和普通数组一样
注意:一维数组的下标是从 0 0 0到 v . s i z e ( ) − 1 v.size()-1 v.size()−1,访问之外的数可能会出错
迭代器法: 类似指针一样的访问 ,首先需要声明迭代器变量,和声明指针变量一样,可以根据代码进行理解(附有注释)。
代码如下:
vector<int> vi; //定义一个vi数组 vector<int>::iterator it = vi.begin();//声明一个迭代器指向vi的初始位置
vector数组访问相关代码:
2.1.下标访问:
//添加元素 for(int i = 0; i < 5; i++) vi.push_back(i); //下标访问 for(int i = 0; i < 5; i++) cout << vi[i] << " "; cout << "\n";
2.2.迭代器访问:
//迭代器访问 vector<int>::iterator it; //相当于声明了一个迭代器类型的变量it //通俗来说就是声明了一个指针变量 //方式一: vector<int>::iterator it = vi.begin(); for(int i = 0; i < 5; i++) cout << *(it + i) << " "; cout << "\n"; //方式二: vector<int>::iterator it; for(it = vi.begin(); it != vi.end();it ++) cout << *it << " "; //vi.end()指向尾元素地址的下一个地址
2.3.智能指针:
只能遍历完数组,如果要指定的内容进行遍历,需要另选方法。
auto 能够自动识别类型。vector<int> v; v.push_back(12); v.push_back(241); for( auto i : v) cout << i << " "; // 12 241
综上:
- vi[i] 和 *(vi.begin() + i) 等价
- 说明:只有
vector
和string
的stl容器支持*(it+i)的元素访问
string的讲解在后续章节会有讲述
-
C++STL之vector详解
2020-04-14 15:55:19一、STL简介 STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。STL 是 C++ 标准库的一部分,不用单独安装。...例如,vector 的底层为顺序表(数组),list 的底层为双向...一、STL简介
STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。STL 是 C++ 标准库的一部分,不用单独安装。
C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环队列,set 的底层为红黑树,hash_set 的底层为哈希表。STL 从根本上讲是“容器”的集合,也是组件的集合。容器包括 list、vector、set、map 等;组件包括迭代器等。STL 的目的是标准化组件。
STL 是 C++ 的一部分,不用额外安装,被内建在支持 C++ 的编译器中。
STL 的算法是标准算法,其实现了将已经定义好的算法应用在容器的对象上。更多STL介绍请看STL是什么
二、C++ vector简介
vector<T> 容器是包含 T 类型元素的序列容器,和 array<T,N> 容器相似,不同的是 vector<T> 容器的大小可以自动增长,从而可以包含任意数量的元素;因此类型参数 T 不再需要模板参数 N。只要元素个数超出 vector 当前容量,就会自动分配更多的空间。只能在容器尾部高效地删除或添加元素。
vector<T> 容器可以方便、灵活地代替数组。在大多数时候,都可以用 vector<T> 代替数组存放元素。只要能够意识到,vector<T> 在扩展容量,以 及在序列内部删除或添加元素时会产生一些开销;但大多数情况下,代码不会明显变慢。 为了使用 vector<T> 容器模板,需要在代码中包含头文件 #include<vector>。时间复杂度:该容器随机存取任何元素都能在常数时间O(1)完成,在尾端增删元素具有最佳的性能(大部分时间是常数时间,即在不需要重新分配存储空间的情况下。在一些特殊的情况下需要的时间是O(n),比如当所需要的存储空间超过了之前动态分配的空间,这时候就需要重新分配存储空间,需要进行一个数组的拷贝工作)当在vector<T>中间或者头部插入或者删除元素所需要的时间复杂度为O(n)因为我们需要将后面的元素一次向后移动一个位置。
三、C++ vector的常用方法
#include<iostream> #include<vector> using namespace std; //定义一个输出vector模板 /*为了方便打印不同类型的vector,如果vector的类型比较少 可以使用for循环打印,例如定义一个 vector<int> num; 输出可以用: //输出num中的内容 size():返回Vector元素数量的大小 for(int i=0;i<num.size();i++){ cout<<num[i]<<" "; //可以使用[]访问,也可以使用at()方法访问 cout<<num.at(i)<<" "; //at():返回指定位置的元素 } cout<<endl; */ template<class T> void printVector(T s,T e){ for(;s != e;++s){ cout<<*s<<" "; } cout<<endl; } int main(){ vector<int> num; //生成存放 int 型元素的 vector<T> 容器 cout<<"赋值之前num的容量:"<<num.capacity()<<endl; //capacity()返回vector所能容纳的元素数量(在不重新分配内存的情况下) 此时没有初始化,所以size() 和 capacity() 都是0;size() 返回容器目前存在的元素个数。 //以初始化列表中的値作为元素初始值,生成有 6个浮点数的vector容器。 double a[6] = {1.1,2.6,3.8,4.9,5.6,6.6}; vector<double> number(a,a+6); printVector(number.begin(),number.end()); //string A[4] = {"str1","str2","str3","str4"}; //vector<string> str(A,A+4); //str有4个元素,全部初始化为 "abc" vector<string> str(4,"abc"); printVector(str.begin(),str.end()); //向容器中添加元素 for(int i=0;i<10;i++){ num.push_back(i); //push_back():在Vector最后添加一个元素 } cout<<"赋值之后num的容量:"<<num.capacity()<<endl; //输出num中的内容 size():返回Vector元素数量的大小 for(int i=0;i<num.size();i++){ cout<<num[i]<<" "; //可以使用[]访问,也可以使用at()方法访问 cout<<num.at(i)<<" "; //at():返回指定位置的元素 } cout<<endl; //insert():插入元素到Vector中 num.insert(num.begin()+3,10); //将 10 插入到下标为3的位置 //begin():返回第一个元素的迭代器 //end():返回最末元素的迭代器(译注:实指向最末元素的下一个位置) printVector(num.begin(),num.end()); //将num的一段0,1,2,3,4从下标为 3 的位置插入 num.insert(num.begin()+3,num.begin(),num.begin()+5); printVector(num.begin(),num.end()); num.erase(num.begin()+3); //删除下标为 3 位置上的元素 printVector(num.begin(),num.end()); //删除一段元素 num.erase(num.begin(),num.end()-2); printVector(num.begin(),num.end()); cout<<"删除前str内容为:"; printVector(str.begin(),str.end()); //删除所有的元素 str.clear(); cout<<"删除后str内容为:"; printVector(str.begin(),str.end()); return 0; }
运行结果:
四、C++ vector的所有方法(更加详细的内容请参考C++的API:https://en.cppreference.com/w/cpp/container/vector)
-
STL之vector扩容机制
2022-03-25 15:18:45STL容器之vector扩容,翻翻源码,到底咋回事的一、背景介绍
vector作为STL的常用容器之一,其特性和数组类似,拥有一段连续的内存空间。vector申请的是一段连续的内存,当插入新的元素内存不够时,通常会再重新申请更大的一块内存,将原来的元素拷贝过去,释放旧空间。因为内存空间是连续的,所以在进行插入和删除操作时,会造成内存块的拷贝,时间复杂度为O(n)。
二、相关函数介绍
2.1 resize()
resize,即重置容器空间。当设置值小于当前容器空间时,会将目前容器中超出设置值的空间释放掉;当设置值大于当前容器空间时,会在当前空间的基础上增加容量。
举个例子,vector当前容量为10,若使用resize(20)设置容量为20,则需要再扩容增加10个;若使用resize(5)设置容量为5,则将6-10的空间进行释放。
空口无凭,咱直接上g++5.2源码:void resize(size_type __new_size) { if (__new_size > size()) _M_default_append(__new_size - size()); else if (__new_size < size()) _M_erase_at_end(this->_M_impl._M_start + __new_size); }
2.2 reserve()
reserve,即预留容器空间。当设置值大于当前容器空间时,会增加当前容器空间的大小,源码如下:
void reserve(size_type __n) { if (__n > max_size()) __throw_length_error(__N("vector::reserve")); if (capacity() < __n) _M_reallocate(__n); }
三、扩容机制(1.5倍还是2.0倍?)
下面将在msvc编译器和gcc编译器上分别测试,直接上代码:
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> dp; int n = 100; while (n--) { dp.push_back(n); cout << "size " << dp.size() << ", capacity " << dp.capacity() << endl; } }
3.1 MSVC执行结果
3.2 GCC执行结果
3.3 总结
显然,不同编译器在vector的扩容策略上显然不太一致,在vector的size()(当前容器所用空间)等于capacity()(当前容器总空间)时会发生扩容,msvc编译器每次是以1.5倍且向下取整的策略进行扩容,gcc编译器则是每次以2.0倍的策略进行扩容。
无论如何,在vector的日常使用中,如果只是简单的push_back插入数据,显然会带来频繁的数据拷贝,这对程序执行效率来说影响很大,因此,在能提前考虑容量的情况下,提前使用**reserve()或resize()**调整容器空间对程序性能提升很有意义。
-
STL之Vector实现原理
2017-08-01 23:24:31Vector的基本知识 在C++中,我们使用信息隐藏技术和封装技术把数据隐藏在类内部不许外部直接操作,同时提供访问器(如get_xxx成员函数)和修改器(如set_xxx成员函数)。STL容器的设计原理如出一辙,只是它们在... -
STL 之vector学习 (最详细的整理)
2018-08-11 16:42:52vector是一种可以存储任意类型的动态数组,属于序列式容器,可以用sort对其进行排序,底层数据结构是数组,可以随机访问元素。 #include<iostream> #include<vector> #include&... -
STL之vector常用方法 二维vector 取vector数组指针
2016-08-16 18:16:58使用包含#include <vector> using namespace std;二.声明1、一维数组: vector a; 2、动态创建m*n的二维vector:方法一: vector<vector<int> > arr; (注意后有空格或者使用typedef定义) arr.resize(m); ... -
STL之vector容器元素删除
2018-01-30 10:06:23删除vector容器的对象元素有三种方法:pop_back,erase,remove算法。 向量容器的成员函数pop_back()可以删除最后一个元素; 函数erase()可以删除由一个iterator指出的元素,也可以删除一个指定范围内的元素; ... -
STL之vector的push_back过程详解
2018-10-12 01:13:27最近,被面试官的一道题问倒,很失落,明明看过《STL源码分析》,为啥这种问题还没答好,只能说自己看的时候没有仔细去思考。这道题就是标题的问题,面试完我重新看了一遍《STL源码分析》中关于这块的内容,这里记录... -
C++STL之vector的拷贝构造
2019-10-25 09:36:28腾讯面试题:请问vector的拷贝构造干了些什么? 拿到这道题可能很多人都已经暗自里庆幸,对于学习过过数据结构的人,对于vector这个结构体一定不会陌生,但是如果在面试的过程中面试官考到了这道题我们要该如何来... -
C++ --STL之vector容器
2022-03-27 18:38:23STL之vector容器初始 -
STL之vector中push_back的时间复杂度分析
2019-04-18 14:41:55vector是STL中的一种序列式容器,采用的数据结构为线性连续空间,它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端,结构... -
STL 之 vector 查找性能优化
2018-08-08 10:54:23如果一个数组元素不多,就没必要做优化了。这里要说的是一个大的数组,在进行遍历查找元素的时候,优化和没有优化的效果还是可以用肉眼看得出来的,下面是一个简单的例子: ...vector> #includ... -
关于STL中vector容器的一些总结
2021-01-01 06:12:59实际上更专业的描述为:vector是一个多功能的,能够操作多种数据结构和算法的模板类和函数库,vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的... -
C++ STL之vector容器遍历与元素修改
2021-03-06 14:48:55vector void fun(int& p) { p = 8; } int main() { vector<int> list; list.push_back(0); list.push_back(1); //向量元素值被修改 for (int i=0;i<list.size();i++) { fun(list[i]); } //... -
【C++】 STL之 vector的capacity和size属性区别
2018-11-16 09:09:36vector的capacity和size属性区别 vector中这两个属性很容易弄混淆。 size是当前vector容器真实占用的大小,也就是容器当前拥有多少个容器。 capacity是指在发生realloc前能允许的最大元素数,即预分配的内存空间... -
C++ STL之vector的简单使用
2018-02-02 11:45:36Vector是c++提供的容器之一,可以很好的扩展。除此之外,提供了一些函数。 本篇文章将常用的函数进行了使用,利用switch组成了一个菜单,具有尾部扩张 、插入、删除、排序、显示 、修改等功能。 适合初学者。 ... -
STL之vector
2016-05-24 14:14:01STL之vector -
c++ STL 之 vector 学习笔记
2020-06-28 22:37:16vector 可以看作是一个封装好的动态数组 定义一个 int 类型 vector vector<int>a; //不止 int、string、char 类型,还可以自己定义结构体类型 结构体相关例题见 vector PTA 7-10 宿舍谁最高? vector PTA 7-7...