Archived

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

krez

how to sort an STL container with pointers?

Recommended Posts

i have an STL container (list, but i could use something else if necessary) full of pointers to objects. i want to sort it, but apparently when i call the "sort" function it is sorting by the pointers'' values (memopry addresses), not the objects pointed to. is there a way to get it to dereference the pointers for the sort call? i could get around it, but it would be a messy slow hack...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Not tested this.. but somrthing like


bool pointercompare(const your_pointer_type* p1, const your_pointer_type* p2)
{
return *p1 < * p2;
}




int main()
{
...
std::sort(something.begin(), something.end(), pointercompare);
...
}

Share this post


Link to post
Share on other sites
Make your own functor to pass to the sort function. Something like:


template<typename T>
class pointer_less
{
public:
bool operator() (const T *t1, const T *T2) { return *t1 < *t2; }
};

std::list<int *> myList;

...

std::sort(myList.begin(), myList.end(), pointer_less<int>());



How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
sneftel (or anyone else who knows all about these things):

i tried that, but i get the warning:
"template argument RandomAccessIterator passed to ''sort'' is a bi-directional iterator: random iterator required in function CTerrain::doPath()"

and then 16 or so other errors in "algorithm.cc" and ".h", relating to missing operators (+/-) for the iterators...

it also has a missing "copy_backwards", "std::__median", "__unguarded_partition", etc... i assume these are all things relating to it expecting a RandomAccessIterator; if so, how would i get one of those from ".begin()"?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by krez
i tried that, but i get the warning:
"template argument RandomAccessIterator passed to ''sort'' is a bi-directional iterator: random iterator required in function CTerrain::doPath()"
(.. snip)
how would i get one of those from ".begin()"?


quote:
my documentation
random access iterators permit values to be accessed by subscript, subtracted one from another (to yield the number of elements between their respective values), or modified by arithmetic operations, all in a manner similar to conventional pointers.



if you''re using a std::list, you simply cannot get a random access iterator. std::sort works with random access iterators. that''s just "The Way It Is" (.. if you want to know why, it''s for performance reasons).

so, it stands that you can''t use std::sort with a list::iterator - this is by design.

use the list::sort() member function, instead.


Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
Wow, what STL library are you using? (If it''s true, that is an excellent diagnostic)

um... whatever comes with the borland command-line compiler?
quote:
Are you attempting to sort a map or list? Map''s are stored sorted, and list have a member function to sort them.

yah, it''s a std::list...
quote:
Original post by Anonymous Poster
if you''re using a std::list, you simply cannot get a random access iterator.
...
use the list::sort() member function, instead.

alright, thanks!

i tried that to begin with, since i saw it had one, but that gave me errors as well... i''ll be back in a few minutes with an update.

Share this post


Link to post
Share on other sites
with the std::list member function sort, i get a different error ("cannot find match for blah blah blah...")... which means that i am getting one or more of the arguments wrong, i believe.

i tried with both the compare function (first AP), and the functor thing from sneftel. the comparator function compiles. but i get warnings about comparing signed and unsigned values (which i definitely am not doing)...

so, what is the proper syntax to use this function? i must be making a stupid mistake here or something...

Share this post


Link to post
Share on other sites
kinda sleepy but I'll give this a shot in the dark


#include <list>
#include <iostream>
#include <algorithm> // needed for the for_each algorithm

#include <stdlib.h>

using namespace std;


// just a simple functor for comparing pointers,

// since the operator () is templated you don't have

// to care about what kind of pointer is passed to it.

struct dereference_less
{
template <class T>
bool operator () (const T* lhs, const T* rhs) const
{
return *lhs < *rhs;
}
};


// just a simple functor for cout'ing pointers,

// since the operator () is templated you don't have

// to care about what kind of pointer is passed to it.

struct dereference_cout
{
template <class T>
void operator () (T* tp)
{
cout << *tp;
}
};


int main()
{
list<int*> l;

for(int i=0; i < 10; i++)
l.push_back( new int( 9-i ) );

cout << "List created: ";
for_each(l.begin(), l.end(), dereference_cout());
cout << endl;


l.sort( dereference_less() );


cout << "The list is now sorted: ";
for_each(l.begin(), l.end(), dereference_cout());
cout << endl;


std::cin.get();

return 0;
}



I ran it and it works fine!

To tired to make it better... goonight

}-- Programmer/Gamer/Dreamer --{

[edited by - Seriema on October 11, 2003 9:33:34 AM]

Share this post


Link to post
Share on other sites
Well, this is off the top of my head, so there'll most likely be a few errors - I have no compiler on this 'puter. You might have to play around with it.

For the comparison:

class pointer_less
{
public:
template <typename T>
bool operator()(const T* lhs, const T* rhs) const {
return *lhs < *rhs;
}
};

Something like this for generic outputting:

template <typename CharT = char, typename Traits = std::char_traits<CharT> >
class pointer_print
{
public:
typedef std::basic_ostream<CharT, Traits> ostream_type;
typedef std::basic_string<CharT, Traits> string_type;

public:
pointer_print(ostream_type& out)
: os_(out) {}
pointer_print(ostream_type& out, const string_type& separate)
: os_(out), sep_(separate) {}
pointer_print(const pointer_print& rhs)
: os_(rhs.os_), sep_(rhs.sep_) {}

template <typename T>
void operator()(const T* obj) {
os_ << *obj << sep_;
}

private:
ostream_type& os_;
string_type sep_;
};

For deleting the objects from the list:

class single_delete
{
public:
template <typename T>
void operator()(T*& ptr) const {
delete ptr;
ptr = 0;
}
};

And a little example test program:

int main()
{
std::list<int*> L;
for (int i = 10; i > 0; --i)
L.push_back( new int(i) );

std::cout << "Initial list:" << std::endl << std::endl;
std::for_each( L.begin(), L.end(), pointer_print(std::cout, "\n") );

L.sort( pointer_less() );

std::cout << std::endl
<< "Sorted list: " << std::endl << std::endl;
std::for_each( L.begin(), L.end(), pointer_print(std::cout, "\n") );

std::for_each( L.begin(), L.end(), single_delete() );
L.clear();

std::cout << "Press any key to continue...";
std::cin.get();
return 0;
}


Edit: Something tells me the compiler wouldn't like "templaete".

[ Google || Start Here || ACCU || STL || Boost || MSDN || GotW || CUJ || MSVC++ Library Fixes || BarrysWorld || E-Mail Me ]

[edited by - Lektrix on October 12, 2003 4:29:27 AM]

Share this post


Link to post
Share on other sites
ah, after sleeping and typing it again from scratch it works, thanks to you useful peoples... thanks a lot!

Share this post


Link to post
Share on other sites
Oh, and here's a version of pointer_print that you can also use like an std::ostream_iterator, but for pointers (you could use it with std::copy).

template <typename CharT = char, typename Traits = std::char_traits<CharT> >
class pointer_print
{
public:
typedef std::basic_ostream<CharT, Traits> ostream_type;
typedef std::basic_string<CharT, Traits> string_type;

public:
pointer_print(ostream_type& out)
: os_(out) {}
pointer_print(ostream_type& out, const string_type& separate)
: os_(out), sep_(separate) {}
pointer_print(const pointer_print& rhs)
: os_(rhs.os_), sep_(rhs.sep_) {}

template <typename T>
void operator()(const T* obj) {
os_ << *obj << sep_;
}

template <typename T>
pointer_print& operator=(const T* obj) {
os_ << *obj << sep_;
return *this;
}

pointer_print& operator*() {
return *this;
}

pointer_print& operator++() {
return *this;
}

pointer_print& operator++(int) {
return *this;
}

private:
ostream_type& os_;
string_type sep_;
};


[ Google || Start Here || ACCU || STL || Boost || MSDN || GotW || CUJ || MSVC++ Library Fixes || BarrysWorld || E-Mail Me ]

[edited by - Lektrix on October 12, 2003 4:30:04 AM]

Share this post


Link to post
Share on other sites
I think that the borland bcc comes with STLport from memory (i know it does in 6 not sure about the 5.5 version that came with the command line compiler)

quote:

um... whatever comes with the borland command-line compiler?


Share this post


Link to post
Share on other sites
well, at the top of "vector.h" it is copyrighted by Hewlett-Packard (1994) and Rogue Wave Software(1994-99)...

Share this post


Link to post
Share on other sites