STL入门

作者：blue

时间：2024.3

[TOC]

0.概述

本文讨论部分常用的STL的运用

1.pair

pair是将2个数据组合成一组数据，

pair的实现是一个结构体，主要的两个成员变量是first second

pair<int ,double> p1;//注意中间要有逗号

p1.first = 1;

p1.second = 2.5;

cout<<p1.first<<' '<<p1.second<<endl;

//输出结果：1 2.5

还可以利用make_pair创建新的pair对象：

pair<int, double> p1;
p1 = make_pair(1, 1.2);        //make_pair
cout << p1.first << p1.second << endl;

//output: 1 1.2

int a = 8;

string m = "James";

pair<int, string> newone;

newone = make_pair(a, m);
cout << newone.first << newone.second << endl;

//output: 8 James

通过tie获取pair元素值

std::pair<std::string, int> getPreson() {
   
    return std::make_pair("Sven", 25);
}

int main(int argc, char **argv) {
   
    std::string name;
    int ages;

    std::tie(name, ages) = getPreson();

    std::cout << "name: " << name << ", ages: " << ages << std::endl;

    return 0;
}

2.set(集合)

集合是存储排序键的关联容器，其中每个键都是唯一的，可以插入或删除但不能更改。

初始化

template< class T,            
          class Compare = less<T>,    
          class Alloc = allocator<T>   
         > class set;

基本上就是三个参数，第一个是值，第二个比较器，用于比较内容，默认为less即降序，第三个是内存配置器，负责内存的分配和销毁。

在实际使用中，我们仅仅为其分配值就足以满足大部分需求。

set<int> s;    //直接指定值的类型创建，其他为默认方法

#include <iostream>
#include <set>
using namespace std;
int main()
{
                      /*两个‘>’之间最好有空格*/
    set<pair<double, double> > s;     //建立一个其中类型为pair<double,double>的集合，名为s
    int x1, y1, x2, y2;
    for (x1 = 0; x1 < 20; x1++)
    {
   
        for (y1 = 0; y1 < 21; y1++)
        {
   
            for (x2 = x1 + 1; x2 < 20; x2++)
            {
   
                for (y2 = 0; y2 < 21; y2++)
                {
   
                    double k = double(x1 - x2) / (y1 - y2);
                    double b = double(x2 * y1 - x1 * y2) / (x2 - x1);
                    s.insert({
    k,b });     //将元素值插入到集合s当中，集合会自动去重。
                }
            }
        }
    }
    printf("%lld", s.size() + 20);
    return 0;
}

set中元素的遍历

关键是要声明迭代器变量，遍历方法与数组类似，可以用while循环也可以用for循环，但用for循环时条件运算符不能用 <，而用 ！= 进行判断，还特别需要注意指针运算符

#include<iostream>
#include<set>
using namespace std;

set<int>all;
int main()
{
   
    //生成待处理的数据
    for(int i=0;i<100;i++)
        all.insert(i);
    //遍历set,用迭代器类型
              ⬇️⬇️⬇️ 注意这种
    for(set<int>::iterator i=all.begin();i!=all.end();i++)
        cout<<*i<<endl; //注意指针运算符
    return 0;
}

3.vector

vector是一个十分有用的容器

简单地说，vector是一个能够\存放任意类型的动态数组*，能够增加和压缩数据。*

实例：
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
signed main()
{
   
    int i;
    vector<int> a;           //定义
    for(i=0;i<=100;i++){
   
        a.push_back(i);      //尾部压入
    }
    for(i=0;i<a.size();i++)   //把其当数组来遍历 
    {
   
        printf("%lld ",a[i]);
    }
    reverse(a.begin(),a.end());   //逆转容器中的值 
    printf("\n");                        //⬇️，注意这里要用"!="
    for(vector<int>::iterator j=a.begin();j!=a.end();j++)  //把他用迭代器指针来遍历 
    {
   
                     //⬇️注意迭代器调用，用指针
        printf("%lld ",*j);
    }
    return 0; 
}

运行结果

排序

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).

bool cmp(int a,int b)
{
   
    return a>b;
}
调用时:sort(vec.begin(),vec.end(),Cmp)，这样就降序排序。

4.string字符串类型

C++ string中的find()函数 - 王陸 - 博客园 (cnblogs.com)

为什么 string.find()返回值是-1_string中find函数-1为什么是18446744073709551615-CSDN博客

两篇文章结合着看

0顺子日期 - 蓝桥云课 (lanqiao.cn)

本题考查了对字符串类型的应用

#include <iostream>
#include <string>
using namespace std;
int main()
{
   
  int ans=0;
  string t1="012",t2="123";
  for(int i=1;i<=12;i++)
  {
   
    for(int j=1;j<=31;j++)
    {
   
      string str="2022";
      if(i>=10) str+=to_string(i);
      else{
   
        str+='0';
        str+=to_string(i);
      }
      if(j>=10) str+=to_string(j);
      else{
   
        str+='0';
        str+=to_string(j);
      }
      if(str.find(t1)!=-1||str.find(t2)!=-1) ans++;
    }
  }
  printf("%d",ans);
  return 0;
}

C++:cin、cin.getline()、getline()的用法_getline(cin,s)函数用法-CSDN博客

关于string，输入带空格或tab的字符串的有趣的用法。

C++中substr()函数用法详解_c++ substr-CSDN博客

string的用法总让人大吃一惊，还能这样用？

 s.substr(pos, len)
 //string a=s.substr(0,3);
 s中从pos开始的len个字符的拷贝

5.queue，deque，priority_queue

队列

queue<type> q
q.push(x) //将x放入队列
q.front() //返回队首元素但不删除
q.pop()   //删除队首元素
q.back()  //返回队尾元素
q.size()  //返回元素个数
q.empty() //检查队列是否为空，空则返回true

双端队列

由于双端队列，队首队尾都可以入队与出队的特点，他的入队出队操作与普通的queue不同，要格外注意

deque<type> dq
dp[i] //返回队列中下标为i的元素
dq.front() //返回队头
dq.back()  //返回队尾
dq.pop_back()//删除队尾，不返回值
dq.pop_front()//删除队头，不返回值
dq.push_back(x)//在队尾添加一个元素x
dq.push_front(x)//在队头添加一个元素x

双端队列的一个重要应用——单调队列

①单调队列与滑动窗口

#include <iostream>
#include <queue>
using namespace std;
int main()
{
              //数组从下标1开始存储，这个0是占位 
    int a[]={
   0,2,6,5,7,8,6};
    int m=3;//窗口的大小 
    deque<int> Q;//存放元素的下标 

    //滑动窗口的边界为  [i-m+1,i] 
    for(int i=1;i<=6;i++)  //维护窗口的最小值，保持队首元素永远是窗口内最小的 
    {
   
        while(!Q.empty()&&a[Q.back()]>a[i]) Q.pop_back();  //新进元素更优，队尾出队 
        Q.push_back(i);//存储的是下标 
        if(Q.front()<i-m+1) Q.pop_front(); //队首已在窗口之外，队首出队 
        if(i>=m) printf("%d ",a[Q.front()]);//窗口充满，可以输出 
    }

    printf("\n");

    for(int i=1;i<=6;i++) //维护窗口的最大值 
    {
   
        while(!Q.empty()&&a[Q.back()]<a[i]) Q.pop_back();
        Q.push_back(i);
        if(Q.front()<i-m+1) Q.pop_front();
        if(i>=m) printf("%d ",a[Q.front()]);
    } 
    return 0;
}

优先队列（priority_queue）

默认大顶堆

priority_queue <Type, Container, Functional> 队列名 //类型，容器类型，比较方式

priority_queue <int,vector<int>,greater<int> > q;//升序队列（最小值优先）

priority_queue <int,vector<int>,less<int> >q;    //降序队列，最大值优先（默认的）

由于优先队列是以堆的形式存储数据的，所以队首的元素应该是堆顶（top），这一点要和其他队列区分开来

q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素

自定义优先级（要注意和自定义排序区分开，不要搞混了）

结构体自定义优先级

6.list的用法

详解C++STL容器系列（二）—— list的详细用法和与vector的对比_vector assign swap 区别-CSDN博客

掌握stl中list的用法

P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <iostream>
#include <list>
using namespace std;
int main()
{
   
    int n,m;
    cin>>n>>m;
    list<int> a;
    for(int i=1;i<=n;i++) a.push_back(i);
    list<int>::iterator it=a.begin();
    while(a.size()>1)
    {
   
        for(int i=1;i<m;i++){
   
            it++;
            if(it==a.end()) it=a.begin();
        }
        cout<<*it<<" ";
        list<int>::iterator next=++it;
        if(next==a.end()) next=a.begin();//end()成员函数返回指向末尾位置的迭代器。这个“末尾位置”            指的是最后一个元素再往后一位，也就是说end()所指的位置不包含有效元素，它相当于一个虚设的节点。
        a.erase(--it);
        it=next;
    }
    cout<<*it;
    return 0;
}