Skip to main content
GameDev.net gamedev.net
🔒 Locked

std::sort question

Started by CProgrammer Apr 25, 2003 at 4:34 AM 23 replies 850+ views
Original Post
CProgrammer
CProgrammer
I have a struct as follows
struct obj
{
int id;
float value;
};

obj objs[10];

 
I want to use std::sort to sort the objs array according to its value variable -CProgrammer
Qw3r7yU10p!
Qw3r7yU10p!
and the question is...

Where can I find some documentation to tell me how to do it?
Qw3r7yU10p!
Qw3r7yU10p!
bookmark this site

see the second paragraph in Description
SabreMan
SabreMan
quote:
Original post by petewood
and the question is...

"I want to use std::sort to sort the objs array according to its value variable. My question is what is the capital of Portugal?"

Lektrix
Lektrix

      
#include <vector>

#include <algorithm>


struct obj
{
    int id;
    float value;
};

inline bool operator<(const obj &obj1, const obj &obj2)
{
    return obj1.value < obj2.value;
}

int main()
{
    std::vector<obj> objects;

    // insert elements


    std::sort(objects.begin(), objects.end());

    // ...


    return 0;
}

Edit: Removed the unnecessary functions.

[edited by - Lektrix on April 25, 2003 6:22:39 AM]
Beer Hunter
Beer Hunter
quote:
Original post by SabreMan
"I want to use std::sort to sort the objs array according to its value variable. My question is what is the capital of Portugal?"
I believe it''s Lisbon.
Qw3r7yU10p!
Qw3r7yU10p!
It is Lisbon.

Lektrix - as it says in the documentation I linked to, you only need the < operator. All the others you supply are unnecessary.

You can alternatively use a functor (which would be more adaptable as you could choose to sort by id or value).

[edited by - petewood on April 25, 2003 6:15:57 AM]
Lektrix
Lektrix
Yeah, I sort of guessed that, I just really couldn't be bothered to look through the header file for the algorithm. I just copied some of my code and found/replaced the object name and function body. In fact, looking through my post I also left the equality and inequality operators in ... oops ...

[ Google || Start Here || ACCU || MSDN || STL || GameCoding || BarrysWorld || E-Mail Me ]

[edited by - Lektrix on April 25, 2003 6:20:13 AM]
Qw3r7yU10p!
Qw3r7yU10p!
a functor is a function-like object. I.e. it is an object that can be called like a function. C++ lets you do this using operator(). The operator() can be overloaded with whatever arguments it needs.

    
#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

struct Speaker {
operator() {
cout << "Don't Speak" << endl;
}
operator()(const string& text) {
cout << text << endl;
}
};

int main() {
Speaker speaker;
speaker(); //calls operator() on the object

speaker("hello"); //calls operator()(const string&) on the object

}


What you can do is define a class, objCompare, with an operator()(const obj& lhs, const obj& rhs) which returns a bool saying whether first is less than second. Then you can use it with std::copy(objs, objs+10, objCompare())

[edited by - petewood on April 25, 2003 7:35:38 AM]
civguy
civguy
Functors are faster than function pointers because the comparison function can be inlined with functors.
SabreMan
SabreMan
quote:
Original post by petewood
a functor is a function-like object.

Or... a functor is a closure-like object which is rendered ineffectual through not being able to establish implicit bindings to it''s lexical environment.
cgoat
cgoat
quote:
Original post by SabreMan
Or... a functor is a closure-like object which is rendered ineffectual through not being able to establish implicit bindings to it''s lexical environment.


Umm, is that good or bad?

Dobbs
Dobbs
But lord it''s trying
flangazor
flangazor
[keeping with the topic drift...]I''m still peeing myself over SabreMan''s templated implementation of car, cdr, and cons.
cannelbrae
cannelbrae
Most of the std algorithms rely work on arrays. Here is a (hopefully) working example:


  
#pragma warning (disable:4514) // inline function removed


#include <algorithm>

struct obj
{
int id;
float value;
};

inline bool operator<(const obj &obj1, const obj &obj2)
{
return obj1.value < obj2.value;
}
int main()
{
const int ArraySize = 10;
obj objs[ArraySize];

// ...


objs[0].id = 9;
objs[0].value = 9;
objs[1].id = 8;
objs[1].value = 8;
objs[2].id = 7;
objs[2].value = 7;
objs[3].id = 6;
objs[3].value = 6;
objs[4].id = 5;
objs[4].value = 5;
objs[5].id = 4;
objs[5].value = 4;
objs[6].id = 3;
objs[6].value = 3;
objs[7].id = 2;
objs[7].value = 2;
objs[8].id = 1;
objs[8].value = 1;
objs[9].id = 0;
objs[9].value = 0;

std::sort(&objs[0], &objs[0] + ArraySize);
return 0;
}



Edit: Someday I will remember the source tag is different here and on flipcode.

[edited by - cannelbrae on April 25, 2003 1:20:46 PM]
cMADsc
cMADsc

  
#include <algorithm>
#include <iostream>

struct obj
{
int id;
float value;
};obj objs[10];

inline bool operator<(const obj &obj1, const obj &obj2){ return obj1.value < obj2.value;}

int main()
{
std::sort(objs, objs+10);

return 0;
}



-----------------------------
"There are ones that say they can and there are those who actually do."

"...u can not learn programming in a class, you have to learn it on your own."



[edited by - cMADsc on April 25, 2003 4:06:31 PM]
-----------------------------"There are ones that say they can and there are those who actually do.""...u can not learn programming in a class, you have to learn it on your own."
Shannon Barber
Shannon Barber
This is the more straight-forward:

      
#include <boost\array.hpp>

#include <algorithm>

bool sort_by_value(Obj& a, Obj& b)
{
return a.value < b.value;
}

boost::array<Obj, 10> objs;

std::sort(
objs.begin(),
objs.end(),
sort_by_value
);


This is a little more complicated, but a little more re-usable:

  
#include <boost\compose.hpp>
#include <algorithm>


boost::array<Obj, 10> objs;
std::sort(
objs.begin(),
objs.end(),
boost::compose_f_gx_hy(
std::less<int>(),
mem_accessor(&Obj::value),
mem_accessor(&Obj::value))
);

//mem_accessor follows:

template<class Class, typename Result>
struct mem_accessor_t : std::unary_function<Class, Result>
{
typedef Result Class::* MemPtr;
mem_accessor_t(MemPtr mem_ptr) : mem_ptr(mem_ptr)
{}
MemPtr mem_ptr;
Result& operator()(Class& c) const
{
return c.*mem_ptr;
}
const Result& operator()(const Class& c) const
{
return c.*mem_ptr;
}
};

template<class Class, typename Result>
mem_accessor_t<Class, Result> mem_accessor(Result Class::* mem_ptr)
{
return mem_accessor_t<Class, Result>(mem_ptr);
}


[edited by - Magmai Kai Holmlor on April 25, 2003 10:30:47 PM]
The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
Shannon Barber
Shannon Barber
Overloading operator < isn''t the right-thing-to-do, though it gets the job done. You should only do that for classes that represent values, such as a complex class.

For a structure, you might want to sort it on value now, but on another member or criteria later.

All pointers are iterators, but there are additional classes that are iterators but not pointers. You use iterators to iterate a container - to transverse it.

For an array, a pointer will work as an iterator, but for a tree, like a map or set, you need something more complicated. Containers define a typedef for their iterator, e.g.


  
typedef std::map<int, std::string> int2string_map;
int2string_map mymap;

int2string_map::iterator it = mymap.begin();
++it; //it now ''points'' to the next element in the map



In order for a class to be used in any stl container, it must have value semantics, which basicially means the copy ctor works as well as operator= and operator<.


The code you posted will not work because the list does not use a raw pointer for an iterator.

list::iterator it = L.begin();
int i = *it;
The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.