算法学习之路|用C++刷算法会用到的STL(一)——vector

简介: 用C++刷算法会用到的STL(一)——vector

STL是Standard Template Library的简称,中文名标准模板库。

从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。STL现在是C++的一部分,因此不用安装额外的库文件。

在C++标准中,STL被组织为下面的17个头文件:

<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。

一、vector

1. vector的自我介绍

  • vector是向量的意思,可以理解为“可变长度的数组”。
  • 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  • 相当于一个动态数组,在你不知道需要的数组有多大时可以使用它来节省很多空间。在ACM中常常会出现内存溢出(out of memory)的问题导致WA(wrong answer),而使用vector就能节省很多内存。
  • 使用vector要在程序开头加上#include<vector>来包含需要的头文件,还有加上“using namespace std;”,这样就可以在代码中使用vector了。

2.vector的定义

  • 定义一个vector:
vector<typename> vectorname;
  • 这个定义相当于定义了一个一维的数组vectorname[SIZE],只不过这个SIZE的长度是可以改变的,随着你“加入”进去数的个数而改变。所谓“可变长度的数组”。
  • 和一维的数组一样,这里的typename可以是任何的类型,如int,double,char,string,long long ,也可以是结构体,甚至是STL的容器如vector,set,queue,stack等。注意!如果typename也是一个容器的话,比如vector<vector<int> > vectorname,要在两个'<'符号之间加上一个空格,否则编译时会误以为是位移操作。

3.vector的创建

vector<double> vec1; // 创建一个空的double向量
vector<int> vec(66); // 创建一个初始大小为66的int向量
vector<double> vec2(vec1); // 创建一个double型的vec2,并用vec1去初始化vec2
vector<char> vec(10,'k'); // 创建一个含有10个char型数据的vector,并全部初始化为'k'
vector<int> vec(10,1);//创建一个初始大小为10的并且值都是1的vector
vector<int> vec2(vec1.begin(),vec1.begin()+3);//用向量vec1的第0个到第2个值初始化vec2
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量,末尾指针指向结束元素
//的下一个
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值,不包含arr[4],
//原因如上

4.特别的,元素为vector的vector数组

  • (其实就是vector的二维数组)和vector数组! 如果typename是vector,那么就这么定义vector<vector<int> > vectorname; 注意在相邻的'>'之间要加空格。 这个就像二维数组的定义,其中一维是一个元素是vector的vector数组。可以把vector数组 当作两个维长度都可变的二维数组理解。vector数组的定义vector<typename> Arrayname[arraySize]; 比如,vector<int> vec[66]; 这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是vector容器。 而vector<vector<int> > vectorname不同的地方时,前者的第一维长度已经固定为arraySize了, 后者却是两个维度都可变长的数组。哈哈哈,用你的大脑,发挥空间想象能力,出现了什么图形? 很神奇是不是!

5.vector容器内元素的访问形式

  • vector一般有两种访问形式:通过下标访问或者是通过迭代器访问。

(1)通过下标访问

和访问普通数组是一样的,一个已经定义的vector<typename> vec的vector容器,直接访问vec[index]就可以了(比如 vec[0],vec[1])。需要注意的一点是,首先这个vec得有size!!!桥黑板!什么意思呢?就是如果一开始你定义了 比如vector<int> vec1;直接使用vec[0]是不对的!因为里面还没有长度啊!开始用的时候我就经常犯这个错误(尴尬) 。所以可以通过下标访问的范围是从0~vec.size()-1.

(2)通过迭代器访问

  • 啥叫迭代器啊?好可怕~就理解为指针吧,不去考虑细节,两者是一样的(包括在java中最近遇见的引用,这简直是三胞胎!)。 定义如下: vector<typename>::iterator it;(it就是变量名,一般默认都写成it) 这样it就是一个vector<typename>::iterator 型的变量了(hhh,这个名字好长啊),其中,typename就是定义vector时 写的类型。比如: vector<double>::iterator it; vector<int> vec; vector<int>::iterator it2; it2=vec.begin();(或者合成一条:vector<int>::iterator it2=vec.begin(); ) 这样就得到了迭代器it(or it2),并且可以通过*it来访问vector里的元素。
vector<int> vec;
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)//vector的迭代器不支持it<vec.end()写法,因此循环中只能用it!=end()
cout << *it << endl;
//或者
vector<int>::iterator it=vec.begin();
for(int i=0;i<vec.size();i++){
printf("%d ",*(it+i));//桥黑板!!在STL容器中,只有vector和string这两个好基友,才允许使用vev.begin()+3这种迭代器加上整
//数的写法,只有这俩。
//从这里可以看出,vec[i]和*(vec.begin()+i)是等价的
}
//或者
for (size_t i = 0; i < vec.size(); i++) {
cout << vec.at(i) << endl;//见下文分解
}

好了,终于说完访问形式了,可以介绍基本操作啦!

6.vector的基本操作

(1)对容量的操作

  • 得到向量的大小: vec.size();
  • 得到向量最大可以是多大: vec.max_size();
  • 重新设置容器size的大小: vec.resize(num);
  • 重新设置容器capacity的大小: vec.reserve(num);
  • 向量真实大小: vec.capacity();
  • 判断向量是否为空: vec.empty();

注:关于resize()和reverse(),我觉得记住一点就行了,容器调用resize()函数后, 所有的空间都已经初始化了,所以可以直接访问。比如: vector<int> vet; vec.resize(100); vec[0]=1;//合法语句! 而reserve()函数预分配出的空间没有被初始化,所以不可访问。 推荐一个关于resize()和reserve()写的不错的博客vector中resize()和reserve()区别

(2)修改元素

  • 多个元素赋值: vec.assign(); //类似于初始化时用数组进行赋值
  • 末尾添加元素: vec.push_back(i)//在末尾添加元素i
  • 末尾删除元素: vec.pop_back();
  • 任意位置插入元素: vec.insert(it,x);
  1. 用来向vector的任意迭代器(见上文)it处插入一个元素x,时间复杂度O(N);
  • 任意位置删除元素: vec.erase();
  1. erease(it)即删除迭代器为it处的元素;
  2. erase(first,last)即删除[first,last)内的所有元素;(老美的左闭右开,你懂的)
  • 交换两个向量的元素: vec.swap();//不多讲,用的真的很少。同样,推荐博客vector利用swap()函数进行内存的释放

(3)惊现迭代器

开始指针:vec.begin();
末尾指针:vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针: vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容,但还是可以通过其他方式修改的,而且指针也是可以移动的。(用的很少,不妨先忽略吧)
指向常量的末尾指针: vec.cend();(同上,不多说)

(4)元素的访问

下标访问: vec[1]; //桥黑板!!并不会检查是否越界
at方法访问: vec.at(1); //以上两者的区别就是at会检查是否越界,是则抛出out of range异常
访问第一个元素: vec.front();
访问最后一个元素: vec.back();
返回一个指针: int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组,所以可以返回一个指针指向这个数组。这是是C++11的特性。(可忽略)

(5)一些算法

  • 遍历元素
Cvector<int>::iterator it; 
for (it = vec.begin();it != vec.end(); it++)
    cout << *it << endl;
//或者
for (size_t i = 0; i < vec.size(); i++) {
     cout << vec.at(i) << endl; 
}
  • 元素翻转
C#include <algorithm>
reverse(vec.begin(), vec.end());
  • 元素排序
C#include <algorithm> 
sort(vec.begin(), vec.end()); //采用的是从小到大的排序 
//如果想从大到小排序,可以采用上面反转函数,也可以采用下面方法: 
bool Comp(const int& a, const int& b) {//固定套路,要加上const,意思是不能修改引用 
return a > b; 
} 
sort(vec.begin(), vec.end(), Comp);

7.vector的用武之地

(1)储存数据

  • vector本身可以作为数组使用,而且在一些元素个数不确定的场合可以很好的节省空间。
  • 有些场合需要根据一些条件把部分数据输出在同一行,数据中间用空格隔开。由于输出的数据个数是不确定的,为了跟方便的处理最后一个满足条件的数据后面不输出额外的空格,可以先用vector记录所有需要输出的数据,然后一次性输出。
  • 有强大的方法可以调用(妈呀,java学多了,请不要喷我,暂且就叫方法吧,介绍如上vector的基本操作(1)~(4))

( 2 )用邻接表存储图

  • 使用vector实现邻接表可以有效避免指针,而且更容易把握。

哈哈哈,终于结束啦(喝口水)。
好了,说了这么多,当然废话也不少~~
来几道题目吧!
PAT A1039. Course List for Student (25)

PAT A1047. Student List for Course (25)

参考:C++ STL之vector用法总结
《算法笔记》(胡凡,曽磊)
 

目录
相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
2月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
73 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
80 2
动态规划算法学习三:0-1背包问题
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明