classes containing operator() for std::sort, and virtual functions

[Markus Dehmann]

In the following code example, I define several Comparator classes
which contain different compare functions to use with std::sort. I
have a Sorter class that gets passed a Comparator and is supposed to
sort using the specific Comparator that's passed to it.

But it always uses the Comparator base class and not the derived class
that it is supposed to use, although the functions are virtual.

How can I make the code work? You might argue that a Sorter class is
not needed, but I want one because I have more data and operations
related to sorting that I would like to put there.

#include <iostream>
#include <vector>

class Comparator {
public:
virtual bool operator() (const int& i1, const int& i2) const {
return i1 < i2;
}
};

// would like to make it abstract base class, but that doesn't compile
class ReverseComparator : public Comparator {
public:
virtual bool operator() (const int& i1, const int& i2) const {
return i2 < i1;
};
};

class Sorter {
public:
Sorter(std::vector<int>& v, Comparator& c){
sort(v.begin(), v.end(), c);
}
};

int main(int argc, char** argv){
std::vector<int> v;
v.push_back(3);
v.push_back(1);
v.push_back(2);
ReverseComparator c;
Sorter s(v, c);
for(std::vector<int>::const_iterator it = v.begin(); it != v.end(); +
+it){
std::cout << *it << std::endl; // prints 1,2,3, instead of 3,2,1
}
return EXIT_SUCCESS;
}

 

[James Kanze]

In the following code example, I define several Comparator
classes which contain different compare functions to use with
std::sort. I have a Sorter class that gets passed a Comparator
and is supposed to sort using the specific Comparator that's
passed to it.

But it always uses the Comparator base class and not the
derived class that it is supposed to use, although the
functions are virtual.

The standard library uses value semantics for its agents. Which
means slicing, and no virtual functions.

How can I make the code work?

You need an additional level of indirection. Perhaps the
letter/envelop idiom.

You might argue that a Sorter class is not needed, but I want
one because I have more data and operations related to sorting
that I would like to put there.

#include <iostream>
#include <vector>

class Comparator {
public:
virtual bool operator() (const int& i1, const int& i2) const {
return i1 < i2;
}
};

// would like to make it abstract base class, but that doesn't compile
class ReverseComparator : public Comparator {
public:
virtual bool operator() (const int& i1, const int& i2) const {
return i2 < i1;
};
};

class Sorter {
public:
Sorter(std::vector<int>& v, Comparator& c){
sort(v.begin(), v.end(), c);

Here's the problem line. std::sort is a template. Template
type deduction uses the static type. (It could hardly use
anything else, since it must be resolved at compile time.) So
the type of the comparison object here is Comparator. std::sort
takes its argument by value, copying the argument you give it
into a value parameter. Of type Comparator, so slicing occurs.

There are several solutions, but first: I'd recommend making
base classes abstract whenever possible, just to catch this sort
of thing. Rather than implementing the function in Comparitor,
make it pure virtual, and provide a derived class with the
default implementation. If Comparitor is abstract here, you'll
get all sorts of nasty messages from the compiler, rather than a
sort program with different semantics than those you wanted.

The simplest work around would be to define a simple wrapper for
a pointer to a Comparator, which forwards the operator()() to
the pointed to object. Alternatively, the letter/envelop idiom
is the classical way of combining value semantics with
polymorphism (but it may be more than what is needed here).