how to create an ordered set using two ordering criteria(for a set of pairs) in c++?

Question

i need to order a set of pairs (one is int, the second one is char), and i need to have my set ordered like this: 12 G, 11 F, 10 A, 10 B, 10 C (in descending order by first, and in ascending order by second) firstly. this is what i've tried so far, and i get some errors:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;
set <pair <int,char> > s;

bool myfunction( const pair<int, char>& i, const pair<int, char>& j ) {
    if( i.first < j.first ) return false;
    if( j.first < i.first ) return true;
    return j.second < i.second;
}

void writes()
{   set <pair<int,char> >::iterator it;
    for (it = s.begin();it<= s.end();it++) /// line (18)
        cout<<(*it).second<<" "<<(*it).first<<"\n\n";
}
int main()
{   ifstream f("info.in");
    int n;
    f>>n;
    for (int i=1;i<=n;i++)
    {   pair<int,char> x;
        int st;
        char nd;
        f>>st;
        f>>nd;
        x.first=st;
        x.second=nd;
        s.insert(x);
    }
    writes();
}

first error i get is at line (18) : no match for 'operator<=' (operand types are 'std::set >::.....

your help is greatly appreciated

my input file looks like this:

@Sam Varshavchik, thanks! that solved my problem with the errors. But still, i don't get the output i needed. I only get:

10 A
10 B
10 C
11 F
12 G

is it possible to change the order criteria in a pair ? if not, what would you recommend to use instead?

it looks like myfunction for the ordering criteria is still ignored by the program. how cand i overload it inside my pair? it looks like, it just sits there and it's never used. the program does it job regardless

i've also tried this: Using custom std::set comparator but it's still not working

using namespace std;

struct lex_compare {
    bool operator()(const pair<int, char>& i, const pair<int, char>& j )
{
   if( i.first != j.first )
   {
      return (i.first > j.first);
   }

   return (j.second > i.second);
}
} // forgot ";", after adding it, it works perfectly.
set <pair <int,char>, lex_compare > s; ///line (22)

void writes()
{   set <pair<int,char> >::iterator it;
    for (it = s.begin();it!= s.end();it++) /// line (18)
        cout<<(*it).second<<" "<<(*it).first<<"\n\n";
}
int main()
{   ifstream f("info.in");
    int n;
    f>>n;
    for (int i=1;i<=n;i++)
    {   pair<int,char> x;
        int st;
        char nd;
        f>>st;
        f>>nd;
        x.first=st;
        x.second=nd;
        s.insert(x);
    }
    writes();
}

ERROR: line (22): invalid declarator before 's';

`// forgot ";", after adding it, it works perfectly.` Voting to close as based on a simple typographical error. — n. m. could be an AI, May 31 '16 at 05:34

score 2 · Answer 1 · edited May 31 '16 at 01:01

for (it = s.begin();it<= s.end();it++)

Iterators, generally, do not implement less/greater-than type of comparisons. Iterators, generally, implement only == and != comparisons, tests for equality. This should be:

for (it = s.begin();it != s.end();it++)

(Only random access iterators can safely be comparison using < and > operators, and a std::sets iterators are not random access iterators)

This answers the question you posed: the compilation error. This question doesn't really have anything to do with your custom set comparison function; which would be a different question.

R Sahu · Answer 2 · 2016-05-31T05:07:40.533

Based on

in descending order by first, and in ascending order by second

The comparison function needs to be:

bool myfunction( const pair<int, char>& i, const pair<int, char>& j )
{
   if( i.first != j.first )
   {
      return (i.first > j.first);
   }

   return (j.second < i.second);
}

And then, make sure to use it when working with the set. Instead of using

set <pair <int,char> > s;

use

set <pair <int,char>, mycompare > s;

That will require a few more changes to your program.

You will need to declare/define mycompare before defining s.

The iterator type needs to be changed too. You have

set <pair<int,char> >::iterator it;

that needs to be:

set <pair<int,char>, mycompare >::iterator it;

If the compiler you are using supports C++11, you can use auto also.

void writes()
{
   auto it = s.begin();
   for ( ; it != s.end(); it++)
   {
      cout<<(*it).second<<" "<<(*it).first<<"\n\n";
   }
}

it looks like myfunction for the ordering criteria is still ignored by the program. how cand i overload it inside my pair? it looks like, it's just there and it's never used. the program does it job regardless — meiznub, May 31 '16 at 01:14

Nick Matteo · Answer 3 · 2016-05-31T01:45:44.137

You never call myfunction or do anything with it!

To use it to order your set, turn myfunction into a functor, like this:

struct comparepair {
    bool operator()( const pair<int, char>& i, const pair<int, char>& j ) {
        if( i.first < j.first ) return false;
        if( j.first < i.first ) return true;
        return i.second < j.second;
    }
};

Then declare the set afterward with it as the comparator, like

set <pair <int,char>, comparepair > s;

Tobias Gurdan · Answer 4 · 2016-05-31T02:01:50.360

In order to use custom comparators, you have to tell the container about the function/functor as described in the SO-question you linked above.

Here is a working example for your case.

#include <iostream>
#include <set>

typedef std::pair<int, char> pic_t;


struct comp {
    bool operator () ( const pic_t& p1, const pic_t& p2 ) const {
        return ( p1.first != p2.first ) ? ( p1.first > p2.first ) : ( p1.second < p2.second );
        //  identical, slightly better performance:
        //  return ( p1.first > p2.first ) || ( ! ( p2.first > p1.first ) && ( p1.second < p2.second ) );
    }
};


int main()
{
    std::set<pic_t, comp> s = { { 10, 'b' }, { 10, 'a' }, { 10, 'c' }, { 11, 'f' }, { 12, 'g' } };

    for ( auto p : s )
        std::cout << p.first << ", " << p.second << std::endl;

    return 1;
}

how to create an ordered set using two ordering criteria(for a set of pairs) in c++?

4 Answers4