算法学习之路|用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>。
AI 代码解读

一、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;
AI 代码解读
  • 这个定义相当于定义了一个一维的数组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],
//原因如上
AI 代码解读

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;//见下文分解
}
AI 代码解读

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

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; 
}
AI 代码解读
  • 元素翻转
C#include <algorithm>
reverse(vec.begin(), vec.end());
AI 代码解读
  • 元素排序
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);
AI 代码解读

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用法总结
《算法笔记》(胡凡,曽磊)
 

目录
打赏
0
0
0
0
1243
分享
相关文章
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
79 11
架构学习:7种负载均衡算法策略
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
45 19
|
17天前
|
C++学习之继承
通过继承,C++可以实现代码重用、扩展类的功能并支持多态性。理解继承的类型、重写与重载、多重继承及其相关问题,对于掌握C++面向对象编程至关重要。希望本文能为您的C++学习和开发提供实用的指导。
48 16
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法(如DES、3DES、AES和国密SM4)及其应用场景,包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法,并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程,以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
58 4
2023/11/10学习记录-C/C++对称分组加密DES
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
37 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
30 1
|
26天前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
51 4
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
52 7
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等