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?

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

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

Mark Oates

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?

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

Thats 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

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

(oops wrong thread)

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.

ImLeftFooted

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.

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:

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.

ImLeftFooted

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

ImLeftFooted

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

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

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

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

Thread #569405. Printed from Allegro.cc

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<CAnimation*> 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	};

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 += min60100;
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	}

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	}

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	}

1	#include <vector>
2	#include <string>
3	#include <algorithm> // contains std::sort
4	#include <iostream>
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<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	}