C++的几种常用STL的用法,map,set,priority_queue

发表于 | 分类于 | 浏览 次

网上类似的博客有很多，我写这个博客主要是为了帮助自己和大家记住STL这几个容器相关的语法

  • 结构体的排序

    • 这三个容器都要求其中的元素可以排序，当插入元素为结构体时，需要通过重载运算符为结构体自定义排序方法。

      1
      2
      3
      4
      5
      6
      struct S{
          ll id,v;
          bool operator< (const S &a)const{
              return v<a.v;
          }
      }s[100];

      若对s结构体数组赋值后排序，则从左到右v依次增大
      可以理解为v代表左边那个,以参数形式传入的a.v代表右边那个，执行完排序之后，结构体中相邻两个元素满足return中的条件，上面的代码可以理解为排序之后左边的v<右边的v

  • set

    • C++的set是利用平衡二叉树实现的一个容器，具有以下特点

      1. 对于插入、删除和查找操作,set保证其时间复杂度都是$O(\log_2n)$（n是set中元素的个数）。
      2. set是一个有序的、可以前向和后向遍历的容器（双向迭代器）。
      3. set的元素可以插入、删除，但是不可更改。
      4. set中的元素不可重复。

      至于具体的原理去学习一下二叉排序树和平衡二叉树就会了解了

    • 插入

      • 1
        .insert();

    • 删除

      • 1
        .erase();

    • 判断是否存在

      • 1
        .count();

        count()本来是STL中用来判断某个元素出现多少次的函数，由于set中元素不能重复，返回值为0或1。

    • 遍历

      • 1
        2
        3
        4
        5
        6
        7
        set<int> s;
        int main(int argc, char const *argv[]) {
            for(int i=0;i<10;++i)
                s.insert(i);
            for(std::set<int>::iterator it=s.begin();it!=s.end();++it)
                cout<<*it<<" ";
        }

        C++11的新语法遍历（Range-based for loop）

        1
        2
        3
        4
        5
        6
        7
        set<int> s;
        int main(int argc, char const *argv[]) {
            for(int i=0;i<10;++i)
                s.insert(i);
            for(auto &v:s)
                cout<<v<<" ";
        }

        输出均为

        1
        0 1 2 3 4 5 6 7 8 9

    • 反向遍历

      • 1
        2
        3
        4
        5
        6
        7
        set<int> s;
        int main(int argc, char const *argv[]) {
            for(int i=0;i<10;++i)
                s.insert(i);
            for(std::set<int>::reverse_iterator rit=s.rbegin();rit!=s.rend();++rit)
                cout<<*rit<<" ";
        }

    • 遍历删除

      • 1
        2
        for(set<int>::iterator it=s.begin();it!=s.end();)
            s.erase(it++);

    • 选择性遍历删除

      • 1
        2
        3
        4
        for(set<int>::iterator it=s.begin();it!=s.end();)
         if((*it)%2)
             s.erase(it++);
        else it++;

        删除set中的奇数

    • 设置排序优先级

      • int或long long

        • 默认从小到大
          使用

          1
          set <int, greater<int> > setTest;

          可以从大到小排序（可以理解为左边的大，所以叫greater)

      • 结构体使用上文说的重载运算符来设置排序优先级

  • map

    • c++11新语法遍历

      1
      2
      3
      4
      5
      for(auto &kv:a)
      {   
          cout<<kv.first;    
          cout<<kv.second;
      }

    • 普通遍历

      1
      2
      3
      for (auto it = num_map.begin(); it != num_map.end(); ++it) {
             std::cout << it->first << ", " << it->second << '\n';
      }

  • priority_queue

    • 排序

      排序方法与set相同，但使用.top()函数时返回的是最右边的元素。

      1
      std::priority_queue<int, std::vector<int>, std::greater<int> >

      默认同样是左小右大，当需要左大右小是使用上面的语法。

    • 函数

      1
      2
      .top();
      .push();