常用STL及其使用方法

发表于 |
字数统计: | 阅读时长 ≈

STL

本文描述了基本的STL容器及其用法qwq

栈

  • STL
1
2
3
4
5
6
7
8
#include <stack> //头文件
std::stack<int> S;
S.top()//访问顶部元素
S.pop()//弹出栈顶元素
//这里记得检测是否为empty 否则RE
S.push(x)//扔x进栈
S.size()//查询stack的大小
S.empty()//检查stack是否为空

  • 手写

    1
    2
    3
    int S[maxn],tot;
    push:S[++tot]=x;
    pop:tot--;

队列/优先队列

  • STL

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <queue>
    std::queue<int> q;
    std::priority_queue<int> q;//大根堆
    q.top()//访问队首
    q.pop()//弹出队首
    q.push(x)//队尾插入x
    q.size()//查询队列长度
    q.empty()//查询是否为空
    //小根堆
    std::priority_queue<int,vector<int>,greater<int> >q;
    q.push(-x);//直接往大根堆扔相反数也行

    动态数组 / Vector

    • STL

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      std::vector<int> a;
      std::vector<int> v(n);//声明了一个 vector，它的每个元素类型为 int，初始元素数量为 n
      a.push_back(x);//加入元素
      a.resize(x)//重新指定大小
      a.pop_back();//删除元素
      a.size();//查询大小
      a[i];//直接访问（注意是否越界
      a.clear();//删除数组
      sort(a.begin(),a.end(),cmp);//排序
      for(RE int i = 1; i <= a.size(); i++) {//循环遍历
          .....a[i].....
      }

      使用 insert() 在某个特定的位置插入一个元素，时间复杂度为O(n)

      使用 erase() 删除某个位置的元素，时间复杂度为O(n)

    Map

    ​ Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力.

    • STL

      1
      2
      3
      4
      5
      6
      7
      #include <map>
      std::map<std::string,int> m;//定义一个string类型作下标，int类型为实值的map
      m["QAQ"] = 5;//赋值
      if(m.count("..."))...;//查询，注意这样子不会增加节点
      //但是如果if(m["..."] == 2333）则会增加节点
      m.erase("...");//删除节点
      m.clear();//删除map

      Set

    • STL

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      #include <set>
      set<int> s;
      s.insert(x);//插入x迭代器
      s.erase(x);//删除x迭代器
      s.size();//返回当前set容器中的元素个数
      s.empty();//判断set容器是否为空
      set<int>::iterator i;//
      i=s.upper_bound(x);//表示查找 >= x 的元素中最小的一个，并返回指向该元素的迭代器
      i=s.lower_bound(x);//表示查找 >x 的元素中最小的一个，并返回指向该元素的迭代器
      i=s.find(x);//返回x对应的迭代器（可能为空
      if(s.begin() != s.end())...;//判断set是否为空
      for(auto i=s.begin() ; i != s.end(); i++)...;//遍历容器
      *i;//访问i迭代器对应的内存地址
0%