C++ STL中setmap 与 priority_queue 中greater、less 的用法区别

admin管理员组

文章数量:1623788

2018.3.4更新：

在自定义类的操作符重载的编写的时候，都写'<'符号，

在使用STL的set(map)中体现出小的在前面；

在使用priority_queue却提现出大的在前面。

代码如下：

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <list>
#include <string>

using namespace std;

class sst{
public:
    int x;
    int y;
    sst(int a, int b):x(a), y(b){}
};

bool operator<(const sst& a, const sst& b)
{
    return a.x < b.x;       //注意这里是'<'，但是在map(set) 和 priority_queue中的排序方式却不同！
}

int main(void)
{
    //map
    map<sst, int> mp;
    for (int i = 0; i < 10; i++)
        mp[sst(i, i + 1)] = i * 5;
    cout<<"map :";
    for (auto it : mp)
        cout<<it.first.x<<"-"<<it.first.y<<"-"<<it.second<<" ";
    cout<<endl;
    
    //set
    set<sst> st;
    for (int i = 0; i < 10; i++)
        st.insert(sst(i, i + 1));
    cout<<"set :";
    for (auto it : st)
        cout<<it.x<<"-"<<it.y<<" ";
    cout<<endl;
    
    //priority_queue
    priority_queue<sst> pq;
    for (int i = 0; i < 10; i++)
        pq.push(sst(i, i + 1));
    cout<<"priority_queue :";
    while (!pq.empty())
    {
        cout<<pq.top().x<<"-"<<pq.top().y<<" ";
        pq.pop();
    }
    cout<<endl;
    
    return 0;
}

上面代码输出：

map :0-1-0 1-2-5 2-3-10 3-4-15 4-5-20 5-6-25 6-7-30 7-8-35 8-9-40 9-10-45 

set :0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 8-9 9-10 

priority_queue :9-10 8-9 7-8 6-7 5-6 4-5 3-4 2-3 1-2 0-1 

**********************************************分割*******************************************************

总结：

set和map：底层都是红黑树 less<> 最小堆，greater<>是最大堆。 默认是less。

make_heap:  less<>() 展现出来的是最大堆， greater<>()展现出来是最小堆。  默认是less。

priority_queue:   底层是使用heap实现的，所以表现出来的特性和heap一致。 

                     less<>() 展现出来的是最大堆， greater<>()展现出来是最小堆。  默认是less。

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <list>
#include <string>

using namespace std;

void set_about(vector<int> t)
{
    //默认情况 = less<int> 最小堆（最小的在头部或者说顶部）
    multiset<int> mst;
    for (auto& i : t)
        mst.insert(i);
    cout<<"set less<int> : ";
    for (auto i : mst)
        cout<<i<<" ";
    cout<<endl;
    
    //greater<int> 最大堆（最大的在头部或者说顶部）
    multiset<int, greater<int>> mst2;
    for (auto& i : t)
        mst2.insert(i);
    cout<<"set greater<int> : ";
    for (auto i : mst2)
        cout<<i<<" ";
    cout<<endl;
}

void map_about(vector<int> t)
{
    //默认情况 = less<int> 最小堆（最小的在头部或者说顶部）
    multimap<int, int> mmp;
    for (auto& i : t)
        mmp.insert(make_pair(i, i));
    cout<<"map less<int> : ";
    for (auto i : mmp)
        cout<<i.first<<"-"<<i.second<<"  ";
    cout<<endl;
    
    //greater<int> 最大堆（最大的在头部或者说顶部）
    multimap<int, int,  greater<int>> mmp2;
    for (auto& i : t)
        mmp2.insert(make_pair(i, i));
    cout<<"map greater<int> : ";
    for (auto i : mmp2)
        cout<<i.first<<"-"<<i.second<<"  ";
    cout<<endl;
}

void heap_about(vector<int> t) //测试自带的heap工具
{
    //默认情况 是 最大堆
    cout<<"heap 默认 :";
    for (int i = 0; i < t.size(); i++)
    {
        make_heap(t.begin() + i, t.end(), greater<int>() );
        cout<<t[i]<<" ";
    }
    cout<<endl;
    
    //less<int>()  heap的less竟然是最大堆
    cout<<"heap less<int>() :";
    for (int i = 0; i < t.size(); i++)
    {
        make_heap(t.begin() + i, t.end(), less<int>() );
        cout<<t[i]<<" ";
    }
    cout<<endl;
    
    //greater<int>()  heap的greater竟然是最小堆
    cout<<"heap greater<int>() :";
    for (int i = 0; i < t.size(); i++)
    {
        make_heap(t.begin() + i, t.end(), greater<int>() );
        cout<<t[i]<<" ";
    }
    cout<<endl;
}

int main(void)
{
    vector<int> t = {4,5,1,1,1,6,2,7,3,8};
    set_about(t);
    map_about(t);
    heap_about(t);
    return 0;
}

set less<int> : 1 1 1 2 3 4 5 6 7 8 

set greater<int> : 8 7 6 5 4 3 2 1 1 1 

map less<int> : 1-1  1-1  1-1  2-2  3-3  4-4  5-5  6-6  7-7  8-8  

map greater<int> : 8-8  7-7  6-6  5-5  4-4  3-3  2-2  1-1  1-1  1-1  

heap 默认 :1 1 1 2 3 4 5 6 7 8 

heap less<int>() :8 7 6 5 4 3 2 1 1 1 

heap greater<int>() :1 1 1 2 3 4 5 6 7 8 

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < 10; i++)
        pq.push(i);
    while(!pq.empty())
    {
        cout<<pq.top()<<" ";           //注意priority_queue取头元素是 top();
        pq.pop();
    }

0 1 2 3 4 5 6 7 8 9

本文标签： 区别setstlmapgreater