Archived

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

std::list::sort() - on interfaces

This topic is 5106 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Okay im going to try to explain my problem *using a pesudo code as my code is EXTREMLY ugly and its cluttred up with unesesery stuff* I got a std::list that is used to store interface of this class.
class Shape
{
     public:
          size_t nSize;
};
 
in my class ShapeStorer I got this std::list
std::list< Shape* > shapes;
 
I allow the user to register a shape tru a RegisterShape() method. Now when all the Shapes* have been registerd ( all with diffrent nSize ). I want to be able to use the .sort() function on the std::list< Shape* > shapes. And make it so that shapes.begin() points to the smalles Shape ( => lowest nSize. 0 is the smallest ) HOW ???? I have looked tru all kinds of documentation but i just cant get it to work. Plz help me !! !!

Share this post


Link to post
Share on other sites
Well, you can''t do it with std::list::sort(). That one automatically uses operator< on the datatype, and you can''t do operator overloading on pointer types (well, except for new and delete, kind of).

Hmm....

You could make a smart-pointer class specifically for this, which would define operator<. That would be my suggestion.

It''s weird that std::list::sort doesn''t allow a functor argument.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Use std::sort. There is an overloaded version that takes a comparison predicate and define a predicate object for it that accepts the interface pointers as parameters:


template <class P>
class ptr_less : public binary_function<P, P, bool>
{
bool operator()(P p1, P p2) const { return *p1 < *p2; }
};


[edited by - antareus on December 14, 2003 8:26:24 PM]

Share this post


Link to post
Share on other sites
IIRC, std::sort won''t work on std::list because it expects bidirectional iterators.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
IIRC, std::sort won't work on std::list because it expects bidirectional iterators.


"Sneftel is correct, if rather vulgar." --Flarelocke

Hmm I'm smoking some good stuff then. I go now.

[actualContent]
I bet he has a crappy STL version, such as the default MSVC6 one (shudder).
[/actualContent]

[edited by - antareus on December 14, 2003 8:41:08 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
IIRC, std::sort won''t work on std::list because it expects bidirectional iterators.

std::list has bidirectional iterators.

Share this post


Link to post
Share on other sites
sort has a different form with list than with vectors. sort is a member function of std::list where vectors uses the function from <algorithm>

EDIT: grr, typo.

[edited by - nervo on December 14, 2003 8:56:49 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
It''s weird that std::list::sort doesn''t allow a functor argument.


std::list::sort does have a form that accepts a function object template parameter. (Though some compilers don''t implement it. Notably MSVC 6 either doesn''t implement it or implements it in a broken manner. I don''t remember which. Either way it''s not usable.)

Share this post


Link to post
Share on other sites
er, s/bidirectional/random access/g. Duh me. Still, std::sort won''t work.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Anyway, back to the original post. If you are using MSVC 6, and can''t use std::list::sort properly, one idea is to store the Shape pointers in a std::map. std::map allows you to specify the sorting property, and I think MSVC 6 implements it properly. Then when all the Shapes are registered, iterate through the map and move the Shape pointers to the list. You might be able to do the same thing with a std:riority_queue instead of a std::map as well. Or store the pointers in a std::vector, apply std::sort and then copy into the list. And so on.

Share this post


Link to post
Share on other sites
well im using VS 7.0,

i get the following error:


shapes.sort( < Shape* > ); //<- i get the compiler error here


error code:
error C2275: 'ShapeCMP

' : illegal use of this type as an expression
with
[
P=Shape *
]



and here is how the ShapeCMP struc is made:


template
class ShapeCMP : public binary_function< P, P, bool>
{
bool operator()(P p1, P p2) const {
return (*p1.nSize < *p2.nSize); }
};



Any ideas ?


[edited by - LogouT on December 15, 2003 5:17:53 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
IIRC, std::sort won''t work on std::list because it expects bidirectional iterators.


No, it needs Random Access.

Even if it didn''t, it''d still be better to use std::list::sort, because std::list::sort can take advantage of the ability to merge sort linked lists with no temporary storage (which requires some trickery with arrays, though I think can be implemented).

Share this post


Link to post
Share on other sites
You''ve got several errors with that code.

For one, ShapeCMP::operator() isn''t public. Also in ShapeCMP::operator(), there''s a precendence error with dereferencing the pointers. Finally, the call to std::list::sort() isn''t correct. Try:

shapes.sort<ShapeCMP<Shape *> >(ShapeCMP<Shape *>());

Share this post


Link to post
Share on other sites