std::pair with a comparable and a non-comparable object needs to be sorted

Question

I've come across with the following problem. I have a std::vector< std::pair<int, Move> > x of type std::pair<int, Move> where Move is an arbitrary object not having any comparison operator defined, for example < > !+ == <= >= and so on.

The main reason why I paired the Move objects with a integer values is that the Move objects should have a number describing their priority for some purpose. The main intention is to sort the vector thus sorting Move objects using their respective integer values.

Real problem begins when I want to sort these pairs in the vector using std::sort function. Initially I thought that only first element of std::pair mattered for comparison, however, it turned out to be that both objects need comparison operations defined for them for the program to be successfully compiled.

Since I did not want to modify original Move class, I wrote a Wrapper class that was supposed to wrap std::pair<int, Move> and have a comparison operation defined on it so that a std::vector< Wrapper < std::pair<int, Move> > > x; could be sorted without having to modify Move class. The logic here is that vector is provided with a class that has < operation defined.

I have used the below wrapper class:

template <typename T>
struct Wrapper{
    Wrapper(const T & pair): pair_mem(pair)
    bool operator(const T & other_pair) const{
          return this->pair_mem.first < other_pair.first;
    }
    T pair_mem;
};

Well, as you may have already guessed the approach above did not work and I had to go through bunch of compiler errors. At last, I tried adding < operator to the Move class and even after that I was not able to compile the program.

Below is the error I think is the most important.

: note: this candidate was rejected because mismatch in count of arguments
    struct Wraper{
           ^
: note: this candidate was rejected because mismatch in count of arguments
            Wraper(const std::pair<int, Move> & move){

I am using mpiCC as the compiler

UPDATE

I did change T to Wrapper as one of the answers suggested, but the problem is not solved. Here is the screenshot from the compiler,

Have you considered using a `std::map`? It lets you build a key-value relationship that is automatically sorted. — NathanOliver, Jun 26 '18 at 21:47
I am actually more interested in the reason why I was not able to get it compiled. — nmd_07, Jun 26 '18 at 21:49
Can you show how you used wrapper to get that error then ([mcve])? Looks like [this](https://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects) might show you what you need. — NathanOliver, Jun 26 '18 at 21:52
`std::vector< Wrapper < std::pair > > x;` is the source of the compile error. `Wrapper` is a class that has comparison defined on it. And it takes `std::pair` — nmd_07, Jun 26 '18 at 21:56

Jarod42 · Accepted Answer · 2018-06-28T08:40:12.867

3

Your wrapper class should be similar to:

template <typename T>
struct Wrapper{
    Wrapper(const T & pair): pair_mem(pair) {}
    bool operator <(const Wrapper& rhs) const {
        return pair_mem.first < rhs.pair_mem.first;
    }
    T pair_mem;
};

Demo

But using custom comparer seems better (less intrusive).

std::sort(x.begin(), x.end(),
          [](const auto& lhs, const auto& rhs) {
              return lhs.first < rhs.first;
          });

edited Jun 28 '18 at 08:40

answered Jun 26 '18 at 22:01

Jarod42

203,559
14
181
302

I actually made the operator overload operation `const`but forgot to include it here. Did not help though. – nmd_07 Jun 26 '18 at 22:02
3

@nmd_07 The comparison parameter is a `Wrapper`, not a `T`. – 1201ProgramAlarm Jun 26 '18 at 22:06
@1201ProgramAlarm Seems like the real reason. – nmd_07 Jun 26 '18 at 22:08
You can use something similar to Barton-Nackman trick. Using friend, you may be able to inject the comparison operator at global scope. – Michael Doubez Jun 27 '18 at 21:18
1

@nmd_07: I have just provided a [Demo link](https://ideone.com/uGvSzn). – Jarod42 Jun 28 '18 at 08:41

score 1 · Answer 2 · answered Jun 26 '18 at 21:53

1

If you are using a c++ compiler recent enough, you can use lambda:

std::sort(std::begin(x), std::end(x), [](auto & l, auto & r) {return l.first < r.first; });

answered Jun 26 '18 at 21:53

Michael Doubez

5,937
25
39

JaMiT · Answer 3 · 2018-06-27T00:50:09.583

When the compiler spits out errors, do not skip the first message. From your image (you really should have copied the text instead of creating an image):

error: no instance of constructor Wraper<T>::Wraper matches the argument list vector(size_type __n, const value_type& __value = value_type()

With the error indicated (by the caret on the next line) as occurring at value_type(). The messages you did put into your question are not errors, but explanations for what the compiler tried to do to find the missing constructor. They list the struct that was tried for value_type and the constructor that was found, the one that takes a T parameter. This does not match because the compiler is looking for a default constructor (no parameters).

Presumably, at line 137 of search-abid_parallel.cpp, you declare a vector of your wrapper class using the constructor that specifies the initial size of the vector. (Also, based on the error message, pre-C++11?) This constructor needs to be able to default-construct those initial elements. The default constructor was suppressed when you defined a different constructor, hence the error.

Some options:

Default initialize the vector, then call reserve() if you want to avoid re-allocations as you build your vector.
Define a default constructor for your wrapper class.
Don't use a wrapper class. Instead, give a comparison function to std::sort (the third parameter when not using a C++20 execution policy).
Don't use a vector. A std::multimap will store your pairs and keep them sorted for you.

std::pair with a comparable and a non-comparable object needs to be sorted

UPDATE

3 Answers3