Archived

This topic is now archived and is closed to further replies.

Bu6mAn

Sorting a std::list<cClassName*>

Recommended Posts

Hi there, my scenario is this one. I currently have a class which represents a Renderer, that has as an atribute a RenderQueue, that is actually a sorted list of pointers to "RenderableObjects". It goes like this:
class cRenderableObject {

  protected:
  int zValue;
  tPoint aPosition;

  public:
  virtual void mDraw() = 0; // Abstract
  friend bool operator<(const cRenderableObject &obj1, const cRenderableObject &obj2) {
	  return (obj1.zValue > obj2.zValue); // Descending sorting, cause it''s a z-buffering }
};


class cSurfaceObject : public cRenderableObject {

  private:
  CL_Surface* aImage;

  public:
  cSurfaceObject(CL_Surface* objImage,int posX, int posY, int zVal);
  void mDraw() { aImage->draw(aPosition.x,aPosition.y); }
};


class cRenderer {

  private:
  static std::list aRenderQueue;

  public:
  static void mAddToQueue(cRenderableObject* objImage);
  static void mRenderQueue();
};
 
So, at certain point y perform a: aRenderQueue.sort(); But, it''s not sorting properly. I think it''s not using the overloaded <"less" operator at all. Maybe it''s because i hold up a list of pointers to cRenderableObject class, and not a list to just objects? Well in that case, how can i accomplish the sorting properly? still using the pointers?. I need this for implementing/simulating a zbuffer for a 2D Graphic Adventure, since ClanLib (the gamelib i''m using), doesn''t support zbuffering/ordering right now. So i''ll keep a list of pointers to the objects to be rendered, updated and sorted at all times, and thanks to polimorphism i can call the ->mDraw() method for every object despite what class they really are. Thanks. If you need better explanations, ask for one.

Share this post


Link to post
Share on other sites
quote:
Original post by Bu6mAn
Maybe it''s because i hold up a list of pointers to cRenderableObject class, and not a list to just objects?


Yep, this is way. It''s sorting based on the value of the pointers

list::sort ought to take a compator functor - so you can make one that takes two cRenderableObject*''s and compare them are you wish.

Share this post


Link to post
Share on other sites
I had a similar problem, and yes, it is sorting the list by pointers, not by objects. As Magmai stated, you need to use a functor, which is essentially a class containing (usually) only one function - an overloaded () operator. In your case it would probably look something like this:


  
class cLessThan
{
public:
bool operator ()(cRenderableObject *lhs, cRenderableObject *rhs)
{return(*lhs < *rhs ? true : false);}
};


and then you would use std::list::sort() like this:

aRenderQueue.sort(cLessThan());

and that should work (I haven''t tested this code specifically, so you might need to tinker with it).

Share this post


Link to post
Share on other sites
Thanks a lot, i read at the book i''m using (The complete Reference C++, Herbert Shildt), that a functor or something could be specified, but i really didn''t know what that was. I tried passing pointers to functions and didn''t work.

Thanks a lot, both, saved my day =).

Share this post


Link to post
Share on other sites
Yes, it''s sorting the pointer by their numeric value.
You need to write a sorting predicate (preferably predicate class) that takes the pointers and compare what they point to, then pass that as the parameter to list::sort.

Or you can use the following adapters to do the indirections for you :

  
template<class BinOp>
struct unary_indirect
{
UnOp op;

typedef const typename UnOp::argument_type* const first_argument_type;
typedef typename UnOp::result_type result_type;

result_type operator()( argument_type arg ) const
{
return op( *arg );
}
};

template<class BinOp>
struct binary_indirect
{
BinOp op;

typedef const typename BinOp::first_argument_type* const first_argument_type;
typedef const typename BinOp::second_argument_type* const second_argument_type;
typedef typename BinOp::result_type result_type;

result_type operator()( first_argument_type lhs,
second_argument_type rhs ) const
{
return op( *lhs, *rhs );
}
};
[source]

And call <tt>aRenderQueue.sort( binary_indirect< less<cRenderableObject> >() );</tt>



[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
I''m getting a message from VC++ Compiler, stating this:

ImplementUtopia.cpp
C:\utopia\source\classes\ImplementUtopia.cpp(642) : error C2664: ''void __thiscall std::list >::sort(struct std::greater)'' : cannot convert parameter
1 from ''class cLessThan'' to ''struct std::greater''
No constructor could take the source type, or constructor overload resolution was ambiguous

--------------------------------------------------

Yoshin, i''ve followed your instructions and also took a look at some examples here: http://www.pixelate.co.za/issues/6/6/articles/stl2/part2.html, so everything looks fine in terms of declarations, but the compiler is complaining. Here''s how i did it:

At the interface:
------------------

class cLessThan {

public:
bool operator()(cRenderableObject* obj1, cRenderableObject* obj2) { return obj1->zValue > obj2->zValue; }

};

At the implementation:
----------------------

void cRenderer::mAddToQueue(cRenderableObject* objImage) {

// Agrego el objeto al Queue
aRenderQueue.push_back(objImage);

// Hago un sorting de la lista
aRenderQueue.sort(cLessThan());

}

------------------------------------

Everything seems fine, doesn''t it? Any clues? Thanks again //

Share this post


Link to post
Share on other sites
For some reason, the sorting predicate you pass to std::list must be a greater<T> type. Beats me as to why.

To get around that, use the generalized sort algorithm sort:

          
std::sort( aRenderQueue.begin(), aRenderQueue.end(), cLessThan());


And I wonder why a list needs a greater predicate...

[edited by - Zipster on March 3, 2003 2:08:20 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
For some reason, the sorting predicate you pass to std::list must be a greater type. Beats me as to why.

To get around that, use the generalized sort algorithm



Thats dropping me lot of errors. I''m not sure, but i think i read somewhere that the general sort couldn''t be used with the std::list. Please, correct me if i''m wrong...

Share this post


Link to post
Share on other sites
quote:
Original post by Bu6mAn
Thats dropping me lot of errors. I''m not sure, but i think i read somewhere that the general sort couldn''t be used with the std::list. Please, correct me if i''m wrong...


They can, except in Visual Studio, whose library is improperly implemented.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
Damn, i''m using visual studio. Does anybody knows another workaround then? What about that Greater predicate? What should i pass to the list::sort then, if it doesn''t want yo receive a comp functor?

Share this post


Link to post
Share on other sites
Check out Fruny''s link to STLPort for a well-implemented standard library. Once you go STLPort, you''ll never go back :D

It''s a bit tricky to get started using, because if you plan on using their IO streams you have to build the proper library first. However, if you just plan on making use of everything else, you have to tell the library that you don''t plan on using thier IO streams by defining a certain thing... the reference should tell you exactly what you define.

Share this post


Link to post
Share on other sites
The predicate for list::sort is the functor "greater".
greater is defined as:


    
template<class T>
struct greater : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y);
};


where, operator() returns true if x > y.

As you can see, the list::sort function, since it is storing pointers, will pass references to the *pointer values* to the greater predicate (i.e., greater<cRenderableObject *>

Therefore, you need to inherit a specialized greater predicate to handle pointers, like this:


  
template<T>
struct pointer_greater : public greater<T> {
bool operator()(const T& x, const T& y) {
return *x > *y;
}
};


Add an operator> to your cRenderableObject class, then, pass that predicate to the sort function and everything should be okay.



[edited by - fizban75 on March 3, 2003 12:56:43 PM]

[edited by - fizban75 on March 3, 2003 12:58:50 PM]

Share this post


Link to post
Share on other sites
Thanks fizban75, i''ll try that when i get home. I''ll also take a nice look at the STLPort, it''s very, very, tempting =).

Thanks everyone.

Share this post


Link to post
Share on other sites