std::sort (AGAIN)

[none]

Hi,

I know that std::sort() is a frequent topic here, and I know it is covered
multiple times in the FAQ, but I can't find the answer to something that
should be simple. It was trivial in C using qsort(), at least, but I got
the crazy idea in my head that it would be a good idea to start using STL.

I want to sort a vector of structs. The catch is that the user can select
which fields in the struct are used for the sort. That alone I can do, but
what I can't do is make it work with member functions. From what I can
gather in the FAQ, there are a few possibilities:

1. Make the compare function static. I can't do this because the
comparison is dependent on what the user selected. In other words, the
compare function must access private members of the class doing the sort.

2. Create a global instance of the class and a wrapper function that calls
the compare member, then pass that wrapper function to std::sort(). I
can't do this because I need the *actual* object to sort its own data, not
some generic global object. I might even have multiple objects doing sorts
and they each might select different options so that they each perform the
sort differently.

3. Use a functor. This is ugly and hacky and I admit that I don't really
get it. But looking at examples of functors, I don't understand how the
function could access the internals of the class doing the sorting.

 

[red floyd]

Hi,

I know that std::sort() is a frequent topic here, and I know it is covered
multiple times in the FAQ, but I can't find the answer to something that
should be simple. It was trivial in C using qsort(), at least, but I got
the crazy idea in my head that it would be a good idea to start using STL.

I want to sort a vector of structs. The catch is that the user can select
which fields in the struct are used for the sort. That alone I can do, but
what I can't do is make it work with member functions. From what I can
gather in the FAQ, there are a few possibilities:

1. Make the compare function static. I can't do this because the
comparison is dependent on what the user selected. In other words, the
compare function must access private members of the class doing the sort.

2. Create a global instance of the class and a wrapper function that calls
the compare member, then pass that wrapper function to std::sort(). I
can't do this because I need the *actual* object to sort its own data, not
some generic global object. I might even have multiple objects doing sorts
and they each might select different options so that they each perform the
sort differently.

3. Use a functor. This is ugly and hacky and I admit that I don't really
get it. But looking at examples of functors, I don't understand how the
function could access the internals of the class doing the sorting.

Look up mem_fun_ref

 

[Alf P. Steinbach]

* none:

Hi,

I know that std::sort() is a frequent topic here, and I know it is covered
multiple times in the FAQ, but I can't find the answer to something that
should be simple. It was trivial in C using qsort(), at least, but I got
the crazy idea in my head that it would be a good idea to start using STL.

I want to sort a vector of structs. The catch is that the user can select
which fields in the struct are used for the sort. That alone I can do, but
what I can't do is make it work with member functions. From what I can
gather in the FAQ, there are a few possibilities:

1. Make the compare function static. I can't do this because the
comparison is dependent on what the user selected. In other words, the
compare function must access private members of the class doing the sort.

2. Create a global instance of the class and a wrapper function that calls
the compare member, then pass that wrapper function to std::sort(). I
can't do this because I need the *actual* object to sort its own data, not
some generic global object. I might even have multiple objects doing sorts
and they each might select different options so that they each perform the
sort differently.

3. Use a functor. This is ugly and hacky and I admit that I don't really
get it. But looking at examples of functors, I don't understand how the
function could access the internals of the class doing the sorting.

How about illustrating your problem with some code.

Cheers & hth.,

- Alf

 

[Marcel Müller]

3. Use a functor. This is ugly and hacky and I admit that I don't really
get it. But looking at examples of functors, I don't understand how the
function could access the internals of the class doing the sorting.

This is your favorite choice. You can do this either yourself


class mycomparer
{ SortCriterion Sort;
public:
mycomparer(SortCriterion sort) : Sort(sort) {}
bool operator()(const mystruct& x, const mystruct& y)
{ // compare x and y according to Sort ...
}
};

vector<mystruct> data;
SortCriterion sortcriterion;
// ...
std::sort(data.begin(), data.end(), mycomparer(sortcriterion));

or you might use a function adaptor. A function adaptor binds an
additional, constant parameter to a existing function or functor
returning a functor with one argument less than the original function.
This enables std::sort to call a custom function with 3 parameters while
std::sort passes only two of them and the third one is your sort criterion.


Of course, you could also write a template comparer function which takes
a functor to an element getter as template argument.

template<class E>
bool mycompare(const mystruct& x, const mystruct& y)
{ return E(x) < E(y);
};

const comptype1& getcomp1(const mystruct& s)
{ return s.comp1;
}
....

std::sort(data.begin(), data.end(), mycompare<&getcomp1>);


The latter solution is the faster one, because the sort criterion is not
checked for each comparsion.


Marcel

 

[none]

I hit "send" a little prematurely on that first post.

Here is the member function that I am trying (and failing) to pass to
std::sort().

// Sort options, defined in the class header
enum sort_options
{
sort_by_last_name,
sort_by_first_name,
sort_by_age,
sort_by_city,
sort_by_state,
sort_by_phone,
// ...
};


// Compare function defined in the class cpp file
bool my_class::sort_func(const my_struct &a,
const my_struct &b)
{
// Loop over all the selected fields until a case is found where
// a.x != b.x, then do the comparison on that field
for (int i = 0; i < NUM_SORT_FIELDS; i++)
{
// m_sort_parameters is the array of options selected by the
// user for this sort, with element [0] being highest priority
switch (m_sort_parameters)
{
case (sort_by_name):

if (a.name != b.name)
{
// "last_name" is a std::string so use compare()
return a.last_name.compare(b.last_name) < 0;
}

break;

case (sort_by_age):

if (a.age != b.age)
{
// "age" is just an int
return a.age < b.age;
}

break;

// more cases ...
}
}

// The two structs are equal in all selected fields
return false;
}

 

[Juha Nieminen]

It was trivial in C using qsort()

I don't understand what stops you from doing it similarly in C++.
qsort() takes a comparator function as parameter, and std::sort() takes
a comparator function as parameter. So what's the problem? Just do it
like you would do it with qsort(), if you find that trivial.

The only basic difference between the comparator taken by qsort() and
the one taken by std::sort() is that the former has the form:

int functionName(const void*, const void*);

while the latter has the form:

bool functionName(const YourType&, const YourType&);

 

[Juha Nieminen]

1. Make the compare function static. I can't do this because the
comparison is dependent on what the user selected. In other words, the
compare function must access private members of the class doing the sort.

A static member function can access the private members of the class
it belongs to. What is the problem?

 

[SG]

I want to sort a vector of structs.  The catch is that the user can select
which fields in the struct are used for the sort.  That alone I can do, but
what I can't do is make it work with member functions.  From what I can
gather in the FAQ, there are a few possibilities:

As Juha wrote you can simply use pointers to a functions like

bool cmp_first_name(YourType const& a, YourType const& b);

In case you really want to sort "structs" (with public members) you
can do something like this:

template<typename S, typename C>
class member_comparator {
S C::*pm;
public:
explicit member_comparator(S C::*p) : pm(p) {}

bool operator()(C const& a, C const& b) const
{return a.*pm < b.*pm;}
};

template<typename S, typename C>
member_comparator<S,C> make_memcmp(S C::*p) {
return member_comparator<S,C>(p);
}

...

void foo(std::vector<YourType> & vec) {
std::sort(vec.begin(), vec.end(),
make_memcmp(&YourType::first_name));
}

provided that YourType has a public member called first_name that is
comparable.

Another thing: If you don't provide your own swap function for
YourType the sort algorithm will fall back on an unspecialized
std::sort which might be slower than necessary. In case your struct
contains objects of type std::string or some other members that swap
quickly but copy slowly you should supply your own swap function.

struct YourType {
std::string first_name;
std::string last_name;
int age;

void swap(YourType & x);
};

void YourType::swap(YourType & x) {
// string::swap is FAST
first_name.swap(x.first_name);
last_name.swap(x.last_name);
std::swap(age,x.age);
}

// non-templated swap, can be found via ADL
inline swap(YourType & a, YourType & b) {a.swap(b);}

// specialization of std::swap to be on the safe side.
namespace std {
template<> swap<YourType>(YourType & a, YourType & b)
{a.swap(b);}
}

hth,
SG

 

[SG]

Here is the member function that I am trying (and failing) to pass to
std::sort().

Oh! Sorry, I didn't read that "member function" bit.

// Sort options, defined in the class header
enum sort_options
{
   sort_by_last_name,
   sort_by_first_name,
   sort_by_age,
   sort_by_city,
   sort_by_state,
   sort_by_phone,
   // ...

};

// Compare function defined in the class cpp file
bool my_class::sort_func(const my_struct &a,
                         const my_struct &b)
{
    // Loop over all the selected fields until a case is found where
    // a.x != b.x, then do the comparison on that field
    for (int i = 0; i < NUM_SORT_FIELDS; i++)
    {
        // m_sort_parameters is the array of options selected by the
        // user for this sort, with element [0] being highest priority
        switch (m_sort_parameters)
        {
        case (sort_by_name):

            if (a.name != b.name)
            {
                // "last_name" is a std::string so use compare()
                return a.last_name.compare(b.last_name) < 0;
            }

            break;

        case (sort_by_age):

            if (a.age != b.age)
            {
                // "age" is just an int
                return a.age < b.age;
            }

            break;

        // more cases ...
        }
    }

    // The two structs are equal in all selected fields
    return false;

}

It's not clear whether this is supposed to be a static or non-static
member function. You're accessing some array called m_sort_parameters
which could be a global array or a member of my_class objects.

In case this is a static member function you could simply use a normal
function pointer as comparator. However, using "global state" is
usually considered bad. You should package the sort parameters inside
a functor.

In case this is a non-static member and m_sort_parameters is a member
of *this you risk having an inconsistent order. The sort parameters
should not be part of the elements.

Cheers!
SG

 

[none]

It's not clear whether this is supposed to be a static or non-static
member function. You're accessing some array called m_sort_parameters
which could be a global array or a member of my_class objects.

Yes, m_sort_parameters is a member of "my_class." And this is why I have a
problem. I don't want to make m_sort_parameters global, because there may
be multiple instances (objects) of my_class.

In case this is a non-static member and m_sort_parameters is a member
of *this you risk having an inconsistent order. The sort parameters
should not be part of the elements.

This is exactly the case. So what is the safe, "STL-style" solution?
Maybe I can make the problem more simple:

1) I have a class that contains a vector (of unspecified things).
2) This same class contains member variables that determine how to sort
those things.
3) I want to call std::sort to sort that vector.

So how do I get information from one particular instance (object) of my
class into std::sort so that it can sort the vector correctly?

I'm sure the answer is here in this thread, but I'm dense. I think that I
failed to state the problem clearly.

 

[none]

A static member function can access the private members of the class
it belongs to. What is the problem?

I thought static meant that the function could not access non-static
members of the class. I get compile errors when I try. In fact, I thought
that you could call static members without even declaring an instance of
the class, meaning that those non-static members would not exist. Do you
mean that a static member function can access static members of the class?
I need to be able to do this:

my_class x;
my_class y;
my_class z;

x.set_sort_parameter1(sort_by_last_name);
x.set_sort_paramerer2(sort_by_first_name);

y.set_sort_parameter1(sort_by_state);
y.set_sort_paramerer2(sort_by_city);

z.set_sort_parameter1(sort_by_age);
z.set_sort_paramerer2(sort_by_phone);

x.do_sort();
y.do_sort();
z.do_sort();

And x, y, z may be in different threads, etc.

 

[Bart van Ingen Schenau]

Yes, m_sort_parameters is a member of "my_class." And this is why I
have a
problem. I don't want to make m_sort_parameters global, because there
may be multiple instances (objects) of my_class.



This is exactly the case. So what is the safe, "STL-style" solution?

red floyd already gave a hint for the direction of the solution.
Unfortunately, the standard does not provide the right tools to help
you, but fortunately Boost does.

The trick is to turn your three-parameter member-function (don't forget
the implicit *this) into the binary function that std::sort expects.
This is where boost::bind comes in handy:
std::sort(vec.begin(), vec.end(), boost::bind(&my_class::sort_func,
this, _1, _2));

Maybe I can make the problem more simple:

1) I have a class that contains a vector (of unspecified things).
2) This same class contains member variables that determine how to
sort those things.
3) I want to call std::sort to sort that vector.

So how do I get information from one particular instance (object) of
my class into std::sort so that it can sort the vector correctly?

I'm sure the answer is here in this thread, but I'm dense. I think
that I failed to state the problem clearly.

Bart v Ingen Schenau

 

[SG]

Yes, m_sort_parameters is a member of "my_class."  And this is why I have a
problem.  I don't want to make m_sort_parameters global, because there may
be multiple instances (objects) of my_class.


This is exactly the case.  So what is the safe, "STL-style" solution?  
Maybe I can make the problem more simple:

Write a special class for these "sort parameters", move your
comparison function from my_class to this comparator class, and use an
object as last parameter for std::sort.

You might want to consider replacing the switch with a form of runtime
polymorphism. (i.e. keep a list of function pointers instead an array
of enums).

Cheers!
SG

 

[Juha Nieminen]

I thought static meant that the function could not access non-static
members of the class.

Of course it can, and making a static comparator function for
std::sort is one of the best examples.

For example:

class A
{
int i;

public:
static bool comparator(const A& lhs, const A& rhs)
{
return lhs.i < rhs.i;
}
};

Then you can call: std::sort(begin, end, A::comparator);

 

[none]

Of course it can, and making a static comparator function for
std::sort is one of the best examples.

For example:

class A
{
int i;

public:
static bool comparator(const A& lhs, const A& rhs)
{
return lhs.i < rhs.i;
}
};

Ah, now I understand the source of the confusion. I'm not sorting
objects of class "A". So the type passed into "comparator()" is not
"const A&".

The type being sorted is not the same as the type (class) doing the
sorting. In other words, to expand on your example, this is illegal:

class B
{
int x;
int y;
};

class A
{
bool z;

public:
static bool comparator(const B& lhs, const BA& rhs)
{
return z ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
}
};

But that is what I really want to do. I think that Bart, SG, and floyd
have provided the answer, but I'm not thrilled about it. I find
Boost to be a little bloated.

The fact that what I want to do is not supported directly by std::sort()
makes me think that my approach is probably just bad from the start.
How would you guys approach the problem? I just have a bunch of data
that I want to sort, but I want to sort it based on multiple user-
selected fields. If you've ever used a spreadsheet, you've probably
seen a dialog for sorting that looks something like this:

Sort first by:
[ COLUMN C ]

Then by:
[ COLUMN F ]

Then by:
[ COLUMN Q ]

That's all I'm looking for.

 

[SG]

The type being sorted is not the same as the type (class) doing the
sorting.  In other words, to expand on your example, this is illegal:

   class B
   {
      int x;
      int y;
   };

   class A
   {
      bool z;

      public:
         static bool comparator(const B& lhs, const BA& rhs)
         {
             return z ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
         }
   };

Pretty much yes. Because of two reasons:

(1) x and y are private members of B you can't access from
the function "comparator".
(2) z is a non-static member of A so "comparator" cannot be a
static member function. A static member has no implicit
this-pointer. (!)

But that is what I really want to do.  I think that Bart, SG, and floyd
have provided the answer, but I'm not thrilled about it.    I find
Boost to be a little bloated.

The fact that what I want to do is not supported directly by std::sort()
makes me think that my approach is probably just bad from the start.  
How would you guys approach the problem?

I already answered that. The key here is to use a comparator that
has a "state" (parameters). std::sort supports more than pure function
pointers. It also accepts objects with overloaded function call
operator. Here is a non-generic example:

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

struct entry {
std::string name;
int age;
explicit entry(std::string n, int a) : name(n), age(a) {}
};

bool comp_name(entry const& a, entry const& b)
{return a.name < b.name;}

bool comp_age(entry const& a, entry const& b)
{return a.age < b.age;}

class multi_compare {
public:
// declared comp_t to be a function pointer type
typedef bool (*comp_t)(entry const&, entry const&);

multi_compare(comp_t pf1, comp_t pf2)
{c[0] = pf1; c[1] = pf2;}

bool operator()(entry const& a, entry const& b) const {
for (int i=0; i<2; ++i) {
comp_t pf = c;
if (pf==0) break;
if (pf(a,b)) return true;
if (pf(b,a)) return false;
}
return false;
}
private:
comp_t c[2];
};

int main() {
std::vector<entry> vec;
vec.push_back(entry("Jack",43));
vec.push_back(entry("Hugo",33));
vec.push_back(entry("Kate",29));
std::sort(vec.begin(), vec.end(),
multi_compare(comp_name,comp_age) );
for (int idx=0, n=vec.size(); idx<n; ++idx) {
entry const& e = vec.at(idx);
std::cout << e.name << " is " << e.age << " years old.\n";
}
}

Cheers!
SG

 

[SG]

  struct entry {
    std::string name;
    int age;
    explicit entry(std::string n, int a) : name(n), age(a) {}
  };

I forgot to add a custom swap function. Otherwise std::sort will fall
back on an unspecialized std::swap algorithm that copies strings
around which might be less efficient.

void swap(entry & a, entry & b) {
a.name.swap(b.name); // use special string swap
std::swap(a.age, b.age); // default swap
}

namespace std {
// specializing std::swap to be on the safe side
template<>
void swap<entry>(entry & a, entry & b)
{::swap(a,b);}
}

Cheers!
SG

 

[none]

I already answered that. The key here is to use a comparator that
has a "state" (parameters). std::sort supports more than pure function
pointers. It also accepts objects with overloaded function call
operator.

Ah, I see! I was misunderstanding the suggestion. Your example makes it
very clear. It is an elegant solition. Many thanks!

 

[Juha Nieminen]

The type being sorted is not the same as the type (class) doing the
sorting. In other words, to expand on your example, this is illegal:

class B
{
int x;
int y;
};

class A
{
bool z;

public:
static bool comparator(const B& lhs, const BA& rhs)
{
return z ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
}
};

Not being able to access x and y from outside B is a question of
design. You have declared them private, so you are explicitly saying
that they cannot be accessed from the outside. If you want to access
them from the outside, you'll have to change your design. (One
possibility is to make A a friend of B, although whether this is a good
design depends on the situation.)

As for a comparator with a state (which is what you want with that A
class), the operator() has been designed for this exact purpose. It
makes objects of the class behave like functions with an internal state.
In other words:

class A
{
bool z;

public:
A(bool iz): z(iz) {}

bool operator()(const B& lhs, const B& rhs) const
{
return z ? whatever;
}
};

Instances of A will now behave like a function taking two references
to B and returning a bool. Like for example:

A a(true);
bool b = a(b1, b2);

Now you can give an instance of A as a comparator to std::sort. Such
instance will behave like a function, but will have an internal state.
Example:

std::sort(begin, end, A(true));