STL Vector + sort
Mariusz

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?

 1 class CSprite 2 { 3 protected: 4 // Attributes 5 int m_AnimIndex; 6 int m_AnimCount; 7 8 float revPerSec; 9 float theta; 10 11 float m_x; 12 float m_y; 13 float m_vx; 14 float m_vy; 15 int m_dx; 16 int m_dy; 17 int m_Active; 18 int m_ZOrder; 19 20 int m_PrevAnimation; 21 vector m_Animations; 22 23 public: 24 // Constructor 25 CSprite(); 26 // Destructor 27 virtual ~CSprite(); 28 29 // Methodes 30 void Add(CAnimation *ptrAnimation); 31 virtual void Input(); 32 virtual void Render(BITMAP *buffer); 33 virtual void Update(float dt); 34 virtual void ChangeAnimation(int _id); 35 virtual void ChangeAnimation(string _name); 36 void SetPosition(int x, int y) {m_x = x; m_y = y;} 37 void SetDirection(int x, int y) {m_dx = x; m_dy = y;} 38 void SetVelocity(float x, float y) {m_vx = x; m_vy = y;} 39 void SetZOrder(int z) {m_ZOrder = z;} 40 bool Collision(CSprite *spr1, CSprite *spr2); 41 // Helpers 42 };

Thanks,
Mariusz

Billybob

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

Mark Oates

Mariuz:

```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.

-----

this is my code that does not compile:

 1 class time_stamp_object 2 { 3 public: 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 17 bool 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?

Billybob

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

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

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

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

Mariusz

Thats right now I remember. Thanks a lot

Bob

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);
```

Mariusz

Thats 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:

 1 void 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

Billybob

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

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

Dustin Dettmer
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);
```

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.

HoHo

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:

 1 class time_stamp_object 2 { 3 public: 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 22 std::sort(timestamps.begin(), timestamps.end());

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

Dustin Dettmer
```#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.

Tobias Dammers

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

Dustin Dettmer
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.

Mariusz

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 26 void SetZOrder(int z) {m_ZOrder = z;} 27 28 bool 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

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

Well, I am not exactly sure where to place Bobs 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'
Galaxy.cpp

Thanks,
M.

lennaert van der linden

You probably forgot to #include <algorithm>.

I have made a small example:

 1 #include 2 #include 3 #include // contains std::sort 4 #include 5 6 class Sprite 7 { 8 public: 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; } 12 private: 13 std::string name_; 14 int z_order_; 15 }; 16 17 // compare pointer to sprites 18 int compareSprites( Sprite const* s1, Sprite const* s2 ) 19 { 20 return s1->getZOrder() < s2->getZOrder(); 21 } 22 23 int main() 24 { 25 std::vector 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

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

M.