#创作计划#C++标准模板库(STL)

Ysjt | 深 ™

2024-11-25 16:32:55

发布于：广东

81阅读

0回复

0点赞

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来说这可能是一个重要的因素).