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();

Jeff wrote:
[color=blue]
> 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();[/color]

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());

On Wed, 17 Aug 2005 01:06:13 +0200, Rolf Magnus <ramagnus@t-online.de>
wrote:
[color=blue]
>
>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());[/color]

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

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

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.

Jeff wrote:[color=blue]
> On Wed, 17 Aug 2005 01:06:13 +0200, Rolf Magnus <ramagnus@t-online.de>
> wrote:
>
>[color=green]
>>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());[/color]
>
>
> I'm using VC++ 6.0. Can you tell me how to make this compile?
> thanks[/color]

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

cipherpunk@gmail.com wrote:[color=blue]
> 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.[/color]

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

Jeff wrote:[color=blue]
> 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[/color]

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

Greg wrote:
[color=blue]
> 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 );
> ...
> }[/color]

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

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

[color=blue]
>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[/color]

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

Jeff wrote:[color=blue]
> [...]
> I get this compile error. Maybe M$ implentation of <list> is broken,[/color]

Yes, it is. And the reason is simple: very bad support in VC++ v6 for
member templates.
[color=blue]
> mentioned in a previous post. I'm using MS VC++ 6.0
>
> [..][/color]

Upgrade to 7.1

On Wed, 17 Aug 2005 15:28:30 -0400, Victor Bazarov
<v.Abazarov@comAcast.net> wrote:
[color=blue]
>Jeff wrote:[color=green]
>> [...]
>> I get this compile error. Maybe M$ implentation of <list> is broken,[/color]
>
>Yes, it is. And the reason is simple: very bad support in VC++ v6 for
>member templates.
>[color=green]
>> mentioned in a previous post. I'm using MS VC++ 6.0
>>
>> [..][/color]
>
>Upgrade to 7.1[/color]

Thanks. That is exactly what I will do.

Jeff wrote:[color=blue]
> On 17 Aug 2005 02:25:34 -0700, "Greg" <greghe@pacbell.net> wrote:
>[color=green]
>>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[/color]
>
>
> 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[/color]

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

Stefan