Sorting a list of objects

[Jeff]

Hello,

I'm finishing a speech recognition jukebox
(http://intelligentjukebox.com/) I have a very basic template
question. I can't find any good examples of what I want to do. I
could write my own sort function faster than I could find a good
reference with examples on the c++ template library.

Can someone tell me how to define the "<" operator so I can use the
sort function for the list template. I want to sort Song objects in
a-z (descending) order by m_filename.

thanks

Here is my code:
//------------------------------------------------------------------------------

class Song
{
public:
Album* m_pAlbum; // make it easy to get the album
string m_name; //display name
string m_filename;
};

list<Song*> *pSongsList; // holds all the songs for this album

//------------------------------------------------------------------------------

I want to this function call to work:

pSongsList->sort();

[Rolf Magnus]

Jeff wrote:

Hello,

I'm finishing a speech recognition jukebox
(http://intelligentjukebox.com/) I have a very basic template
question. I can't find any good examples of what I want to do. I
could write my own sort function faster than I could find a good
reference with examples on the c++ template library.

Can someone tell me how to define the "<" operator so I can use the
sort function for the list template. I want to sort Song objects in
a-z (descending) order by m_filename.

thanks

Here is my code:
//------------------------------------------------------------------------------

class Song
{
public:
Album* m_pAlbum; // make it easy to get the album
string m_name; //display name
string m_filename;
};

list<Song*> *pSongsList; // holds all the songs for this album

//------------------------------------------------------------------------------

I want to this function call to work:

pSongsList->sort();

You can't, because that function call would use operator< on the element
type, which is pointer to Song. You cannot change the built-in behavior of
pointers, therefore you cannot overload that operator<.
What you can do is specify an alternative comparison:

struct song_cmp
{
bool operator()(Song* lhs, Song* rhs) const
{
return lhs->m_filename < rhs->m_filename;
}
};

pSongList.sort(song_cmp());

[Jeff]

On Wed, 17 Aug 2005 01:06:13 +0200, Rolf Magnus <ra******@t-online.de>
wrote:

You can't, because that function call would use operator< on the element
type, which is pointer to Song. You cannot change the built-in behavior of
pointers, therefore you cannot overload that operator<.
What you can do is specify an alternative comparison:

struct song_cmp
{
bool operator()(Song* lhs, Song* rhs) const
{
return lhs->m_filename < rhs->m_filename;
}
};

pSongList.sort(song_cmp());

I'm using VC++ 6.0. Can you tell me how to make this compile?
thanks
-------------------------------
line 95:
m_pSongsList->sort(song_cmp());
Compiling...
music.cpp
J:\home\jeff\src\intelligent_jukebox\dev\intellimu sic\current\music.cpp(95)
: error C2664: 'void __thiscall std::list<class Song *,class
std::allocator<class Song *> >::sort(struct std::greater<class Song
*>)' : cannot convert parameter 1 from 'stru
ct song_cmp' to 'struct std::greater<class Song *>'
No constructor could take the source type, or constructor
overload resolution was ambiguous

[Jeff]

In five minutes I wrote a bubble sort which added less than 1/10 of a
second to the startup time of my program for 14,000 songs. Most
albums have less than 20 songs.

I spent more than two hours trying to figure out the retarded notation
to sort a list and failed. Apparently there are no clear examples of
how to sort a list using your own comparison function. Sometimes I
really hate c++.

thanks for the help anyway though

int n;
bool bSorted = false;
Song* tmpSong;

while (false == bSorted)
{
bSorted = true;
for (n = 0; n < m_totalSongs-1; n++)
{
if ( (m_pSongsArray[n])->m_filename >
(m_pSongsArray[n+1])->m_filename )
{
// swap values
tmpSong = m_pSongsArray[n];
m_pSongsArray[n] = m_pSongsArray[n+1];
m_pSongsArray[n+1] = tmpSong;
bSorted = false;
}
}
} // end while

[cipherpunk]

The problem is std::sort requires random-access iterators, which
std::list lacks.

According to my copy of Plauger's _The C++ Standard Template Library_,
std::stable_sort should accept bidirectional iterators (see pg. 160).
According to Josuttis (pg. 397), std::stable_sort requires
random-access iterators. I don't know what the Standard itself says,
unfortunately.

Still, it may be worth trying std::stable_sort, to see if your system
supports it. G++ 4.0 doesn't.

Other options: copy the list into a vector and then sort it. Or write
your own out-of-place mergesort function, and do it the LISPy way.
Either way, you should be able to get roughly O(n lg n) performance
without too much headache. E.g.:

=====

int main()
{
int vals[] = { 2, 1, 5, 6, 4, 9, 8, 7, 3 };
list<int> l(vals, vals + 9);
vector<int> v(l.begin(), l.end());
sort(v.begin(), v.end());
l.assign(v.begin(), v.end());
copy(l.begin(), l.end(), ostream_iterator<int>(cout, "\t"));
cout << endl;
return 0;
}

=====

That doesn't seem to be too obnoxiously bad to me.

[Stefan Näwe]

Jeff wrote:

On Wed, 17 Aug 2005 01:06:13 +0200, Rolf Magnus <ra******@t-online.de>
wrote:

You can't, because that function call would use operator< on the element
type, which is pointer to Song. You cannot change the built-in behavior of
pointers, therefore you cannot overload that operator<.
What you can do is specify an alternative comparison:

struct song_cmp
{
bool operator()(Song* lhs, Song* rhs) const
{
return lhs->m_filename < rhs->m_filename;
}
};

pSongList.sort(song_cmp());

I'm using VC++ 6.0. Can you tell me how to make this compile?
thanks

That's easy...NOT!
It's one of those M$-VC++ stupidities.
I solved it by a template spezialization for std::greater<Song*>
(Hint: Search for _Pr3 in include file 'list' to see what's going on
there...)

<code>

namespace std
{
template<>
struct greater<Song*>
{
bool operator()(const Song* lhs, const Song* rhs) const
{
return lhs->m_filename < rhs->m_filename;
}
};
}
....
....
pSongList->sort(std::greater<Song*>());

</code>

That works for me.

HTH

Stefan

[Greg]

ci********@gmail.com wrote:

The problem is std::sort requires random-access iterators, which
std::list lacks.

According to my copy of Plauger's _The C++ Standard Template Library_,
std::stable_sort should accept bidirectional iterators (see pg. 160).
According to Josuttis (pg. 397), std::stable_sort requires
random-access iterators. I don't know what the Standard itself says,
unfortunately.

Still, it may be worth trying std::stable_sort, to see if your system
supports it. G++ 4.0 doesn't.

Other options: copy the list into a vector and then sort it. Or write
your own out-of-place mergesort function, and do it the LISPy way.
Either way, you should be able to get roughly O(n lg n) performance
without too much headache. E.g.:

=====

int main()
{
int vals[] = { 2, 1, 5, 6, 4, 9, 8, 7, 3 };
list<int> l(vals, vals + 9);
vector<int> v(l.begin(), l.end());
sort(v.begin(), v.end());
l.assign(v.begin(), v.end());
copy(l.begin(), l.end(), ostream_iterator<int>(cout, "\t"));
cout << endl;
return 0;
}

=====

That doesn't seem to be too obnoxiously bad to me.

The drawback with using any of these suggestions to sort a std::list is
that iterators of the list may no longer point to the same values as
they did before the list was sorted.

For that reason std::list provides two sort() methods of its own, one
that sorts the list in an ascending order, and another that sorts it
using a user defined predicate for comparing elements. Clearly one of
these two std::list member functions is the preferred way to sort
elements in a std::list. Both of these methods guarantee not to have
changed any of the list's iterators once the list has been sorted.

Greg

[Greg]

Jeff wrote:

In five minutes I wrote a bubble sort which added less than 1/10 of a
second to the startup time of my program for 14,000 songs. Most
albums have less than 20 songs.

I spent more than two hours trying to figure out the retarded notation
to sort a list and failed. Apparently there are no clear examples of
how to sort a list using your own comparison function. Sometimes I
really hate c++.

thanks for the help anyway though

int n;
bool bSorted = false;
Song* tmpSong;

while (false == bSorted)
{
bSorted = true;
for (n = 0; n < m_totalSongs-1; n++)
{
if ( (m_pSongsArray[n])->m_filename >
(m_pSongsArray[n+1])->m_filename )
{
// swap values
tmpSong = m_pSongsArray[n];
m_pSongsArray[n] = m_pSongsArray[n+1];
m_pSongsArray[n+1] = tmpSong;
bSorted = false;
}
}
} // end while

Actually, to use list::sort you can just provide the name of a function
to perform the comparison:

bool CompareSongs( const Song * leftSong, const Song * rightSong)
{
return leftSong->m_filename < rightSong->m_filename;
}

int main()
{
...
pSongsList->sort( CompareSongs );
...
}

Greg

[Rolf Magnus]

Greg wrote:

Actually, to use list::sort you can just provide the name of a function
to perform the comparison:

bool CompareSongs( const Song * leftSong, const Song * rightSong)
{
return leftSong->m_filename < rightSong->m_filename;
}

int main()
{
...
pSongsList->sort( CompareSongs );
...
}

Yes. However, a function object (see my post with the compare struct) is
usually faster.

[Jeff]

On 17 Aug 2005 02:25:34 -0700, "Greg" <gr****@pacbell.net> wrote:

Actually, to use list::sort you can just provide the name of a function
to perform the comparison:

bool CompareSongs( const Song * leftSong, const Song * rightSong)
{
return leftSong->m_filename < rightSong->m_filename;
}

int main()
{
...
pSongsList->sort( CompareSongs );
...
}

Greg

I get this compile error. Maybe M$ implentation of <list> is broken,
mentioned in a previous post. I'm using MS VC++ 6.0

: error C2664: 'void __thiscall std::list<class Song *,class
std::allocator<class Song *> >::sort(struct std::greater<class Song
*>)' : cannot convert parameter 1 from 'bool
(const class Song *,const class Song *)' to 'struct
std::greater<class Song *>'
No constructor could take the source type, or constructor
overload resolution was ambiguous

[Victor Bazarov]

Jeff wrote:

[...]
I get this compile error. Maybe M$ implentation of <list> is broken,
Yes, it is. And the reason is simple: very bad support in VC++ v6 for
member templates.
mentioned in a previous post. I'm using MS VC++ 6.0

[..]

Upgrade to 7.1

[Jeff]

On Wed, 17 Aug 2005 15:28:30 -0400, Victor Bazarov
<v.********@comAcast.net> wrote:

Jeff wrote:

[...]
I get this compile error. Maybe M$ implentation of <list> is broken,

Yes, it is. And the reason is simple: very bad support in VC++ v6 for
member templates.

mentioned in a previous post. I'm using MS VC++ 6.0

[..]

Upgrade to 7.1

Thanks. That is exactly what I will do.

[Stefan Näwe]

Jeff wrote:

On 17 Aug 2005 02:25:34 -0700, "Greg" <gr****@pacbell.net> wrote:

Actually, to use list::sort you can just provide the name of a function
to perform the comparison:

bool CompareSongs( const Song * leftSong, const Song * rightSong)
{
return leftSong->m_filename < rightSong->m_filename;
}

int main()
{
...
pSongsList->sort( CompareSongs );
...
}

Greg

I get this compile error. Maybe M$ implentation of <list> is broken,
mentioned in a previous post. I'm using MS VC++ 6.0

: error C2664: 'void __thiscall std::list<class Song *,class
std::allocator<class Song *> >::sort(struct std::greater<class Song
*>)' : cannot convert parameter 1 from 'bool
(const class Song *,const class Song *)' to 'struct
std::greater<class Song *>'
No constructor could take the source type, or constructor
overload resolution was ambiguous

I already answered that in another post in this thread.
It *is* possible with M$-VC++ 6.0

Stefan