How to order strings case-insensitively (not lexicographically)?

Question

I'm attempting to order a list input from a file alphabetically (not lexicographically). So, if the list were:

C d A b

I need it to become: A b C d

Not the lexicographic ordering: A C b d

I'm using string variables to hold the input, so I'm looking for some way to modify the strings I'm comparing to all uppercase or lowercase, or if there's some easier way to force an alphabetic comparison, please impart that wisdom. Thanks!

I should also mention that we are limited to the following libraries for this assignment: iostream, iomanip, fstream, string, as well as C libraries, like cstring, cctype, etc.

[This question](http://stackoverflow.com/questions/313970/stl-string-to-lower-case) looks great for what you need, but the arbitrary restriction of libraries seems to force you write a for loop with `toupper`/`tolower` to do the job. — Prashant Kumar, Nov 25 '13 at 18:58
Thanks for pointing me to that, but it looks like I'd need access to the algorithm or boost libraries to make use of those suggestions. It looks like I'm just going to have to defeat this problem via some very tedious method of character extraction and toppering for each string. — Victor Brunell, Nov 25 '13 at 19:05
Note on vocabulary: alphabetical = lexicographic (or, more precisely, lexicographic order is a generalisation of alphabetical order). What you want is known as “case insensitive”. — Konrad Rudolph, Nov 25 '13 at 19:06
Thanks for the vocab tip. In that case, I think what I need is "case insensitive" ordering. The lexicographic ASCII ordering places uppercase letters before lowercase letters. So, 'Z' comes before 'a'. But I need to sort a list so that 'a' comes before 'Z'. — Victor Brunell, Nov 25 '13 at 19:19

score 1 · Answer 1 · answered Nov 25 '13 at 19:01

You don't have to modify the strings before sorting. You can sort them in place with a case-insensitive single character comparator and std::sort:

bool case_insensitive_cmp(char lhs, char rhs) {
  return ::toupper(static_cast<unsigned char>(lhs) < 
         ::toupper(static_cast<unsigned char>(rhs);
}

std::string input = ....;
std::sort(input.begin(), input.end(), case_insensitive_cmp);

bames53 · Accepted Answer · 2014-04-15T21:05:36.060

It looks like I'm just going to have to defeat this problem via some very tedious method of character extraction and toppering for each string.

Converting the individual strings to upper case and comparing them is not made particularly worse by being restricted from using algorithm, iterator, etc. The comparison logic is about four lines of code. Even though it would be nice not to have to write those four lines having to write a sorting algorithm is far more difficult and tedious. (Well, assuming that the usual C version of toupper is acceptable in the first place.)

Below I show a simple strcasecmp() implementation and then put it to use in a complete program which uses restricted libraries. The implementation of strcasecmp() itself doesn't use restricted libraries.

#include <string>
#include <cctype>
#include <iostream>

void toupper(std::string &s) {
  for (char &c : s)
    c = std::toupper(c);
}

bool strcasecmp(std::string lhs, std::string rhs) {
  toupper(lhs); toupper(rhs);
  return lhs < rhs;
}

// restricted libraries used below

#include <algorithm>
#include <iterator>
#include <vector>

// Example usage:
//  > ./a.out <<< "C d A b"
//  A b C d
int main() {
  std::vector<std::string> input;
  std::string word;
  while(std::cin >> word) {
    input.push_back(word);
  }

  std::sort(std::begin(input), std::end(input), strcasecmp);
  std::copy(std::begin(input), std::end(input),
            std::ostream_iterator<std::string>(std::cout, " "));
  std::cout << '\n';
}

I'm not familiar with the for-each syntax. Does for( char &c : s ) mean "for each character in the string s"? — Victor Brunell, Nov 25 '13 at 20:14
@Caulibrot Yes. It's C++11 syntax and it does the same thing as `for (int i=0; i — bames53, Nov 25 '13 at 21:25

score 1 · Answer 3 · answered Apr 22 '22 at 14:36

1

std::vector<string> vec {"A", "a", "lorem", "Z"};    
std::sort(vec.begin(),
          vec.end(),
          [](const string& s1, const string& s2) -> bool {
            return strcasecmp(s1.c_str(), s2.c_str()) < 0 ? true : false;
          });

answered Apr 22 '22 at 14:36

Udit Gupta

11
2

score 0 · Answer 4 · answered Nov 25 '13 at 18:46

0

Use strcasecmp() as comparison function in qsort().

answered Nov 25 '13 at 18:46

olegarch

3,670
1
20
19

Is strcasecmp() part of any of the libraries mentioned above? When I Google it, it looks like it's not part of any of the standard libraries, meaning it's off limits for my assignment--which is a real bummer. – Victor Brunell Nov 25 '13 at 18:54
1

Correct, `strcasecmp` is POSIX, not part of the C++ standard. – Prashant Kumar Nov 25 '13 at 18:54

score 0 · Answer 5 · answered Nov 25 '13 at 18:49

0

I am not completely sure how to write it, but what you want to do is convert the strings to lower or uppercase.

If the strings are in an array to begin with, you would run through the list, and save the indexes in order in an (int) array.

answered Nov 25 '13 at 18:49

Evan Carslake

2,267
15
38
56

1

I'm holding them in variables of type string. I was hoping to find a simple way to force alphabetic ordering. I know I could do something like use the at() function to extract characters from the string and toupper() them, but that seems like a lot of work and complication. – Victor Brunell Nov 25 '13 at 18:52

score 0 · Answer 6 · answered Nov 25 '13 at 19:03

0

If you're just comparing letters, then a terrible hack which will work is to mask the upper two bits off each character. Then upper and lower case letters fall on top of each other.

answered Nov 25 '13 at 19:03

woolstar

5,063
20
31

By mask, do you mean to use a bitwise mask and switch the bits to the opposite values? – Victor Brunell Dec 08 '13 at 02:15
Yes you could do `c = 0x40 | ( c & 0x1f ) ;` – woolstar Dec 08 '13 at 06:53

How to order strings case-insensitively (not lexicographically)?

6 Answers6