Sign in to follow this  

std::sort

This topic is 4359 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

A while ago I posted problems with qsort() and was told to use std::sort. I did that and I still get some errors that I can't understand. I have a class unit:
class unit{
public:
 unit();
 int place_on_path,length_of_path;
 bool got_to_dest,path_found;
 int state;
 int formation_id;
 VERTEX position;
 VERTEX speed;
 float rotation;
 void init();
 void draw();
 void update();
 void InitPath();
 void FindSpeeds(grid now,grid next);
 grid path[500];
 grid current_step,next_step,offset; 
};

and a group class:
class player_group{
public:
 //typedef int (*compfn)(const void*, const void*);
 player_group();
 vector<unit>units;
 unit mid_pos;
 grid main_path[500];
 int place_on_path,length_of_path;
 int middle_man;
 
 ...
 
 void SortUnits(int method);
 bool SortDis( struct unit *elem1, struct unit *elem2);
 bool SortDisMid( struct unit *elem1, struct unit *elem2);
};

With the SortUnits function I want to sort the units vector according to the method. For example, inorder to sort them from closest to main_path to furthest from main_path I used the function:
bool player_group :: SortDis( struct unit *elem1, struct unit *elem2)
{
 if(  abs(elem1->next_step.x-main_path[place_on_path+step].x)+
      abs(elem1->next_step.y-main_path[place_on_path+step].y)
     <abs(elem2->next_step.x-main_path[place_on_path+step].x)+
      abs(elem2->next_step.y-main_path[place_on_path+step].y))			
      return FALSE;																					
   else										
      return TRUE;	
}

and then for the SortUnits I did:
void player_group :: SortUnits(int method)
{


  if(method==0)
  {
   sort(units.begin(), units.end(), SortDis());
  }
  if(method==1)
  {
  sort(units.begin(), units.end(), SortDisMid());
  }
}

But I got the error messages: PGroup.cpp C:\Dev-Cpp\Examples\ctf\PGroup.cpp In member function `void player_group::SortUnits(int)': 170 C:\Dev-Cpp\Examples\ctf\PGroup.cpp no matching function for call to `player_group::SortDis()' 55 C:\Dev-Cpp\Examples\ctf\PGroup.cpp candidates are: bool player_group::SortDis(unit*, unit*) What is the problem? Thanks!!

Share this post


Link to post
Share on other sites
Your units vector is declared as std::vector<unit> not vector<unit *> so your sort predicate will expect the parameters to be unit, not unit*.

Share this post


Link to post
Share on other sites
I changed the bool Sort functions to:

bool SortDis( struct unit elem1, struct unit elem2);

and changed the -> to '.' .
It still gave the same errors.
Thank.

EDIT: It looks from the errors that the problem is in the fact that I'm writing SortDis() without the elem1 and elem2 in the (), what should I do?

Share this post


Link to post
Share on other sites
make your sort routines static or make them global to make it work. Sort requires a binary function, means 2 arguments. BUT if you declare a memberfunction nonstatic it has 3 arguments, of which one is hidden (the this pointer). Also a pointer to a memberfunction is a bit different than a pointer to a 'global' function...afaik thats also why people invented delegates, so they can call memberfunctions of instances of classes (but thats a different story...)

ok the next thing you should make is, if you are programming 'const' correct you should make the params const


edit: eww yes your edit indicates another 'error' std::sort(units.begin(), units.end(), yoursortfunc_without_brackets);


T2k

Share this post


Link to post
Share on other sites
Thanks, can you show me with some code how I can make the sort function part of the player_group class so that I can use it's variables in the function?
Thanks.

Share this post


Link to post
Share on other sites
I read the link and did this:

struct SortDis : public player_group
{
bool operator()(unit*& elem1, unit*& elem2)
{
return abs(elem1->next_step.x-main_path[place_on_path+1].x)+
abs(elem1->next_step.y-main_path[place_on_path+1].y)
< abs(elem2->next_step.x-main_path[place_on_path+1].x)+
abs(elem2->next_step.y-main_path[place_on_path+1].y) ;
}
};



I still got just about the same errors!? Does anyone know what the problem is?

Thanks!!

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
I read the link and did this:
*** Source Snippet Removed ***


Quote:
Original post by JY
Your units vector is declared as std::vector<unit> not vector<unit *> so your sort predicate will expect the parameters to be unit, not unit*.



//BAD!!! v v
bool operator()( unit * & elem1, unit * & elem2 )
//BAD!!! ^ ^

//GOOD!!! v v
bool operator()( unit & elem1, unit & elem2 )
//GOOD!!! ^ ^

//EXTRA CREDIT! vvvvv vvvvv vvvvv
bool operator()( const unit & elem1, const unit & elem2 ) const
//EXTRA CREDIT! ^^^^^ ^^^^^ ^^^^^


/* Rationale: This is an issue of const correctness. consts #1 and #2 mean we
* won't modify our arguments, and thus it's OK to pass our function const
* objects. Non-const objects are also fine. Note that by doing this,
* assignments such as "elem1.next_step = ..." will generate compiler errors,
* since elem1 is const. This is to prevent a mistake - a good thing in this
* case! Const #3 tells the compiler that the function itself isn't modifying
* anything of it's owning class - thus this becomes legal:
*
* const SortDis sorter;
* bool unit1_before_unit2 = sorter( unit1 , unit2 );
*
* As is, the above code will fail, because operator() is not const, and thus
* cannot be called for a const SortDis (as sorter is).
*/

//BAD!!               vv
abs(elem1->blah)+
abs(elem1->blah)
< abs(elem2->blah)+
abs(elem2->blah) ;
//BAD!!! ^^

//GOOD!! v
abs(elem1.blah)+
abs(elem1.blah)
< abs(elem2.blah)+
abs(elem2.blah) ;
//GOOD!!! ^


[Edited by - MaulingMonkey on January 27, 2006 1:58:24 AM]

Share this post


Link to post
Share on other sites
Thanks, now my program atleast compiles but I have another problem. Originally I stored the units in an array. Then I changed them to a vector and changed the sort function as you said, but now my program crashes. Is there anything else that I have to modify? (in general)
Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
but now my program crashes.


The description of your crash is vauge to the point of not existing. Because it dosn't.

Find out where it's crashing (use a debugger to backtrace), post the relevant code, and then I might be able to make suggestions as to modification. The problem does not lie in the function/method so far discussed, I can say that much, even if it is crashing there, presuming it is indeed written as indicated.

Share this post


Link to post
Share on other sites
Thanks - Can you please explain how I can backtrace or use the debugger to find out were the program is crashing (I have DevC++)? I've wanted to know how to do that for a long time but I never figured it out. I usually start going line by line and give up after a few thousand lines. How can I do this?
Thanks! (I know almost nothing about this and the more detail and code thr better - Thanks a ton)

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
Thanks - Can you please explain how I can backtrace or use the debugger to find out were the program is crashing (I have DevC++)?


I havn't used DevC++, but I'm under the impression it simply uses the GNU Toolset, something I do have ample experience with.

5 second tutorial (output, user input, #comments):

C:\...\> gdb myprogram.exe
...
(gdb) run
...
Program received signal SIGSEGV, Segmentation fault. #Segfault = attempted read/write to an invalid location*
0x77c478c0 in _libmsvcrt_a_iname () #just an example - says where it crashed
(gdb) bt #backtrace
#0 0x77c478c0 in _libmsvcrt_a_iname () #same as our original message - actual current location
#1 0x0043bf1f in std::basic_ostream<char, std::char_traits<char> >& std::operat
or<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >
&, char const*) () #who called that function
#2 0x00401425 in main () #who called that function


For line information, compile with the flag -g3. Full example:

C:\Documents and Settings\Mike>g++ -g3 example.cc -o example

C:\Documents and Settings\Mike>gdb example
GNU gdb 5.2.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i686-pc-mingw32"...
(gdb) run
Starting program: C:\Documents and Settings\Mike/example.exe

Program received signal SIGSEGV, Segmentation fault.
0x00401304 in main () at example.cc:3 # format: "at file:line"
3 *foo = 3; # they even show us the line...
(gdb) bt
#0 0x00401304 in main () at example.cc:3 # same format
(gdb) _


Obviously, the problem lies with the variable "foo". There are two possible causes:

1) foo is a class member, and this is a member function, and the problem arises from trying to access the implicit this pointer ("this->foo"). This problem arises from calling member functions on a bad pointer, e.g.:

example * rawr = 0;
rawr->set_foo_to_three();


2) The problem arises from dereferencing it ("*foo"). This problem arises from foo being null, uninitialized, deleted, or otherwise pointing to something that isn't there. This is the case in the above example:

int main( void ) {
int * foo = 0;
*foo = 3;
}


Google for more information about using the GNU DeBugger (GDB).

Share this post


Link to post
Share on other sites
were can I get the gdb? I could only find compressed tar files and I dont know how to open them?
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
were can I get the gdb? I could only find compressed tar files and I dont know how to open them?

I use 7-Zip for .tar files on windows.

I would think GDB would have come with GCC which would have come with Dev-C++, however.

GNU Website
7-Zip Website
MinGW Website (MinGW = windows port of the GNU toolset, the GCC included with Dev-C++ comes from this AFAIK)
Cygwin Website (An alternative to MinGW, although just for the compiler I wouldn't go for cygwin for various reasons)

Share this post


Link to post
Share on other sites
I compiled different lines untill the program crashes and it looks like I'm still having trouble with the sort. I did:

//player_group group;
middle_man = group.FindMiddle();
group.mid_pos = group.units[middle_man];
group.SortUnits(1);


and the program crashed. I'm initializing the group like this:

void InitGroup()
{

unit push_unit;

group.units.clear();
////init positoins
for(j=0;j<number_of_units;j++)
{
do
{
push_unit.current_step.x = int(rand()%(MAP_SIZE-60))+30;
push_unit.current_step.y = int(rand()%(MAP_SIZE-60))+30;
}while((map[push_unit.current_step.x][push_unit.current_step.y]==1)||(map[push_unit.current_step.x][push_unit.current_step.y]==5)||(map[push_unit.current_step.x][push_unit.current_step.y]==4));

push_unit.init();
group.units.push_back(push_unit);
}

////////////////reset vars

group.place_on_path = 0;
group.group_state=0;
group.group_regrouped=FALSE;
group.mid_pos = group.units[group.FindMiddle()];
group.SortUnits(1);
group.FindFormationPositions();
group.middle_man = group.FindMiddle();
}




For some reason the program didn't crash when I called it in the initialization but but crashed when I called it later?

Do you have any idea what the problem is?
Thanks a lot!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Since "unit" is such a large class, it is HIGHLY recommended to use a vector of pointers instead of values:

vector<unit*> units;

Otherwise you'll get terrible performance when sorting the vector; All the elements in the vector may have to be copied around several times, and copying hundreds of objects each of which seem like some kilobytes (depending on what "grid" is) is going to be a killer for performance.

Of course, I shouldn't be making any assumptions about your code's bottlenecks like this. I'm just giving this as a general hint. But if I had to guess, I'd say that you are probably sorting it quite often and there are probably quite many units. Using a vector of pointers is a must in that case.

Share this post


Link to post
Share on other sites
I dont know, I feel stuck and its real annoying because it was working perfectly before I changed to stl eaven though I know that it'll be better in the long run - so please be patiant with me. I think that the sort function still isn't working for some reason.
My player_group and unit classes are the same as posted above, but the SortDisMid looks like this:

struct SortDisMid : public player_group
{
bool operator()(const unit & elem1, const unit & elem2)
{
return abs(elem1.current_step.x-mid_pos.current_step.x)+
abs(elem1.current_step.y-mid_pos.current_step.y)
< abs(elem2.current_step.x-mid_pos.current_step.x)+
abs(elem2.current_step.y-mid_pos.current_step.y);
}
};
////the file PGroup.h looks like this:

#ifndef PGROUP_H
#define PGROUP_H

#include <vector>
#include "PUnits.h"
//typedef int (*compfn)(const void*, const void*);
using namespace std;

class player_group{
public:
//typedef int (*compfn)(const void*, const void*);
player_group();
//unit units[20];
vector<unit> units;
unit mid_pos;
grid main_path[500];
grid src, dest;
bool group_regrouped;
bool resort;
int group_state,number_of_units;
int place_on_path,length_of_path;
int middle_man;
int group_stopped,change_pos_count;

void InitDestination();
void SortUnits(int method);
void MoveGroup();
int FindMiddle();
void RegroupUnits();
void FindFormationPositions();
void FindRegroupPath();
void MoveToTargetState();
void RegroupUnitsState();
void RegroupCheck();

};

struct SortDis : public player_group
{
bool operator()(const unit & elem1, const unit & elem2)
{
return abs(elem1.next_step.x-main_path[place_on_path+1].x)+
abs(elem1.next_step.y-main_path[place_on_path+1].y)
< abs(elem2.next_step.x-main_path[place_on_path+1].x)+
abs(elem2.next_step.y-main_path[place_on_path+1].y) ;
}
};

struct SortDisMid : public player_group
{
bool operator()(const unit & elem1, const unit & elem2)
{
return abs(elem1.current_step.x-mid_pos.current_step.x)+
abs(elem1.current_step.y-mid_pos.current_step.y)
< abs(elem2.current_step.x-mid_pos.current_step.x)+
abs(elem2.current_step.y-mid_pos.current_step.y);
}
};


//
#endif


Is there any problem with that?
I get the mid_pos in the InitGroup() above (any problem with that?) and the FindMiddle() function seems to work.
I print out all the distances from group.units[group.middle_man] after calling InitGroup and the units aren't sorted? - I get a list of numbers like this:
59 43 31 24 22 0 7 12 23 24
were group.number_of_units = 10, and group.middle_man = 5. The nimbers should go from smallest to biggest?
When I try to call the SortUnits(1) again the program crashes:( .

Does anyone have any ideas? I really want to get on with this game and my list of projects is starting to build up (over 20 ideas that I really want to try...) but I hate stopping in the middle of things.
Thanks a lot!!

Share this post


Link to post
Share on other sites
[EDIT] Use source tag and detail explanation. ;)
[EDIT2] Fix the '->' to '.'.

*note*:
1. Your SortDis and SortDisMid are classes.
2. Putting () behind both will create another new instance of the class. That way you are operating on some temporary-created-instance instead of your real object. That's why your stuff never get sorted. Further calling might screw up the stack and causes weird problems. And Your operator() overload hides your mistake.


I suggest you do this way:

class player_group
{
public:
static bool SortDis( unit const & elem1, unit const & elem2);
static bool SortDisMid( unit const & elem1, unit const & elem2);
};

bool player_group::SortDis(unit const & elem1, unit const & elem2)
{
return abs(elem1.next_step.x-main_path[place_on_path+step].x)+
abs(elem1.next_step.y-main_path[place_on_path+step].y)
< abs(elem2.next_step.x-main_path[place_on_path+step].x)+
abs(elem2.next_step.y-main_path[place_on_path+step].y);
}

bool player_group::SortDisMid(unit const & elem1, unit const & elem2)
{
return abs(elem1.current_step.x-mid_pos.urrent_step.x)+
abs(elem1.current_step.y-mid_pos.current_step.y)
< abs(elem2.current_step.x-mid_pos.current_step.x)+
abs(elem2.current_step.y-mid_pos.current_step.y);
}

void player_group::SortUnits(int method)
{
if(method==0)
{
sort(units.begin(), units.end(), SortDis);
}
if(method==1)
{
sort(units.begin(), units.end(), SortDisMid);
}
}





[Edited by - DerekSaw on February 10, 2006 2:22:27 AM]

Share this post


Link to post
Share on other sites
Sorry to bother you again...
Now I'm sure that there's a problem with the sorting. I changed the :
vector<unit> units; to:
units[20];

the PGroup.h file to:

extern player_group group //!Changed! :(
class player_group{
public:
//typedef int (*compfn)(const void*, const void*);
player_group();
unit units[20]; //!Changed!
//vector<unit> units;
unit mid_pos;
grid main_path[500];
grid src, dest;
bool group_regrouped;
bool resort;
int group_state,number_of_units;
int place_on_path,length_of_path;
int middle_man;
int group_stopped,change_pos_count;

void InitDestination();
void SortUnits(int method);
void MoveGroup();
int FindMiddle();
void RegroupUnits();
void FindFormationPositions();
void FindRegroupPath();
void MoveToTargetState();
void RegroupUnitsState();
void RegroupCheck();

};
/* /// !Changed!
struct SortDis : public player_group
{
bool operator()(const unit & elem1, const unit & elem2)
{
return abs(elem1.next_step.x-main_path[place_on_path+1].x)+
abs(elem1.next_step.y-main_path[place_on_path+1].y)
< abs(elem2.next_step.x-main_path[place_on_path+1].x)+
abs(elem2.next_step.y-main_path[place_on_path+1].y) ;
}
};

struct SortDisMid : public player_group
{
bool operator()(const unit & elem1, const unit & elem2)
{
return abs(elem1.current_step.x-mid_pos.current_step.x)+
abs(elem1.current_step.y-mid_pos.current_step.y)
< abs(elem2.current_step.x-mid_pos.current_step.x)+
abs(elem2.current_step.y-mid_pos.current_step.y);
}
};

*/

//!Changed!
int CompareDis(struct unit *elem1, struct unit *elem2);
int CompareDisMid(struct unit *elem1, struct unit *elem2);
//
#endif


And the SortUnits to

void player_group :: SortUnits(int method)
{


if(method==0)
{
//!Changed!
qsort((void *) &units, number_of_units, sizeof(struct unit), (compfn)CompareDis );
//sort(units.begin(), units.end(), SortDis());
}
if(method==1)
{
//!Changed!
qsort((void *) &units, number_of_units, sizeof(struct unit), (compfn)CompareDisMid );
//sort(units.begin(), units.end(), SortDisMid());
}
}



And everything worked perfectly! Why did it work like this and not with the std::sort? I know that I have to change to the std::sort cause qsort cant take members in classes so all the player_groups that I use will have to be defined as externs in the player_group file...total mess:( .
Does anyone know?
Thanks a lot!

Share this post


Link to post
Share on other sites
Thanks, I did what you said (the -> in SortDis should be '.' right?) and I got the following error:

135 C:\Dev-Cpp\Examples\ctf\PGroup.cpp
invalid use of member `player_group::main_path' in static

I think the problem is that I can't use members in static functions - but thats exactly what I want to do (thats why I'm using std and not qsort() )?

Without the static I get pointer to member errors.

Thanks!

Share this post


Link to post
Share on other sites
Ooops. You are right. I copy-paste. :P It should be '.'. And I miss that main_path. Sorry.

EDIT: Say, you need lots of data member access. I miss whole lot of that. A better naming next time. ;) (e.g. m_memberdata or _memberdata)

EDIT2: In that case, you do:


class player_group
{
void SortUnits(int method)
{
_method = method;
sort(units.begin(), units.end(), *this);
}

bool operator()(const unit & elem1, const unit & elem2)
{
if (_method == 1)
{
return ....;
}
if (_method == 2)
{
return ....;
}
}
private:
int _method;
};


Share this post


Link to post
Share on other sites
Sign in to follow this