Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » STL Vector + sort

This thread is locked; no one can reply to it. rss feed Print
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:
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
23public:
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
Member #3,136
January 2003
avatar

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

_________________________________________________
"God speed, my lonely angel."
Bitcoin | Bitcoin Ponzi Scheme

Mark Oates
Member #1,146
March 2001
avatar

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
Member #3,136
January 2003
avatar

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.

_________________________________________________
"God speed, my lonely angel."
Bitcoin | Bitcoin Ponzi Scheme

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
avatar

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

_________________________________________________
"God speed, my lonely angel."
Bitcoin | Bitcoin Ponzi Scheme

Mark Oates
Member #1,146
March 2001
avatar

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

Mariusz
Member #1,634
November 2001

That’s right now I remember. Thanks a lot

Bob
Free Market Evangelist
September 2000
avatar

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

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:

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
avatar

(oops wrong thread)

Billybob
Member #3,136
January 2003
avatar

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.

_________________________________________________
"God speed, my lonely angel."
Bitcoin | Bitcoin Ponzi Scheme

Mark Oates
Member #1,146
March 2001
avatar

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

Dustin Dettmer
Member #3,935
October 2003
avatar

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
Member #4,534
April 2004
avatar

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

Dustin Dettmer
Member #3,935
October 2003
avatar

#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
Member #2,604
August 2002
avatar

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

Dustin Dettmer
Member #3,935
October 2003
avatar

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

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 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'
error C3861: 'sort': identifier not found, even with argument-dependent lookup
Galaxy.cpp

Thanks,
M.

lennaert van der linden
Member #6,053
July 2005
avatar

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.

M.

Go to: