 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
jean Davy
Guest
|
 Posted: Mon Dec 15, 2003 10:31 am Post subject: sort through multiple key with STL |
 |
|
Say I have a struct like this
struct PERSON
{
int Age;
float Salary;
string Name;
};
given a container of PERSON, what is the "easiest " way of sorting these
through the struct members.
I code like this:
bool sort_by_Age( const PERSON& Left, const PERSON& Right )
{
return Left.Age < Right.Age );
}
bool sort_by_Salary( const PERSON& Left, const PERSON& Right )
{
return Left.Salary < Right.Salary );
}
bool sort_by_Age_Salary( const PERSON& Left, const PERSON& Right )
{
if( Left.Age == Right.Age )
return sort_by_Salary( Left, Right );
return Left.Age < Right.Age );
}
vector < PERSON > Array;
sort( Array.begin(), A.end(), sort_by_Age_Salary );
I feel that I could do better with some "mem_fun_ref" and "adjacent_find",
but I waste time on this, having the impression of "reinventing" the
wheel...
Any suggestion, help, appreciated...
Regards,
jean Davy
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Francis Glassborow
Guest
|
| Posted: Mon Dec 15, 2003 3:49 pm Post subject: Re: sort through multiple key with STL |
|
|
In article <brjvev$rcl$1 (AT) s1 (DOT) read.news.oleane.net>, jean Davy
<nospam (AT) unspam (DOT) com> writes
Please break the habit of using names without lowercase letters because
many programmers reserve such all uppercase names for use by the
pre-processor.
| Quote: | {
int Age;
float Salary;
string Name;
};
given a container of PERSON, what is the "easiest " way of sorting these
through the struct members.
I code like this:
bool sort_by_Age( const PERSON& Left, const PERSON& Right )
Bad function name because it does not sort anything try compare_by_age |
instead. In addition most style guides would advocate all lowercase for
parameter names.
| Quote: | {
return Left.Age < Right.Age );
}
bool sort_by_Salary( const PERSON& Left, const PERSON& Right )
as above
{
return Left.Salary < Right.Salary );
}
bool sort_by_Age_Salary( const PERSON& Left, const PERSON& Right )
{
if( Left.Age == Right.Age )
return sort_by_Salary( Left, Right );
return Left.Age < Right.Age );
}
|
The trouble with this approach is that it creates an explosion of
comparison functions.
| Quote: | vector < PERSON > Array;
assuming you have actually placed code that intialises Array (another |
poor name, usually suggestive of use of a raw C-type array)
| Quote: | sort( Array.begin(), A.end(), sort_by_Age_Salary );
|
Consider:
sort(Array.begin(), Array.end(), compare_by_sallary);
stable_sort(Array.begin(), Array.end(), compare_by_age);
The advantage of this approach is that it allows you to compose sorts by
multiple fields as you want. Approaches such as yours are attempts to
optimise and break the first rule of optimisation (Don't)
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
or http://www.robinton.demon.co.uk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dan McLeran
Guest
|
| Posted: Tue Dec 16, 2003 10:53 am Post subject: Re: sort through multiple key with STL |
|
|
| Quote: | I feel that I could do better with some "mem_fun_ref" and "adjacent_find",
but I waste time on this, having the impression of "reinventing" the
wheel...
Any suggestion, help, appreciated...
|
I have a suggestion, although it's not very elegant yet. I've added
methods to your Person struct to make this work, don't know if this is
acceptable or not. Also, this template requires the functor type and
class type that contains the methods you wish to call. There is a way
to eliminate the 2nd template parameter but I don't have alot of time
to spend messing with it.
To sort by age, you pass a pair of functors that point to Person::Age,
to sort by weight you pass a pair of functors that point to
Person::Weight, etc.
This is not as elegant as I would like but give it a shot. You can
probably get this to work with MSVC6SP5 if you use the portable syntax
for boost::function.
First, I modified your Person struct by adding methods to return
weight and age:
struct Person
{
std::string name;
int age;
float weight;
const float Weight() const
{
return weight;
}
const int Age() const
{
return age;
}
};
I then wrote this template:
template<typename FunctorType,typename ArgumentType>
struct FunctorCallLess : std::binary_function<bool,ArgumentType
const&,ArgumentType const&>
{
FunctorCallLess(FunctorType const& f1,FunctorType const& f2) :
f1_(f1),f2_(f2){}
bool operator() (ArgumentType const& arg1,ArgumentType const& arg2)
{
return (f1_(&arg1) < f2_(&arg2));
}
private:
FunctorType const& f1_;
FunctorType const& f2_;
};
It basically calls operator < for each pair of elements of a container
of Person(s). You pass the functor type, i.e. which Person method to
call. Here is the complete project (I used MinGW Developer Studio
2.04):
#include
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <boost/function.hpp>
struct Person
{
std::string name;
int age;
float weight;
const float Weight() const
{
return weight;
}
const int Age() const
{
return age;
}
};
template<typename FunctorType,typename ArgumentType>
struct FunctorCallLess : std::binary_function<bool,ArgumentType
const&,ArgumentType const&>
{
FunctorCallLess(FunctorType const& f1,FunctorType const& f2) :
f1_(f1),f2_(f2){}
bool operator() (ArgumentType const& arg1,ArgumentType const& arg2)
{
return (f1_(&arg1) < f2_(&arg2));
}
private:
FunctorType const& f1_;
FunctorType const& f2_;
};
int main()
{
using namespace std;
typedef boost::function
typedef boost::function<const int (const Person*)> AgeFnType;
WeightFnType f1 = &Person::Weight;
WeightFnType f2 = &Person::Weight;
AgeFnType f3 = &Person::Age;
AgeFnType f4 = &Person::Age;
vector<Person> v;
Person p1;
Person p2;
Person p3;
p1.name = "a";
p2.name = "b";
p3.name = "c";
p1.age = 21;
p2.age = 25;
p3.age = 22;
p1.weight = 191.5;
p2.weight = 190.5;
p3.weight = 160.5;
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
sort(v.begin(),v.end(),FunctorCallLess<WeightFnType,Person>(f1,f2));
cout<<"By weight:"<
for(vector
{
cout<
}
sort(v.begin(),v.end(),FunctorCallLess
cout<<"By age:"<
for(vector
{
cout<
}
return 0;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Tue Dec 16, 2003 11:26 am Post subject: Re: sort through multiple key with STL |
|
|
Hi,
Try this:
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>
#include <ostream>
template <class T, typename M, class Comparator>
struct MemComp : public std::binary_function<T, T, bool>
{
MemComp(M T::*memptr, const Comparator &comp = Comparator())
: m_(memptr), c_(comp) {}
bool operator()(const T &left, const T &right) const
{
return c_(left.*m_, right.*m_);
}
private:
M T::*m_;
Comparator c_;
};
template <class T, typename M, class Comparator>
MemComp<T, M, Comparator>
makeMemComp(M T::*m, const Comparator &c)
{
return MemComp<T, M, Comparator>(m, c);
}
struct Person
{
Person(int a, int s) : age(a), salary(s) {}
int age;
int salary;
};
int main()
{
std::vector<Person> v;
v.push_back(Person(30, 1000));
v.push_back(Person(32, 800));
std::cout << "sorting by age:n";
std::sort(v.begin(), v.end(),
makeMemComp(&Person::age, std::less
for (size_t i = 0; i != v.size(); ++i)
std::cout << v[i].age << ", "
<< v[i].salary << 'n';
std::cout << "nsorting by salary:n";
std::sort(v.begin(), v.end(),
makeMemComp(&Person::salary, std::less
for (size_t i = 0; i != v.size(); ++i)
std::cout << v[i].age << ", "
<< v[i].salary << 'n';
}
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Tue Dec 16, 2003 6:03 pm Post subject: Re: sort through multiple key with STL |
|
|
In article <19b0e504.0312151553.7b25b186 (AT) posting (DOT) google.com>, Dan
McLeran <dan.r.mcleran (AT) seagate (DOT) com> writes
| Quote: | I feel that I could do better with some "mem_fun_ref" and "adjacent_find",
but I waste time on this, having the impression of "reinventing" the
wheel...
Any suggestion, help, appreciated...
I have a suggestion, although it's not very elegant yet. I've added
methods to your Person struct to make this work, don't know if this is
acceptable or not. Also, this template requires the functor type and
class type that contains the methods you wish to call. There is a way
to eliminate the 2nd template parameter but I don't have alot of time
to spend messing with it.
|
As the OP was implicitly asking about a way to optimise the sort with
two criteria (or more likely simply did not know about stable_sort but
did know that sort does not respect prior order when two elements
compare equal)
I think that you have spent a good deal of time providing a generic
solution to the questions asked rather than addressing the reason the
question was asked. This is a very common problem and is addressed,
IIRC, in the very first essay in Programming Pearls (Bentley, 2ed 0 201
65788 0) which should IMO, be required reading for programmers.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
or http://www.robinton.demon.co.uk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Tue Dec 16, 2003 6:03 pm Post subject: Re: sort through multiple key with STL |
|
|
In article <brmhkj$bb1$1 (AT) atlantis (DOT) news.tpi.pl>, Maciej Sobczak
<no.spam (AT) no (DOT) smap.com> writes
| Quote: | Hi,
Try this:
#include
#include
#include
#include
#include
template
struct MemComp : public std::binary_function
{
MemComp(M T::*memptr, const Comparator &comp = Comparator())
: m_(memptr), c_(comp) {}
bool operator()(const T &left, const T &right) const
{
return c_(left.*m_, right.*m_);
}
private:
M T::*m_;
Comparator c_;
;
|
I do not see how this addresses the OP's problem. He wants to sort a
sequence container by two (or more) criteria. AFAICS all your code does
is provide a complicated way of generating a suitable comparison
function for a single criterion.
Possibly I am just confused by all this genericity. Perhaps we should
add another guideline for application programmers along side the Rule 1
for optimisation:
Don't write generic code.
and Rule 2
Don't write generic code yet.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
or http://www.robinton.demon.co.uk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Wed Dec 17, 2003 10:19 am Post subject: Re: sort through multiple key with STL |
|
|
Hi,
Francis Glassborow wrote:
| Quote: | In article <brmhkj$bb1$1 (AT) atlantis (DOT) news.tpi.pl>, Maciej Sobczak
[email]no.spam (AT) no (DOT) smap.com[/email]> writes
Try this:
I do not see how this addresses the OP's problem.
|
It all depends on what the OP's problem is.
| Quote: | He wants to sort a
sequence container by two (or more) criteria.
|
Yes, this is what I can see by the way he calls std::sort algorithm.
However, there is a sort_by_Age function that is defined but not used in
the example code. I understood that the OP's problem was to find a way
to sort array of structs by different criteria (that's what the presence
of sort_by_Age and sort_by_Salary suggests to me), possibly combining
the sort (that's what sort_by_Age_Salary suggests).
My understanding is that there is no need to write a separate comparison
function for every field in every struct (x2 for less/greater
comparisons), because such sorting always boils down to "get the member
and compare" and can be done with single MemComp functor, reusable with
other fields and with other structs.
| Quote: | AFAICS all your code does
is provide a complicated way of generating a suitable comparison
function for a single criterion.
|
Reusable way. It aims at avoiding writing separate comparison functions
for every field in every struct. Programmers sometimes write too much
anticipating the use that is in fact never needed (consider the OP's
sort_by_Age function - defined but not used).
The way to sort by one key was shown in my example. The reader should be
able to adapt it for his particular needs.
The way to sort by multiple keys was shown by you with the use of
stable_sort, where MemComp is also usable.
I believe that your suggestion + the MemComp presented in my post are
both very good tools (orthogonal and therefore usable together or in
separation) and both deserve to be known.
| Quote: | Possibly I am just confused by all this genericity.
Perhaps we should
add another guideline for application programmers along side the Rule 1
for optimisation:
Don't write generic code.
|
Yesterday, Le Chaud Lapin wrote: "Don't write classes".
Where are we heading?
I'm scared to open the next post... "Don't write C++"???
;)
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Aniket Kulkarni
Guest
|
| Posted: Wed Dec 17, 2003 10:20 am Post subject: Re: sort through multiple key with STL |
|
|
"jean Davy" <nospam (AT) unspam (DOT) com> wrote
| Quote: | Say I have a struct like this
struct PERSON
{
int Age;
float Salary;
string Name;
};
Hi Jean, |
How about this
enum Keys { AGE, SALARY, NAME };
enum Direction { ASC, DESC };
typedef std::vector<Keys> sort_keys;
template <Direction d=ASC>
struct compare : public std::binary_function<person, person, bool>
{
compare (sort_keys& keys) : _keys (keys) {}
bool operator() (const PERSON& left, const PERSON& right)
{
return d == ASC ? compare_one( left, right ) : compare_one( right, left );
}
bool compare_one( const PERSON& left, const PERSON& right )
{
for (sort_keys::iterator i = _keys.begin(); i != _keys.end() ; i++ ) {
switch (*i) {
case AGE:
if (left.age != right.age) return left.age < right.age;
break;
case SALARY:
if (left.salary != right.salary) return left.salary < right.salary;
break;
case NAME:
if (left.name != right.name) return left.name < right.name;
}
}
return false;
}
private:
sort_keys& _keys;
};
std::vector
// Create the list of sort keys
sort_keys k; k.push_back( AGE );
// Sort V on key AGE, in ascending order
std::sort( v.begin(), v.end(), compare<ASC>( k ) );
// Sort V on keys AGE and NAME in descending order
std::sort( v.begin(), v.end(), compare<DESC>( k ) );
A vector of keys spefies the keys to be used for sorting. So if k
contains [AGE, NAME] then V is first sorted on AGE and then on NAME
The compare class, checks the equality for each sort key, and returns
less_than for the first un-equal key. For Descending sort, the arguments
to less_than are simply swapped
HTH
~ aniket
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Wed Dec 17, 2003 4:46 pm Post subject: Re: sort through multiple key with STL |
|
|
Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote
[...]
| Quote: | Possibly I am just confused by all this genericity. Perhaps we should
add another guideline for application programmers along side the Rule
1 for optimisation:
Don't write generic code.
and Rule 2
Don't write generic code yet.
|
This reminds me of something Dietmar Kuehl said in another thread, about
inheritance: use inheritance if you must, use something else if you can.
In both cases, I think that the real rule is just Occam's razor. Don't
use inheritance/generic code unless the alternatives are "worse" (more
complicated). To which I would add: define exactly what you need before
deciding: generally, inheritance or generic code will do more than the
simpler alternatives. Which justifies using it IF (and only if) you
need that something more.
Obviously, too, I'm talking about the usual case in a professional
environment, where the goal is a maintainable program which does what it
is supposed to. If the goal is experimenting, learning a new feature,
or demonstrating it to someone else, then not using the feature because
it isn't needed isn't a good idea, and creating an example where it
absolutly is needed may introduce additional complexities which detract
from the problem at hand.
--
James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Wed Dec 17, 2003 4:57 pm Post subject: Re: sort through multiple key with STL |
|
|
In article <brp4lp$rek$1 (AT) atlantis (DOT) news.tpi.pl>, Maciej Sobczak
<no.spam (AT) no (DOT) smap.com> writes
| Quote: | Don't write generic code.
Yesterday, Le Chaud Lapin wrote: "Don't write classes".
Where are we heading?
I'm scared to open the next post... "Don't write C++"???
;)
But we are actually being entirely consistent. If you want to program |
your VCR machine don't write C++  If you want to customise your
browser do not write a C++ plugin unless the functionality you require
cannot be provided otherwise.
IOWs be aware of the relevance and costs entailed. For example, many
years ago I spent a good deal of my Summer holiday writing a set of
extensions (to handle school data -- there weren't any efficient
databases around in those days) for a version of BASIC that was used on
my school's newly acquired micro computer. As I did not have an
assembler I actually had to convert my Z80 code to hex. The end result
was that I could generate all the lists the school ever needed
(including highly personalised ones) on a single afternoon (limited only
by the speed of the printer). The school got back my invested time many
times over in the next few years, as well as my colleagues appreciating
what could be achieved. My children's school used their machine for a
solid week to generate a standard set of lists (no customisation
options) on an identical machine (they declined my offer to give them
the extended software:-)
These days I would never dream of spending time writing (and hand
assembling) assembler. Such programs are definitely I/O bound these
days. I would just purchase a suitable database and spend some time
customising that. Now I just might do the customisation in C++ but
probably not.
So, don't write C++ unless doing so solves a problem as effectively as
the other options.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
or http://www.robinton.demon.co.uk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Thu Dec 18, 2003 8:44 am Post subject: Re: sort through multiple key with STL |
|
|
On 17 Dec 2003 11:46:15 -0500, [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote:
| Quote: | Obviously, too, I'm talking about the usual case in a professional
environment, where the goal is a maintainable program which does what it
is supposed to. If the goal is experimenting, learning a new feature,
or demonstrating it to someone else, then not using the feature because
it isn't needed isn't a good idea, and creating an example where it
absolutly is needed may introduce additional complexities which detract
from the problem at hand.
|
Unfortunately that results in all examples being obviously incorrect use
of the features. One can easily conclude that there is no need for the
features. As you said, they will usually not be used in a professional
environment.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dan McLeran
Guest
|
| Posted: Fri Dec 19, 2003 7:44 am Post subject: Re: sort through multiple key with STL |
|
|
| Quote: | As the OP was implicitly asking about a way to optimise the sort with
two criteria (or more likely simply did not know about stable_sort but
did know that sort does not respect prior order when two elements
compare equal)
|
Actually, the OP wrote:
'given a container of PERSON, what is the "easiest " way of sorting
these
through the struct members.'
I don't see the word optimize anywhere. One could debate whether or
not my recommendation is "easier".
Regards.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
