post  How to sort a string vector

tnjones (38)   Link to this post
Hello,
I have never worked with vectors but is finding them not difficult. However I am trying to sort a string vector. Actually, the vector is being sorted if all the strings start with the a capital/lower letter. For example if the vector consists of see, can, be the output is be, can ,see(which is correct), but if the vector consists of See, Can, be the output is Can, See, be(incorrect).Is there any way that the vector can be sorted correctly regardless rather the frst letter is lower/capital without changing each string to Upper/lower. Any help will be greatly appreciated!!!
exception (323)   Link to this post
You would have to provide a new comparison operator for std::sort (which you are using, i presume).
One interface for sort is:
template <class RAI, class StrictWeakOrdering> void sort(RAI first, RAI last, StrictWeakOrdering comp)
(where RAI is a random access iterator). You have to provide a 'comp' parameter which behaves case insensitive like you want (note, though, that it has to be a model for the concept Strict Weak Ordering, so no behavior like '<=' but like '<' is required)
Another possibility would be to change the char_traits (a std::string is typedef'ed as something like
std::basic_string<char, char_traits<char>, allocator<char> >)
so you can provide your own char_traits with another operator< and then use the other sort interface without comp, since the string operator< is then used. This does, however, change the type of the string, so
1
2
 
basic_string<char, my_char_traits<char>, allocator<char> > s = "Hello, World";
std::cout<<s<<std::endl;

does *not* work until you provide an operator<< for the string with your char_traits.
tnjones (38)   Link to this post
Thanks!! However, I am not fully understanding what you are saying to do. Below is my code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
vector<string> vec;
vec.push_back("See"); vec.push_back("be"); vec.push_back("can");
sort(vec.begin(), vec.end());
for (int i = 0; i < vec.size(); ++i)
cout << vec[i] << ' ';
cout << endl;
return 0;
}
How would I change the char traits?Once again thanks!!

exception (323)   Link to this post
The string uses the character traits class to determine the behavior of a character. You can write:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct case_insensitive_chartraits : public std::char_traits<char>
{
  static bool eq(char c1, char c2) { return toupper(c1) == toupper(c2); }
  // same for 'lt' (less than), 'compare' and 'find' - that should be all you need for case insensitivity
  // See the default implementation or your preferred C++ book on the signatures and requirements
};

typedef std::basic_string<char, case_insensitive_chartraits> case_insensitive_string;

case_insensitive_string s1, s2;
s1 = "Hello";
s2 = "hello";
assert(s1 == s2);

Do *NOT* repeat, *NOT* use char_traits polymorphically, although public inheritance was used. This would be *EVIL* since std::char_traits<char> has no virtual destructor. However, there is little reason to do so, so everything is fine. Also, resist the temptation (?) to define anything in namespace std; this is not legal.

PS
1
2
 
for (int i = 0; i < vec.size(); ++i)
cout << vec[i] << ' ';


This can be done even easier, thanks to std::ostream_iterator:
  
std::copy(vec.begin(), vec.end(), std::ostream_iterator<std::string>(std::cout, " "));
Last edited on
satm2008 (151)   Link to this post
As you said you have never worked with vectors before, and a simple linked list of strings would work, if you dont have to use vectors for your purpose, I would suggest you to write a simple linked list to place the node in a sorted order.
With a help of strcmp() or string.compare() you could write a nice linked list program.
Check it out. Good luck :)
Mitsakos (343)   Link to this post
You have to provide a 'comp' parameter which behaves case insensitive like you want (note, though, that it has to be a model for the concept Strict Weak Ordering, so no behavior like '<=' but like '<' is required)


I think that this is the easiest method of doing it, especially if you are new to c++ and the STL.

As exception mentioned one interface of the sort() function is:
void sort(RAI first, RAI last, StrictWeakOrdering comp)
That means that except from the start and end position iterators, it can also accept a function name which will provide it a Strict Weak Ordering.

So, you can make your own function for comparing the strings ( classes, structs, or whatever you want ).

I did it like that:
1
2
3
4
5
6
7
8
9
10
 
bool stringCompare( const string &left, const string &right ){
   for( string::const_iterator lit = left.begin(), rit = right.begin(); lit != left.end() && rit != right.end(); ++lit, ++rit )
      if( tolower( *lit ) < tolower( *rit ) )
         return true;
      else if( tolower( *lit ) > tolower( *rit ) )
         return false;
   if( left.size() < right.size() )
      return true;
   return false;
}


and the call to the sort() function was:
sort( strs.begin(), strs.end(), stringCompare );

To explain a little my function:
The for-loop will run through the elements of the strings and will compare them by converting each letter to lower case.
If the strings have different sizes then the for-loop will check only the char positions they both have (so the iterators won't go offlimits).

If both strings are identical after the end of the loop then it will check the size. If the size() of the left string is bigger than the size of the right string it will return true so they can change positions in the sort.

Hope this helps.

[EDIT]
@satm2008
Telling him to use a simple linked list wont solve his problem, he will still has to deal with it. Also he will have to make his own sorting function and much more that vectors have already...
Last edited on

This topic is archived - New replies not allowed.