当前位置: 首页 > news >正文

(蓝桥杯C/C++)——STL(下)

目录

一、list

1.list的定义与结构

2.list的常用函数

二、set

1.set集合

         2.multiset多重集合

        3.unordered set无序集合

三、queue

1.queue队列

priority_queue优先队列

3.deque双端队列


一、list

1.list的定义与结构

list的使用频率不高,在做题时极少遇到需要使用list的情景list是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器list容器以节点(node)的形式存储元素,并使用指针将这些节点链接在一起,形成一个链表结构。

list容器的定义和结构如下:

template<class T,class Allocator = std::allocator<T>>

class list;

ist容器模板接受两个参数:

1.T:指定容器中存储的元素类型

2.Allocator(可选):指定用于分配内存的分配器类型,默认为std:allocator<T>。

list容器的特点包括:·

双向性:每个节点都包含指向前一个节点和后一个节点的指针,因此可以在常数时间内在链表中的任意位置进行插入、删除和访问操作。

动态大小:链表的大小可以根据需要动态扩展或收缩,不需要预先指定容器的大小

不连续存储:链表中的节点可以在内存中的任意位置分布,不要求连续存因此插入和删除操作不会导致元素的移动。list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素,包删除、访问、反转等操作。可以使用迭代器来遍历链表中的元素

list的使用频率不高,在做题时极少遇到需要使用list的情景。

list是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器list容器以节点(node)的形式存储元素,并使用指将这些节点链接在一起,形成一个链表结构。

list容器的定义和结构如下:

template <class(T)class Allocator= std::allocator<T>>
class list;

以下是一个示例,展示如何使用list容器:
     #include <iostream>
     #include <list>

           int main()

   {
          std::list<int> mylist;
         //在链表尾部指入元素myList;

         myList.push back(1);

         myList.push back(2);

         myList.push_back(3);
       

         //在链表头部插入元素

         myList.push_ front(0);
        //历链表并输出元素
        for(int num: myList)

          {
               std::cout << num << " ";

          }
               std::cout << std::endl;
    return 0;

}


在上述示例中,我们首先创建了一个list容器myList,然后使用push back()和push front()函数分别在链表尾部和头部插入元素。最后,使用范围基于范围的for循环遍历链表并输出元素。需要注意的是,由于list是双向链表,因此插入和删除操作的时间复杂度是常量时间O(1),但访问和查找操作的时间复杂度是线性时间O(n),其中n是链表的大小。因此,如果需要频繁进行随机访问操作,可能更适合使用支持随机访问的容器,如vector或deque。

2.list的常用函数

list容器提供了多个常用的成员函数来操作和访问链表中的元素。以下是一些常用的list函数的解释:
1.push back(): 将元素插入到链表的末尾
2.push front():  将元素插入到链表的开头
3.pop_back():  移除链表末尾的元素
4.pop_front():  移除链表开头的元素。
5.size(): 返回链表中元素的个数。
6.empty(): 检查链表是否为空。

7.clear(): 清空链表中的所有元素

8.front():返回链表中第一个元素的引用。
9.back()返回链表中最后一个元素的引用。
10.begin(): 返回指向链表第一个元素的迭代器。
11.end(): 返回指向链表未尾的下一个位置的迭代器。
12.insert(): 在指定位置之前插入一个或多个元素

13.erase():从链表中移除指定位置的一个或多个元素

二、set

1.set集合

set是一种容器,用于存储一组唯一的元素,并按照一定的排序规则进行排序。set中的元素是按照升序排序的默认情况下,它使用元素的比较运算符(<)来进行排序。

set的定义和结构如下:

emplate   << class Key,class Compare  = less<Key>,
                class Allocator =  allocator<Key>>
class set;


·Key: 表示存储在set中的元素的类型。

·Compare: 表示元素之间的比较函数对象的类型,默认为less,即按照元素的值进行比较」

·Allocator: 表示用于分配内存的分配器类型,默认为allocator。set的内部实现使用了红黑树(一种自平衡的二叉搜索树)来存储元素,并保持元素的有序性这使得在set中插入、删除和查找元素的时间复杂度都是对数时间,即O(log n)。set中的元素是唯一的,即不允许重复的元素存在。当插入一个重复的元素时,set会自动忽略该元素。


 

函数
insert
erase
find
lower_bound

upper_bound

size

empty

clear

begin

end

rbegin

rend

描述
向集合中插入元素
从集合中移除元素
查找集合中的元素
返回第一个不小于给定值的迭代器

返回第一个大于给定值的的迭代器

返回一个范围,其中包含所有给定值的元素
返回集合中元素的数量
检查集合是否为空
清空集合

返回指向集合起始位置的迭代器
返回指向集合末尾位置的迭代器
返回指向集合末尾位置的逆向迭代器
返回指向集合起始位置的逆向迭代器

平均时间复杂度
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
O(1)
O(1)
O(n)

O(1)
O(1)

O(1)
O(1)

最坏时间复杂度

O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
O(1)
O(1)
O(n)

O(1)
O(1)

O(1)
O(1)

set示例
#include<iostream>
#include <set>

using nanespace std;

struct MyCo
bool operator()(const int& aconst int系 b)const// 自宝义比较逻辑return a>b;// 改为送序
      int main()

    {
       set <int,  greater<int>> myset;
             mySet.insert(25);

             mySet.insert(17);

             mySet.insert(39);

             mySet.insert(42);

            for (const auto& elem : mySet)

                    {

                     cout << elem <<" ";

                   }

                  cout << endl;

                 return 0;

}

multiset示例

#include<iostream>
#include <set>

using nanespace std;

     struct MyCompare

     {

      bool operator()(const int& a,const int& b) const

         {

              //自定义比较逻辑

             return  a > b;  //改为逆序 

            }

};
          int main()

                {

                  set<int,  MyCompare> mySet;

                  

             mySet.insert(25);

             mySet.insert(17);

             mySet.insert(39);

             mySet.insert(42);


           for (const auto& elem : mySet)

       {

            cout << elem <<" ";

        }

     cout << endl;
return 0;

}


2.multiset多重集合

函数
insert
erase
find
lower_bound

upper_bound

size

empty

clear

begin

end

rbegin

rend

描述
向集合中插入元素
从集合中移除元素
查找集合中的元素
返回第一个不小于给定值的迭代器

返回第一个大于给定值的的迭代器

返回一个范围,其中包含所有给定值的元素
返回集合中元素的数量
检查集合是否为空
清空集合

返回指向集合起始位置的迭代器
返回指向集合末尾位置的迭代器
返回指向集合末尾位置的逆向迭代器
返回指向集合起始位置的逆向迭代器

平均时间复杂度
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
O(1)
O(1)
O(n)

O(1)
O(1)

O(1)
O(1)

最坏时间复杂度

O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
O(1)
O(1)
O(n)

O(1)
O(1)

O(1)
O(1)

3.unordered set无序集合

unordered_set是一种容器,用于存储一组唯一的元素,并且没有特定的顺序。unordered_set容器使用哈希表来实现元素的存储和访问,因此元素的插入、删除和查找的时间复杂度都是常数时间,即0(1)。

unordered_set的定义和结构如下:
template <class Key, class Hash = hash<Key>,

                 class KeyEqual =equal to<Key>,

                 class Allocator=allocator<Key>>

class unordered set;


Key: 表示存储在unordered set中的元素的类型。

Hash: 表示用于计算元素哈希值的哈希函数对象的类型,默认为hash,使用Key类型的默认哈希函数。

KeyEqual: 表示用于比较元素是否相等的函数对象的类型,默认为equal_to,使用Key类型的默认相等比较函数。

Allocator: 表示用于分配内存的分配器类型,默认为allocator。

unordered_set中的元素是唯一的,即不允许重复的元素存在。当插入一个重复的元素时,unordered_set会自动忽略该元素

这些时间复杂度是基于哈希函数的性能和哈希冲突的情况来计算的。平均情况下,unorderedset的插入、查找和移除操作都具有常数时间复杂度0(1)。然而,在最坏情况下这些操作的时间复杂度可能为O(n)其中n是无序集合中的正素整致:最地性深通设公生在项希决交较为品重的饰况所以我们一般情况下不会使用unordered_set,而选择使用复杂度更稳定的set

函数
insert
erase
find

count

size

描述
向集合中插入元素
从集合中移除元素
查找集合中的元素

返回元素在集合中出现次数

返回无序集合中元素的数量

平均时间复杂度

O(1)
O(1)

O(1)
O(1)

O(1)

最坏时间复杂度

O(n)

O(n)

O(n)

O(n)

O(n)

三、queue

1.queue队列

queue是一种先进先出(FIF0)的数据结构。

queue提供了一组函数来操作和访问元素,但它的功能相对较简单。

queue的定义和结构如下:
template <class T, class Container = deque<T>>
                class queue;


·T:  表示存储在queue中的元素的类型。

*Container:  表示底层容器的类型,默认为degue。也可以使用其他容器类型,如list。queue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。

以下是一些queue的常用函数:

函数
push(x)
pop0
front()
back()

empty()

size()

描述
在队尾插入元素 x
弹出队首元素
返回队首元素
返回队尾元素

检查队列是否为空

返回队列中元素的个数

时间复杂度
O(1)
O(1)
O(1)
O(1)
O(1)

O(1)

priority_queue优先队列


priority_queue与普通队列不同,priority queue中的元素是按照一定的优先级进行排序的。默认情况下,priority_queue按照元素的值从大到小进行排序,即最大元素位于队列的前面priority aueue的定义和结构如下(仅做了解即可):

template <classT, class Container =  vector<T>,

              class Compare = less<typename Container::value type>>
class priority queue;

T: 表示存储在priority queue中的元素的类型,

Container: 表示底层容器的类型,默认为vector。也可以使用其他容器类型,如deque。

Compare: 表示元素之间的比较函数对象的类型,默认为less,即按照元素的值进行比较。priority_queue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素,

以下是一些priority_queue的常用函数:

优先队列是一个十分重要的数据结构考察频率极高。

函数

push(x)
pop()
top()
empty()
size()

描述

将元素x插入到优先队列中
弹出优先队列中的顶部元素
返回优先队列中的顶部元素
检查优先队列是否为空

返回优先队列中元素的个数

时间复杂度

O(logN)
O(logN)
O(1)
O(1)
O(1)

接下来介绍几种优先队列修改比较函数的方法

struct compare

{

    {
       bool operator()(int a, int b)          //自定义的比较函数,按照逆序排列

      return a > b;

    }

}

int main()

{
       std: :priority_ queue<int, std::vector<int>, compare> pq;

另一种方法:

auto compare = [ ](int a, int b)        

//自定义的比较函数,按照逆序排列

          {

             return a > b;

          }

}
  std::priority queue<int,std::vector<int>, decltype (compare)> pq(compare)


如果优先队列中的元素类型比较简单,可以直接使用greater<T>来修改比较方法。

priority queue<int,vector<int>,greater<int>>pq;std::greater函数对象定义在<functional>头文件中。

3.deque双端队列

deque(双端队列)是一种容器,它允许在两端进行高效的插入和删除操作。deque是由一系列连续的存储块(缓冲区)组成的,每个存储块都存储了多个元素。这使得deque能够在两端进行快速的插入和删除操作,而不需要移动其他元素。
deque的定义和结构如下(仅做了解即可):

template <class T,class Allocator =allocator<T>)

                 class deque;


T:表示存储在degue中的元素的类型。

Allocator:表示用于分配内存的分配器类型,默认为allocator

degue的内部实现使用了一系列的存储块(缓冲区),每个存储块存储了多个元素,并且通过指针进行连接。

这种设计使得在两端进行插入和删除操作的时间复杂度为常数时间,即0(1)。“单调队列”将使用双端队列来实现。单纯考察双端队列的并不常见。

函数
push back(x)
push_front(x)
pop_back()
pop_front()
front()
back()
empty()
size()
clear()
描述
在尾部插入元素 x
在头部插入元素 x
弹出尾部元素
弹出头部元素
返回头部元素
返回尾部元素
检查 deque 是否为空
返回 deque 中元素的个数
清空 deque 中的所有元素
时间复杂度
平摊O(1)
平摊O(1)
平摊O(1)
平摊O(1)
0(1)
0(1)
0(1)
0(1)
O(N)


http://www.mrgr.cn/news/62753.html

相关文章:

  • PostgreSQL的学习心得和知识总结(一百五十七)|新的 COPY 选项 LOG_VERBOSITY
  • 【CTF】 文件包含漏洞——data伪协议 【详】
  • AI产品经理岗,面试了个211女孩,真的不错
  • 【Java笔记】2-Java和C++/Go等基础语法不同之处
  • 如何在Linux系统中使用rsync进行高效的文件同步
  • [Chrome插件开发]关于报错Service worker registration failed. Status code: 15
  • 【微服务】Nacos 注册中心
  • 17. 从尾到头打印链表
  • 白盒测试基本概念(学习笔记)
  • Redis数据库
  • 【IC每日一题--单bitCDC跨时钟和同步FIFO】
  • mysql8.0.32升级到8.0.40
  • LeetCode20:有效的括号
  • 支持ANC的头戴式蓝牙耳机,更有小金标认证,QCY H3 Pro体验
  • 10.30
  • AR基础知识:SLAM同时定位和构图
  • 功能强大视频编辑软件 Movavi Video Editor Plus 2024 v24.2.0 中文特别版
  • ValueError: Object arrays cannot be loaded when allow_pickle=False
  • Typora配置GitHub图床--结合PicGo
  • 配置DDNS结合光猫路由器实现外网映射
  • SAP 采购申请的增强(对内容的处理,比如批次)
  • MySQL的使用
  • 亚马逊云免费Amazon CloudFront服务
  • 基于单片机的无线气象仪系统设计(论文+源码)
  • 程序员工作七年,我踩过的那七个坑
  • 好的呼叫中心系统是什么样的