STL之sort、priority_queue 排序

深藏阁楼爱情的钟 2021-06-24 15:57 446阅读 0赞

前几天在使用priority\_queue时，发现其与sort排序相反，遂做个对比。

## **一、sort** ##

sort()一般情况下,会使用快排,但是发现效率不高的话,会自动调整成其他排序来辅助。sort的默认排序为less，也就是说从小到大排序。

字符排序：从小到大
    char ch[20]="dcba";
    sort(ch,ch+14);
    // a b c d
    // 使用string自带迭代器
    string str("cvicses");
    string s(str.rbegin(),str.rend());

自定义排序函数：从大到小
    int a[10];
    bool complare(int a,int b)
    {
      return a>b;
    }
    sort(a,a+10,complare)

可使用STL自带函数作为排序函数
    int a[10];
    sort(a,a+10,less<int>());
    sort(a,a+10,greater<int>());

定义结构体排序函数：
    bool com(const int& a, const int& b ){  
        return a < b ; //从小到大 
    }  
    struct scmp{  
        bool operator()( const int& a , const int& b ){  
            return a < b ;      //从小到大 
        }  
    }; 
    sort(a,a+10, com ) ;  
    sort(a,a+10, scmp() ) ;

结构体自身排序函数：
    struct line{
        int u,v,w;
        friend bool operator < (const line &a, const line &b){
            return a.w<b.w;
        }   // STL默认重载<排序函数
    };
    line edges[200000];
    sort(edges, edges+m);

对vector<int>进行排序：
    sort(road.begin(),road.end());

struct Node{
        int time,key,isget;
        Node(int t, int k, int s):time(t),key(k),isget(s){}
        Node(){}
    };
    
    bool comp(Node& a, Node& b){
        if(a.time<b.time){
            return true;
        }else if(a.time==b.time && a.isget<b.isget){
            return true;
        }else if(a.time==b.time && a.isget==b.isget && a.key<b.key){
            return true;
        }else{
            return false;   //需保证至少返回一个值，切记最后一个else
        }
    }
    vector<Node> node;
    sort(node.begin(),node.end(),comp);  //comp不能加括号，加括号相当如无参函数

使用类：
    enum Enumcomp{ASC,DESC};
    class compare
    {
      private:
          Enumcomp comp;
      public:
          compare(Enumcomp c):comp(c) {};
      bool operator () (int num1,int num2)
      {
          switch(comp)
          {
              case ASC:
                  return num1<num2;
              case DESC:
                  return num1>num2;
          }
     }
    };
    sort(a,a+20,compare(DESC));

## **二、priority\_queue** ##

priority\_queue默认排序是less，也就说大顶堆；在此排序下使用top()取值时实际取得是堆顶，也就是说取值时是从大到小排序。由于priority\_queue底层使用的是Push\_heap。每次添加元素入堆时，在默认情况下添加进去的数据作为较小值入堆，priority\_queue中top()表示堆顶元素，所以是最大值。

// 默认大顶堆
    int a[3] = {
       1，2，3};
    priority_queue<int> pq;
    for(i = 0; i < 3; i++)
        pq.push(a[i]);
    for(i = 0; i < 3; i++)
    {
        cout<<pq.top()<<" ";   // 输出:3 2 1。默认大顶堆，元素大的优先级高
        pq.pop();
    }

// 实现小顶堆：从大到小
    priority_queue<int, vector<int>, greater<int> > pq;
    ----------------------------------------------------
    struct Node{
        int x, y;
        Node(int a, int b): x(a), y(b) {}
        friend bool operator<(Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    priority_queue<Node> pq;  // 只需定义一个struct就行了。

struct Node{
        int x, y;
        Node(int a, int b): x(a), y(b) {}
        friend bool operator<(Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    struct Cmp{
        bool operator() (Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    priority_queue<Node, vector<Node>, Cmp> pq;  // 第三个参数自定义时需每个参数显示调用。

## **三、map、set** ##

map、set默认排序是less，用迭代器迭代的时候是从小到大排序的。