One last question about linked lists
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?
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 * */}
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
linked list
head
position 1 hello
position 2 mail
position 3 viola
position 4 tortise
null
then I need the list.sort() to change the position to
head
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 :)
linked list
head
position 1 hello
position 2 mail
position 3 viola
position 4 tortise
null
then I need the list.sort() to change the position to
head
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 :)
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:
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement