Problems with STL sorting using member functions

[Nelis Franken]

Good day.

I'm having trouble telling STL to use a member function to sort items
within the relevant class. The isLess() function needs to have access
to the private members of the Foo class to determine if the one item is
less than the other (it uses two vectors, one containing the actual
data, and one that stores IDs that index into the data vector). The
code below is pretty self-explanatory. I've looked into mem_fun, but
I'm stuck. The same general error seems to occur if I use other
<algorithm> algorithms ("find_if" etc), so it's not something specific
to STL's "sort", but rather on how to let it use the member function
correctly.

I'm using g++ (GCC) 3.4.4 (cygming special), and the error (if you were
to compile the code below) is:

In member function `void Foo::mySort()':
error: no matching function for call to
`sort(__gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*,
std::vector<int, std::allocator<int> > >, <unknown type>)'
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2576:
note: candidates are: void std::sort(_RandomAccessIterator,
_RandomAccessIterator, _Compare) [with _RandomAccessIterator =

, _Compare = bool (Foo::*)(int, int)]

If I rewrite:
sort(idList.begin(), idList.end(), isLess)

to read:
sort(idList.begin(), idList.end(), &Foo::isLess)

a long list of STL files (only stl_algo.h reproduced here) report the
following error:
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:124:
error: must use .* or ->* to call pointer-to-member function in `__comp
(...)'

Any help will be greatly appreciated.

Thanks!


#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

class Foo {

public:

Foo() {

for (int i=0; i < 5; i++) {
myList.push_back(i*10);
idList.push_back(i);
}

random_shuffle(myList.begin(), myList.end());
}

bool isLess(int leftID, int rightID) {
return (myList[leftID] < myList[rightID]);
}

void mySort() {
sort(idList.begin(), idList.end(), isLess);
}

private:
vector<int> myList;
vector<int> idList;

};

int main(int argc, char** argv) {

Foo myObj;
myObj.mySort();

return 0;
}

 

[Jens Theisen]

Good day.

I'm having trouble telling STL to use a member function to sort items
within the relevant class. The isLess() function needs to have access
to the private members of the Foo class to determine if the one item is
less than the other (it uses two vectors, one containing the actual
data, and one that stores IDs that index into the data vector). The
code below is pretty self-explanatory. I've looked into mem_fun, but
I'm stuck. The same general error seems to occur if I use other
<algorithm> algorithms ("find_if" etc), so it's not something specific
to STL's "sort", but rather on how to let it use the member function
correctly.

STL is not your friend in this case, because you can't make a binary
member function to a ternary free function with it's means. So unless
you want to use boost, it's a specialised nested functor:

struct IsLess
{
IsLess(Foo const& self_)
: self(self_) { }

bool operator () (int leftID, int rightID) const {
return self.myList[leftID] < self.myList[rightID];
}

Foo const& self;
};

void mySort() {
sort(idList.begin(), idList.end(), IsLess(*this));
}

In boost, there some alternatives:

#include <boost/bind.hpp>

void mySort() {
sort(idList.begin(), idList.end(),
bind(&Foo::isLess, this, _1, _2));
}

or very similar the boost lambda library:

#include <boost/lambda/bind.hpp>

namespace bl = boost::lambda;

void mySort() {
sort(idList.begin(), idList.end(),
bind(&Foo::isLess, this, bl::_1, bl::_2));
}

or even without isLess:

void mySort() {
sort(idList.begin(), idList.end(),
bl::var(myList)[bl::_1] < bl::var(myList)[bl::_2]);
}

then

for_each(idList.begin(), idList.end(), cout << bl::_1);

prints

42310

The var in the more advanced use of boost::lambda is necessary to make
the compiler take boost::lambda's subscript operator rather than
std::vector's one. This is not an issue with most of the binary operators.

Jens

 

[Nelis Franken]

Thanks Jens!

Good day.

I'm having trouble telling STL to use a member function to sort items
within the relevant class. The isLess() function needs to have access
to the private members of the Foo class to determine if the one item is
less than the other (it uses two vectors, one containing the actual
data, and one that stores IDs that index into the data vector). The
code below is pretty self-explanatory. I've looked into mem_fun, but
I'm stuck. The same general error seems to occur if I use other
<algorithm> algorithms ("find_if" etc), so it's not something specific
to STL's "sort", but rather on how to let it use the member function
correctly.

STL is not your friend in this case, because you can't make a binary
member function to a ternary free function with it's means. So unless
you want to use boost, it's a specialised nested functor:

struct IsLess
{
IsLess(Foo const& self_)
: self(self_) { }

bool operator () (int leftID, int rightID) const {
return self.myList[leftID] < self.myList[rightID];
}

Foo const& self;
};

void mySort() {
sort(idList.begin(), idList.end(), IsLess(*this));
}

In boost, there some alternatives:

#include <boost/bind.hpp>

void mySort() {
sort(idList.begin(), idList.end(),
bind(&Foo::isLess, this, _1, _2));
}

or very similar the boost lambda library:

#include <boost/lambda/bind.hpp>

namespace bl = boost::lambda;

void mySort() {
sort(idList.begin(), idList.end(),
bind(&Foo::isLess, this, bl::_1, bl::_2));
}

or even without isLess:

void mySort() {
sort(idList.begin(), idList.end(),
bl::var(myList)[bl::_1] < bl::var(myList)[bl::_2]);
}

then

for_each(idList.begin(), idList.end(), cout << bl::_1);

prints

42310

The var in the more advanced use of boost::lambda is necessary to make
the compiler take boost::lambda's subscript operator rather than
std::vector's one. This is not an issue with most of the binary operators.

Jens

 

[Victor Bazarov]

I'm having trouble telling STL to use a member function to sort items
within the relevant class. The isLess() function needs to have access
to the private members of the Foo class to determine if the one item
is less than the other (it uses two vectors, one containing the actual
data, and one that stores IDs that index into the data vector). [..]

You're trying to use non-static member function as a callback, essentially.
That's impossible. You need to use binders and mem_fun, but the problem is
that the standard mem_fun adapters do not adapt functions with more than
one argument. So, you could try a static function and pass the pointer to
your 'Foo' as its first argument, but then you have a function with three
arguments and standard binders don't work with functions with more than
two arguments.

Your solution is either use 'Boost's binders, or roll your own, or create
a "proxy" comparator, which will hold a reference to your 'Foo' object and
use it in its operator():

class Foo {
...
class ProxyLess {
Foo& that;
public:
ProxyLess(Foo& f) : that(f) {}
bool operator()(int leftID, int rightID) const {
return (that.myList[leftID] < that.myList[rightID]);
}
};

void mySort() {
sort(idList.begin(), idList.end(), ProxyLess(*this));
}
...
};

Also, naming your member 'List' and instead implement it using a vector
is misleading, considering that there is a standard 'list' template,
which you cannot sort using 'std::sort' function. Just an observation.

V