STL Vector + sort

STL Vector + sort

Mariusz

Member #1,634

November 2001

Hello,

I am using vectors for my Sprite class. I was wondering how to implement sorting so that I could order my sprites using ZOrder attribute that I have given it?

1class CSprite
2{
3protected:
// Attributes
int  m_AnimIndex;
int  m_AnimCount;
7 
float revPerSec;
float theta;
10 
float m_x;
float m_y;
float m_vx;
float m_vy;
int m_dx;
int m_dy;
int m_Active;
int m_ZOrder;
19 
int  m_PrevAnimation;
vector<CAnimation*>  m_Animations;

23public:
// Constructor
CSprite();
// Destructor
virtual ~CSprite();
28 
// Methodes
void Add(CAnimation *ptrAnimation);
virtual void Input();
virtual void Render(BITMAP *buffer);
virtual void Update(float dt);
virtual void ChangeAnimation(int _id);
virtual void ChangeAnimation(string _name);
void SetPosition(int x, int y) {m_x = x; m_y = y;}
void SetDirection(int x, int y) {m_dx = x; m_dy = y;}
void SetVelocity(float x, float y) {m_vx = x; m_vy = y;}
void SetZOrder(int z) {m_ZOrder = z;}
bool Collision(CSprite *spr1, CSprite *spr2);
// Helpers
42};

Thanks,
Mariusz

Billybob

Member #3,136

January 2003

Overload the < operator on that class. Then you can use STL's regular sort algorithm.

Mark Oates

Member #1,146

March 2001

Mariuz:
overload with this:

bool operator<(const CSprite &a, const CSprite &b)
{
   return a.m_ZOrder < b.m_ZOrder;
}

and sort with this:

vector<CSprite> sprites;
sort(sprites.begin(), sprites.end());

it might be squirly because m_ZOrder is protected.

-----
I was about to post a very similar question, but more about the nature of overloading:

this is my code that does not compile:

1class time_stamp_object
2{
3public:
4    unsigned int min;
5    unsigned int sec;
6    unsigned int hun_sec;
7    
8    int get_length()
9    {
10        int num = hun_sec;
11        num += sec*100;
12        num += min*60*100;
13        return num;
14    }
15};
16 
17bool operator<(const time_stamp_object &a, const time_stamp_object &b)
18{
19   return a.get_length() < b.get_length();
20}

for some reason it doesn't like that I'm using a function (get_laugh()) to compare the two objects, and I get the errors:

main.cpp: In function `bool operator<(const time_stamp_object&, const time_stamp_object&)':
main.cpp:108: error: passing `const time_stamp_object' as `this' argument of `int time_stamp_object::get_length()' discards qualifiers
main.cpp:108: error: passing `const time_stamp_object' as `this' argument of `int time_stamp_object::get_length()' discards qualifiers

what am I doing wrong?

--
Visit CLUBCATT.com for cat shirts, cat mugs, puzzles, art and more <-- coupon code ALLEGRO4LIFE at checkout and get $3 off any order of 3 or more items!

AllegroFlare • AllegroFlare Docs • AllegroFlare GitHub

Billybob

Member #3,136

January 2003

Mark: get_length needs to be declared const, otherwise the compiler is unsure if get_length will modify the object, therefore possibly violating the const in operator<'s parameters.

Mariusz

Member #1,634

November 2001

Thanks for your quick response. Well it has been ages since I have worked with operators. It apears that I have to put this outside my CSprite class, which then like you said my m_ZOrder would not be accessible, unless I make it public. Is there another way to make this operator part of my class?

Right now If I make < part of CSprite I get:
error C2804: binary 'operator <' has too many parameters

Thanks,
Mariusz

Billybob

Member #3,136

January 2003

Because it should only be one parameter, and you'd do
this->m_ZOrder < other_thing.m_ZOrder

I'm not sure if it'll still complain about protected, though. If it does you'll need to create a function that returns m_ZOrder, or just move m_ZOrder to public.

EDIT:

bool operator<(const CSprite &b)
{
   return this->m_ZOrder < b.m_ZOrder;
}

Mark Oates

Member #1,146

March 2001

William: I tried adding const in front of the function but didn't work ... ??

--
Visit CLUBCATT.com for cat shirts, cat mugs, puzzles, art and more <-- coupon code ALLEGRO4LIFE at checkout and get $3 off any order of 3 or more items!

AllegroFlare • AllegroFlare Docs • AllegroFlare GitHub

Mariusz

Member #1,634

November 2001

Thats right now I remember. Thanks a lot

Bob

Free Market Evangelist

September 2000

You don't need to overload anything if you don't want to. You can just write something like:

struct sprite_sorter {
    bool operator()(const CSprite &a, const CSprite &b) {
        return a.m_ZOrder < b.m_ZOrder;
    }
};

/* And then */
std::sort(sprites.begin(), sprites.end(), sprite_sorter);

--
- Bob
[ -- All my signature links are 404 -- ]

Mariusz

Member #1,634

November 2001

Thats cool, but I have just implemented William's suggestion and it seems that everything is working just fine. Anyhow, I really appreciate your input, it helps me to refresh my rusty C/C++ stuff.

All the best,
Mariusz

-----------------------------------------------------------------------------------
Few minutes later......

Wow, now I am confused. The sorting works just fine when I use QuickWatch everything is sorted as it should, but my Render function draws somehow different.

I have BG with zOrder of 1000 (background with size of full screen).
I have two sprites zOrder 1 and 1005

My Render function looks like this:

1void CGame::Draw()
2{
3  const int h = text_height( font );
4  const int c = makecol( 255, 255, 255 );
5 
6  // Draw Sprites
7  acquire_bitmap(m_Buffer);
8 
9  sprite_list::const_iterator spr=sprites.begin();
10  while (spr!=sprites.end()) 
11  {
12    (*spr)->Render(m_Buffer);
13    spr++;
14  }
15 
16  release_bitmap(m_Buffer);
17 
18  // Blit all
19  acquire_screen();
20  blit(m_Buffer, screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);
21  release_screen();
22}

I would expect fro one sprite to be hidden behind my Background according to its ZOrder.

Any suggestions?

Mark Oates

Member #1,146

March 2001

(oops wrong thread)

--
Visit CLUBCATT.com for cat shirts, cat mugs, puzzles, art and more <-- coupon code ALLEGRO4LIFE at checkout and get $3 off any order of 3 or more items!

AllegroFlare • AllegroFlare Docs • AllegroFlare GitHub

Billybob

Member #3,136

January 2003

Mark: Hmm, learn something new everyday. You need to put it after the () of the function.
"const int some_function" apparently means that the result is constant, while
"int some_function() const" means that the function will not modify *this.

Mark Oates

Member #1,146

March 2001

ah, thanks. I'd give a cookie if I could.

--
Visit CLUBCATT.com for cat shirts, cat mugs, puzzles, art and more <-- coupon code ALLEGRO4LIFE at checkout and get $3 off any order of 3 or more items!

AllegroFlare • AllegroFlare Docs • AllegroFlare GitHub

ImLeftFooted

Member #3,935

October 2003

Quote:

struct sprite_sorter {
bool operator()(const CSprite &a, const CSprite &b) {
return a.m_ZOrder < b.m_ZOrder;
}
};

/* And then */
std::sort(sprites.begin(), sprites.end(), sprite_sorter);

Why bother with the struct?

#include <algorithm>

static bool comp(const CSprite &a, const CSprite &b) {
  return a.m_ZOrder < b.m_ZOrder;
}

std::sort(sprites.begin(), sprites.end(), comp);

[edit]

Quote:

Right now If I make < part of CSprite I get:
error C2804: binary 'operator <' has too many parameters

Make the operator < take only one argument and compare whether *this < the parameter.

How is my posting?

HoHo

Member #4,534

April 2004

I would probably go with overloaded operator< if maximum speed is necessary. I'm not sure if functors can get inlined.

// should be inside class definition
bool operator<(const CSprite &a) const 
{
   return m_ZOrder < a.m_ZOrder;
}


//Somewhere in code
std::sort(sprites.begin(), sprites.end());

If I was Mark I'd use this kind of code:

1class time_stamp_object
2{
3public:
4    unsigned int min;
5    unsigned int sec;
6    unsigned int hun_sec;
7    
8    int get_length() const
9    {
10        int num = hun_sec;
11        num += sec*100;
12        num += min*60*100;
13        return num;
14    }
15    bool operator<(const time_stamp_object &a) const
16    {
17        return get_length() < a.get_length();
18    }
19};
20 
21//somewhere in code
22std::sort(timestamps.begin(), timestamps.end());

If all this code is in headers those functions should get inlined.

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

ImLeftFooted

Member #3,935

October 2003

#include <algorithm>

inline bool comp(const CSprite &a, const CSprite &b) {
  return a.m_ZOrder < b.m_ZOrder;
}

std::sort(sprites.begin(), sprites.end(), comp);

Any speed boost you're getting from using operator < is imagined.

How is my posting?

Tobias Dammers

Member #2,604

August 2002

What HoHo said. The overloaded operator should be a member func. That's why the compiler complains about the "this" argument.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

ImLeftFooted

Member #3,935

October 2003

Quote:

What HoHo said. The overloaded operator should be a member func. That's why the compiler complains about the "this" argument.

No, thats wrong. A standard conforming compiler accepts both ways, one takes 2 parameters and the other only takes 1.

How is my posting?

Mariusz

Member #1,634

November 2001

Hi,

I have a question in regards to STL list sorting.

This is a snap of my code that I use:

1 
2  CSprite *Background;
3 
4  CSprite *Player;
5  CSprite *Alien;
6 
7.
8.
9.
10  Player->SetZOrder(1);
11  Alien->SetZOrder(2);
12  Background->SetZOrder(0);
13  
14  sprites.push_back(Player);
15  sprites.push_back(Alien);
16  sprites.push_back(Background);
17  sprites.sort();
18 
19 
20.
21.
22.
23.
24 
25//Sprite Class
26void SetZOrder(int z) {m_ZOrder = z;}
27 
28bool CSprite::operator<(const CSprite &b)
29{
30   return this->m_ZOrder < b.m_ZOrder;
31}

Problem I am having is that Alien sprite is hidden behind Background and unless I add sprites in order Background, player, alien I have alien sprite hidden.

It appears that the sort function is not working for me. Any suggestions would be appreciated.

Thanks,
Mariusz

lennaert van der linden

Member #6,053

July 2005

This is a guess, but I think you are sorting pointers, instead of objects (it's a vector of pointers to CSprite, instead of an vector of CSprite). Try adding some logging to the operator< member function to see if it is actually called.

You could create a custom compare function that compares pointers to CSprite and use that as an argument to the sort algorithm. See Bob's message above.

Mariusz

Member #1,634

November 2001

Well, I am not exactly sure where to place Bobs code. Is the structure a part of Sprite Class, or a shared function?

Where do I call sort from, so far I get an error telling me that sort is not a member of std namespace.

error C2039: 'sort' : is not a member of 'std'
error C2275: 'sprite_sorter' : illegal use of this type as an expression
f:\Dev\App\Galaxy\Game.cpp(9) : see declaration of 'sprite_sorter'
error C3861: 'sort': identifier not found, even with argument-dependent lookup
Galaxy.cpp

Thanks,
M.

lennaert van der linden

Member #6,053

July 2005

You probably forgot to #include <algorithm>.

I have made a small example:

1#include <vector>
2#include <string>
3#include <algorithm> // contains std::sort
4#include <iostream>
5 
6class Sprite
7{
8public:
9  Sprite( std::string const& name, int z_order ) : name_(name), z_order_(z_order) {}
10  int getZOrder() const { return z_order_; }
11  void print() const { std::cout << "sprite " << name_ << std::endl; }
12private:
13  std::string name_;
14  int z_order_;
15};
16 
17// compare pointer to sprites
18int compareSprites( Sprite const* s1, Sprite const* s2 ) 
19{ 
20  return s1->getZOrder() < s2->getZOrder(); 
21}
22 
23int main()
24{
25  std::vector<Sprite*> ps;
26  ps.push_back( new Sprite( "player", 2 ) );
27  ps.push_back( new Sprite( "alien", 1 ) );
28  ps.push_back( new Sprite( "background", 0 ) );
29 
30  
31  std::cout << "unsorted:" << std::endl;
32  std::for_each( ps.begin(), ps.end(), std::mem_fun( &Sprite::print ) );
33 
34  std::sort( ps.begin(), ps.end() );
35  std::cout << "\nsorted by pointer address:" << std::endl;
36  std::for_each( ps.begin(), ps.end(), std::mem_fun( &Sprite::print ) );
37 
38  std::sort( ps.begin(), ps.end(), compareSprites );
39  std::cout << "\nsorted by z-order (using compareSprites):" << std::endl;
40  std::for_each( ps.begin(), ps.end(), std::mem_fun( &Sprite::print ) );
41}

Mariusz

Member #1,634

November 2001

Thank you, I will check this as soon I have a chance.