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

## Recommended Posts

Any ideas on how to sort a linked list class made up of strings alphabetically? for example strings list1 hello mail viola tortise needs to read hello mail tortise viola I think I know how to change the position of the items but how can I compare one item to another and determine which of the two leads the other?

##### Share on other sites
If you're using the standard library as I suggested in your last thread, it'd be a simple matter of:

#include <algorithm>#include <list>#include <iostream>#include <iterator>#include <string>using namespace std;int main () {    list< string > example;    example.push_back( "hello" );    example.push_back( "mail" );    example.push_back( "viola" );    example.push_back( "tortise" );    example.sort();    //print out every example on a new line:    copy( example.begin() , example.end() , ostream_iterator< string >( cout , "\n" ) );    cout << flush;    /* this will print out, in this order:     *     * hello     * mail     * tortise     * viola     *     */}

##### Share on other sites
I need to actually change the postion of where the items are linked to be alphabetical for instance ... and I am new please bear with me on this one

position 1 hello
position 2 mail
position 3 viola
position 4 tortise
null

then I need the list.sort() to change the position to

position 1 hello
position 2 mail
position 3 tortise
position 4 viola
null

the problem is comparing tortise to viola and determing which comes first. I can use the insert and remove function I wrote to get this done once I determine how to compare one element to the other.

Sorting a linked list made up of integers is relatively easy. char and char strings is where i get lost :)

##### Share on other sites
Else, look at the 'strcmp' function.

##### Share on other sites
If you use std::string, it will in fact sort just the way you've described.

list.sort can also take an optional argument (a functor) which will describe exactly how you wish to sort. To sort numbers from greater-to-smaller instead of the default smaller-to-greater, for example, one would use:

list.sort( std::greater< int >() );

The above could also be used to sort strings from Z to A rather than A to Z.

Of note is that the lexographical comparison will be case-sensitive, all capital entries will come before lowercase. For a case insensitive sort one should provide a custom functor. Borrowing one to help our implementation from here, I arrive at this example:

struct ToLower{    ToLower(std::locale const& l) : loc(l) {;}    char operator() (char c) const  { return std::tolower(c,loc); }private:    std::locale const& loc;};class CompareCaseInsensitive {    std::locale const& locale;public:    CompareCaseInsensitive(std::locale const& locale)        : locale(locale)    {    }    template < typename string_t >    bool operator()( const string_t & lhs , const string_t & rhs ) const {        string_t lowercase_lhs = lhs;        string_t lowercase_rhs = rhs;        std::transform( lowercase_lhs.begin() , lowercase_lhs.end() , ToLower( locale ) );        std::transform( lowercase_rhs.begin() , lowercase_rhs.end() , ToLower( locale ) );        if ( lowercase_lhs == lowercase_rhs ) { //if case is only difference...            return lhs < rhs; //... compare by case ...        } else { //... otherwise ...            return lowercase_lhs < lowercase_rhs; //... compare without case        }    }};int main () {    std::list< std::string > example;    ...    example.sort( CompareCaseInsensitive( std::locale() ) ); //compare using the default locale}

Notes: I went a bit overboard with this example by introducing locales and the like, so it will work with weird languages :-). Also, CompareCaseInsensitive is a misdominer - it will sort by case, but only if they match letter for letter (e.g. "Mike" will come before "mike" but not "mikda")

[Edited by - MaulingMonkey on August 1, 2005 12:16:54 AM]

##### Share on other sites
Thanks I am starting to see the light

1. 1
2. 2
JoeJ
18
3. 3
4. 4
frob
12
5. 5

• 13
• 16
• 13
• 20
• 13
• ### Forum Statistics

• Total Topics
632188
• Total Posts
3004650

×