Jump to content
  • Advertisement
Sign in to follow this  
polisasimo

One last question about linked lists

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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


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 :)

Share this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!