#创作计划#C++标准模板库(STL)
2024-11-21 14:58:42
发布于：广东
00 Intro
前面咱们主要讲的都是算法类的(例如:高精度算法,深度优先搜索(DFS)&广度优先搜索(BFS),排序算法)
那么今天咱们讲的简单一点,把知识点往回倒,来介绍一下C++标准模板库(STL)本文均同步CSDN-Ysjt | 深
点击链接关注!!!话不多说进入正题:
01 STL模板库历史
对于软件界来说,做出一个可重复利用的东西是一直以来的梦想,为了实现这个梦想,就有许多我们熟悉的东西被发明创造了出来(后面我也会讲),例如函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹
性、交互操作性(相互合作性,interoperability),诞生了STL。
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要
出现在 c+ +中，但是在引入 c++之前该技术已经存在很长时间了。
-- 选自C++ - STL标准库
STL容器主要包括(敲黑板): 容器(container) 算法(algorithm) 迭代器(iterator)
02 STL容器的使用(参考:①,②)
我们先用表格讲一下STL容器的名称和区别
| 容器 | 实现 | 查询 | 插入 | 删除 | 其它 |
|---|---|---|---|---|---|
| vector(本篇讲解) | 一段内存连续区域 | 查询下标O(1) 值查询O(N) | 尾部O(1) 中间O(N) | 尾部O(1) 中间O(N) | 空间只增不减,空间够,1.5-2倍扩容 |
| list | 双向链表 | O(N) | O(1) | O(1) | |
| deque | 中控器map+多个连续缓冲区 | 查询下标O(1) 值查询O(N) | 尾部O(1) 头部O(N) | 尾部O(1) 头部O(N) | list&vector(见上)折中 |
| map(set)(本篇讲解) | 红黑树(无重复,有序) | 下标访问log2(N) | log2(N) | log2(N) | |
| stack(本篇讲解) | deque | 插入栈顶O(1) | 删除栈顶O(1) | ||
| queue(本篇讲解) | deque | 插入队尾O(1) | 插入队头O(1) |
03 STL库-vector动态数组[1]
vector数组简介:vector数组是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组，在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（list是一个双向链表，在同一个位置插入大量的数据时速度很快，但是查找的速度就会慢很多）
vector数组在初始化的时候,需要加上头文件
#include<vector>
但如果定义的是万能头,则可以直接忽略
定义数组时,切记不可像int ,float ,double ,char一样直接定义
对于vector数组来说,要用:
//定义:
int<vector> 数组名;
int a;
//输入:
while(cin>>数组名){
数组名.push_back(a);
}
时间复杂度:O(n)
04 STL库-map(set)[2]
map的作用:访问地址符(篇幅有限,后面还有栈和队列,我们简单讲一下使用方法)
map跟vector一样,有专属于自己的头文件,见下:
#include<map>
使用万能头的可以忽略
在map后加一个括号set是因为set拥有去重的功能,配合代码如下:
// 准备以id作为唯一标识去重的数据对象
const arr = [
{ id: '01', value: 'aa' },
{ id: '01', value: 'aa' },
{ id: '02', value: 'cc' },
{ id: '03', value: 'dd' },
];
const map = new Map();
arr.forEach((item) => {
if (!map.has(item.id)) {
map.set(item.id, item);
}
});
// 此时的map即为去重后的，拿到map的value,转成数据即可
const newArr = Array.from(map.values()); // 得到去重后的数组
console.log(newArr)
05 STL库-stack(栈)
栈的东西太多,我个人认为可以单独开一篇文章讲解了(后续完善,可查看目录)
那么就将最重要的东西!!!!!
顺序进出(入栈,出栈)
接下来给出代码:ACGO官方例题
#include<iostream>
using namespace std;
int top;
int s[1010];
//入栈
void push(int x){
s[++top]=x;
}
//出栈
void pop() {
--top;
}
int Top(){
return s[top];
}
int size(){
return top;
}
bool empty()
{
return top==0;
}
int main(){
int n,x;
string s;
cin>>n;
while(n--){
cin>>s;
if(s=="empty"){
if(empty()) cout<<"yes";
else cout<<"no";
cout<<endl;
}
else if(s=="push"){
cin>>x;
push(x);
}
else if(s=="pop"){
if(!empty()){
cout<<"pop "<<Top();
pop();
}
else cout<<"pop fail";
cout<<endl;
}
else if(s=="top"){
if(!empty()) cout<<"top = "<<Top();
else cout<<"top fail";
cout<<endl;
}
else if(s=="size"){
cout<<"size = "<<size()<<endl;
}
}
return 0;
}
06 STL库-queue(队列)[3]
讲了这么多,到队列这我们直接引用了,(手指报废,眼睛报废),如果后面有时间会修改的 (AC君见谅)
队列是一种线性的数据结构【线性数据结构：数组、栈、队列】
相比数组，队列对应的数据操作是数组的子集。
只能从一端(队尾)添加元素，只能从另一端(队首)取出元素。
AC题解:
#include<bits/stdc++.h>
using namespace std;
int N=1e5+10;
char q[300];
int head,tail;
void push(char x){
q[++tail]=x;
}
bool empty(){
return tail==head;
}
char front(){
return q[head+1];
}
void pop(){
head++;
}
int main(){
string s;
cin>>s;
for(int i=0;i<s.size();i++) push(s[i]);
while(!empty()){
cout<<front();
pop();
push(front());
pop();
}
return 0;
}
07 STL库-list(链表)[4]
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素).
代码及例题不给了(作者懒)
修改发布时间:2024年7月3日18:43:12
有帮助，赞一个