C++标准模板库(STL)

时间：2024-11-16 07:06:25

目录

 

00 Intro

01 STL模板库历史

STL容器主要包括(敲黑板): 容器(container) 算法(algorithm) 迭代器(iterator)

02 STL容器的使用(参考:[①](/qq_33278461/article/details/10005863),[②](/weixin_49303682/article/details/122137217))

我们先用表格讲一下STL容器的名称和区别

03 STL库-vector动态数组

vector数组简介:vector数组是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组，在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（list是一个双向链表，在同一个位置插入大量的数据时速度很快，但是查找的速度就会慢很多）

vector数组在初始化的时候,需要加上头文件

定义数组时,切记不可像int ,float ,double ,char一样直接定义

时间复杂度:O(n)

04 STL库-map(set)[2]

map的作用:访问地址符(篇幅有限,后面还有栈和队列,我们简单讲一下使用方法)

在map后加一个括号set是因为set拥有去重的功能,配合代码如下:

05 STL库-stack(栈)

顺序进出(入栈,出栈)

06 STL库-queue(队列)[3]

AC题解:

07 有必要的解释:

00 Intro

> 前面咱们主要讲的都是算法类的(例如:[高精度算法](/weixin_66580750/category_12708323.html),[深度优先搜索(DFS)&广度优先搜索(BFS)](/weixin_66580750/category_12708396.html),[排序算法](/weixin_66580750/category_12709035.html))
那么今天咱们讲的简单一点,把知识点往回倒,来介绍一下C++标准模板库(STL)

>>本文均同步[****-Ysjt | 深](/weixin_66580750?type=sub&spm=1001.2014.3001.5348)
点击链接关注!!!
>>> 话不多说进入正题:

01 STL模板库历史

对于软件界来说,做出一个可重复利用的东西是一直以来的梦想,为了实现这个梦想,就有许多我们熟悉的东西被发明创造了出来(后面我也会讲),例如**函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)**

>为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹
性、交互操作性(相互合作性,interoperability),诞生了STL。
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要
出现在 c+ +中，但是在引入 c++之前该技术已经存在很长时间了。
-- 选自[C++ - STL标准库](/weixin_49303682/article/details/122137217)

STL容器主要包括(敲黑板): 容器(container) 算法(algorithm) 迭代器(iterator)

02 STL容器的使用(参考:[①](/qq_33278461/article/details/10005863),[②](/weixin_49303682/article/details/122137217))

我们先用表格讲一下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动态数组

vector数组简介:vector数组是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组，在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（list是一个双向链表，在同一个位置插入大量的数据时速度很快，但是查找的速度就会慢很多）

vector数组在初始化的时候,需要加上头文件
#include<vector>

但如果定义的是万能头,则可以直接忽略

定义数组时,切记不可像int ,float ,double ,char一样直接定义

对于vector数组来说,要用:

    

  1. 

    

    
//定义:
    

    2. 

  2. 

    

    int<vector> 数组名;
    

    3. 

  3. 

    

    int a;
    

    4. 

  4. 

    

    
//输入:
    

    5. 

  5. 

    

    while(cin>>数组名){

    

    6. 

  6. 

    

        数组名.push_back(a);
    

    7. 

  7. 

    

    }
    

    8.

时间复杂度:O(n)

04 STL库-map(set)[2]

map的作用:访问地址符(篇幅有限,后面还有栈和队列,我们简单讲一下使用方法)

map跟vector一样,有专属于自己的头文件,见下:

#include<map>

使用万能头的可以忽略

在map后加一个括号set是因为set拥有去重的功能,配合代码如下:
    

  1. 

    

    
// 准备以id作为唯一标识去重的数据对象
    

    2. 

  2. 

    

    const arr = [
    

    3. 

  3. 

    

        { id: '01', value: 'aa' },
    

    4. 

  4. 

    

        { id: '01', value: 'aa' },
    

    5. 

  5. 

    

        { id: '02', value: 'cc' },
    

    6. 

  6. 

    

        { id: '03', value: 'dd' },
    

    7. 

  7. 

    

     ];
    

    8. 

  8. 

    

     
    

    9. 

  9. 

    

    const map = new Map();
    

    10. 

  10. 

    

     
    

    11. 

  11. 

    

    ((item) => {
    

    12. 

  12. 

    

        if (!()) {
    

    13. 

  13. 

    

          map.set(, item);
    

    14. 

  14. 

    

        }
    

    15. 

  15. 

    

     });
    

    16. 

  16. 

    

    
// 此时的map即为去重后的，拿到map的value,转成数据即可
    

    17. 

  17. 

    

    const newArr = Array.from(map.values());  // 得到去重后的数组
    

    18. 

  18. 

    

    (newArr)
    

    19. 

  19. 

    

     
    

    20.

05 STL库-stack(栈)

栈的东西太多,我个人认为可以单独开一篇文章讲解了(后续完善,可查看目录)
那么就将最重要的东西!!!!!

顺序进出(入栈,出栈)

接下来给出代码:ACGO官方例题

    

  1. 

    

    #include<iostream>

    

    2. 

  2. 

    

    
using namespace std;
    

    3. 

  3. 

    

    int top;
    

    4. 

  4. 

    

    int s[1010];
    

    5. 

  5. 

    

    
//入栈 
    

    6. 

  6. 

    

    void push(int x){
    

    7. 

  7. 

    

    	s[++top]=x;
    

    8. 

  8. 

    

    }
    

    9. 

  9. 

    

    
//出栈
    

    10. 

  10. 

    

    void pop() {
    

    11. 

  11. 

    

    	--top;
    

    12. 

  12. 

    

    }
    

    13. 

  13. 

    

     
    

    14. 

  14. 

    

    int Top(){
    

    15. 

  15. 

    

    	return s[top];
    

    16. 

  16. 

    

    }
    

    17. 

  17. 

    

     
    

    18. 

  18. 

    

    int size(){
    

    19. 

  19. 

    

    	return top;
    

    20. 

  20. 

    

    }
    

    21. 

  21. 

    

     
    

    22. 

  22. 

    

    bool empty()
    

    23. 

  23. 

    

    {
    

    24. 

  24. 

    

    	return top==0;	
    

    25. 

  25. 

    

    }
    

    26. 

  26. 

    

    int main(){
    

    27. 

  27. 

    

    	int n,x;
    

    28. 

  28. 

    

    	string s;
    

    29. 

  29. 

    

    	cin>>n;

    

    30. 

  30. 

    

    	while(n--){
    

    31. 

  31. 

    

    		cin>>s;

    

    32. 

  32. 

    

    		if(s=="empty"){
    

    33. 

  33. 

    

    			if(empty()) cout<<"yes";
    

    34. 

  34. 

    

    			else cout<<"no";
    

    35. 

  35. 

    

    			cout<<endl;
    

    36. 

  36. 

    

    		}
    

    37. 

  37. 

    

    		else if(s=="push"){
    

    38. 

  38. 

    

    			cin>>x;

    

    39. 

  39. 

    

    			push(x);
    

    40. 

  40. 

    

    		}
    

    41. 

  41. 

    

    		else if(s=="pop"){
    

    42. 

  42. 

    

    			if(!empty()){
    

    43. 

  43. 

    

                    cout<<"pop "<<Top();
    

    44. 

  44. 

    

                    pop();
    

    45. 

  45. 

    

                }
    

    46. 

  46. 

    

    			else cout<<"pop fail";
    

    47. 

  47. 

    

    			cout<<endl;
    

    48. 

  48. 

    

    		}
    

    49. 

  49. 

    

    		else if(s=="top"){
    

    50. 

  50. 

    

    			if(!empty()) cout<<"top = "<<Top();
    

    51. 

  51. 

    

    			else cout<<"top fail";
    

    52. 

  52. 

    

    			cout<<endl;
    

    53. 

  53. 

    

    		}
    

    54. 

  54. 

    

    		else if(s=="size"){
    

    55. 

  55. 

    

    			cout<<"size = "<<size()<<endl;
    

    56. 

  56. 

    

    		}
    

    57. 

  57. 

    

    		
    

    58. 

  58. 

    

    	} 
    

    59. 

  59. 

    

    	return 0;
    

    60. 

  60. 

    

    }
    

    61.

06 STL库-queue(队列)[3]

讲了这么多,到队列这我们直接引用了,(手指报废,眼睛报废),如果后面有时间会修改的 (AC君见谅)

队列是一种线性的数据结构【线性数据结构：数组、栈、队列】
相比数组，队列对应的数据操作是数组的子集。
只能从一端(队尾)添加元素，只能从另一端(队首)取出元素。

例题-传送门

AC题解:

    

  1. 

    

    #include<bits/stdc++.h>

    

    2. 

  2. 

    

    
using namespace std;
    

    3. 

  3. 

    

    int N=1e5+10;
    

    4. 

  4. 

    

    char q[300];
    

    5. 

  5. 

    

    int head,tail;
    

    6. 

  6. 

    

    void push(char x){
    

    7. 

  7. 

    

    	q[++tail]=x;
    

    8. 

  8. 

    

    }
    

    9. 

  9. 

    

    bool empty(){
    

    10. 

  10. 

    

    	return tail==head;
    

    11. 

  11. 

    

    }
    

    12. 

  12. 

    

    char front(){
    

    13. 

  13. 

    

    	return q[head+1];
    

    14. 

  14. 

    

    }
    

    15. 

  15. 

    

    void pop(){
    

    16. 

  16. 

    

    	head++;
    

    17. 

  17. 

    

    }
    

    18. 

  18. 

    

    int main(){
    

    19. 

  19. 

    

    	string s;
    

    20. 

  20. 

    

    	cin>>s;

    

    21. 

  21. 

    

    	for(int i=0;i<s.size();i++) push(s[i]);
    

    22. 

  22. 

    

    	while(!empty()){
    

    23. 

  23. 

    

    		cout<<front();
    

    24. 

  24. 

    

    		pop();
    

    25. 

  25. 

    

    		push(front());
    

    26. 

  26. 

    

    		pop();
    

    27. 

  27. 

    

    	}
    

    28. 

  28. 

    

    	return 0;
    

    29. 

  29. 

    

    }
    

    30. 

  30. 

    

     
    

    31.

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

  1. 03节参考内容:①,②,③,④,⑤ ↩︎

  2. 04节参考(引用):①,② ↩︎

  3. 06节参考(引用):① ↩︎

  4. 07节参考内容(引用):①,② ↩︎

  1. 03节参考内容:①,②,③,④,⑤ ↩︎

  2. 04节参考(引用):①,② ↩︎

  3. 06节参考(引用):① ↩︎

相关文章