C++ sorting - special characters after normal letters

Question

I have a vector of strings which is holding strings like

BB
aA
12
b
AA
&
[
**
1

Using the default sort() with C++ I am given this sorted list

&
**
1
12
AA
BB
[
aA
b

Instead of that, I need it to be ordered with the normal letters A, a, B, b.... coming first, those followed by "special" characters like 0-9, *, [, , ~, !.... in their normal ASCII order.

I really have no idea how to go about changing the way that the vector is sorted in order to make sure that it is all in that order. Thanks.

Answer 1

You can specify your own function that compares values for the sort to use.

bool myfunction(std::string a, std::string b){ ... }

std::sort(data.begin(), data.end(), myfunction);

Using myfunction you can specify the order you want. Here is more information about sort:

http://www.cplusplus.com/reference/algorithm/sort/

Answer 2

Another untested solution.

If I missed a case, I'm sure someone will point it out, but here goes:

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    std::vector <std::string> StringVect = { "BB", "aA", "12", "b", "AA", "&", "[", "**", "1" };

    std::sort(StringVect.begin(), StringVect.end(), []
        (const std::string& s1, const std::string& s2)
    {
        if (s1.empty() || s2.empty()) 
           return s1 < s2;

        // a convenience array                             
        bool ac[] = { isalpha(s1[0]), isalpha(s2[0]),
                      isdigit(s1[0]), isdigit(s2[0]),
                      !isalnum(s1[0]), !isalnum(s2[0]) };

        // If both strings start with the same type, then return 
        // s1 < s2
        if ((ac[0] && ac[1]) || // if both alpha strings
            (ac[2] && ac[3]) || // if both digit strings
            (ac[4] && ac[5]))   // if both non-alphanumeric strings
            return s1 < s2;

        // if first string is alpha, or second string is not alphanumeric
        // the strings are in order, else they are not
        return (ac[0] || ac[5]);
    });
    copy(StringVect.begin(), StringVect.end(), ostream_iterator<string>(cout, "\n"));
}

Basically, the condition says this:

1) If one of the strings are empty, then return s1 < s2

2) If both strings start with the same character type, just return s1 < s2

3) If the first string starts with an alpha, or if the second string is not an alphanumeric, then the strings are in order and return true, else return false. The trick here is to realize that step 2) eliminated all combinations of both strings being of the same type, so our check at the step 3) stage becomes simplified.

Live example: http://ideone.com/jxxhIY

Edit:

If you are checking for case-insensitive strings, then you need to change the code, and add the case-insensitive check. I won't add the code, since there are multiple ways, both with their respective advantages and disadvantages, of doing a case-insensitive compare.

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    std::vector <std::string> StringVect = { "BB", "aA", "12", "b", "AA", "&", "[", "**", "1" };

    std::sort(StringVect.begin(), StringVect.end(), []
        (const std::string& s1, const std::string& s2)
    {
        if (s1.empty() || s2.empty()) 
           return s1 < s2;

        // a convenience array                             
        bool ac[] = { isalpha(s1[0]), isalpha(s2[0]),
                      isdigit(s1[0]), isdigit(s2[0]),
                      !isalnum(s1[0]), !isalnum(s2[0]) };

        // If both strings start with the same type, then return 
        // s1 < s2
        if ((ac[2] && ac[3]) || (ac[4] && ac[5]))
            return s1 < s2;

        // case insensitive 
        if (ac[0] && ac[1]) // both strings are alpha
           return myCaseInsensitiveComp(s1, s2);  //returns true if s1 < s2, false otherwise

        // if first string is alpha, or second string is not alphanumeric
        // the strings are in order, else they are not
        return (ac[0] || ac[5]);
    });
    copy(StringVect.begin(), StringVect.end(), ostream_iterator<string>(cout, "\n"));
}

Again, the myCaseInsensitiveComp is a stub that you should fill in with a function that accomplishes this goal. For a link, see this:

Case insensitive string comparison in C++

Answer 3

Anyway, you need implement your own comparison logic for it, and use it with sort.

(1) You can give a comparison function object to sort, and implement your own comparison(less than) logic in it, such as:

struct my_comparison {
    bool operator()(const string &a, const string &b) {
        // implement the less than logic here
    }
}

and then:

sort(v.begin(), v.end(), my_comparison());

Reference: http://en.cppreference.com/w/cpp/algorithm/sort

(2) You can implement your own char_traits<char> to make a special string which uses the special comparison logic. Such as:

struct my_char_traits : public char_traits<char> 
              // just inherit all the other functions
              // that we don't need to replace
{
    static bool eq(char c1, char c2) { 
        // implement the comparison logic here
    }
    static bool lt(char c1, char c2)
        // implement the comparison logic here
    }
    static int compare(const char* s1, const char* s2, size_t n)
        // implement the comparison logic here
    }
};

And then:

typedef basic_string<char, my_char_traits> my_string;
vector<my_string> v;
// ...
sort(v.begin(), v.end());

Reference: http://en.cppreference.com/w/cpp/string/char_traits

Answer 4

Disclaimer: Untested code.

Here's an implementation of a compare function that should work. The crux of the solution is to re-encode into an array the values corresponding to the characters whose order you want to be changed in the compare function.

void initializeEncoding(char encoding[])
{
   for (int i = 0; i < 256; ++i )
   {
      encoding[i] = i;
   }

   // Now re-encode for letters, numbers, and other special characters.
   // The control characters end at 31. 32 == ' ', the space character.

   int nextIndex = 32;

   // Re-encode the uppercase letters.
   for ( int c = 'A'; c <= 'Z'; ++c, ++nextIndex )
   {
      encoding[c] = nextIndex;
   }

   // Re-encode the lowercase letters.
   for ( int c = 'a'; c <= 'z'; ++c, ++nextIndex )
   {
      encoding[c] = nextIndex;
   }

   // Re-encode the numbers.
   for ( int c = '0'; c <= '9'; ++c, ++nextIndex )
   {
      encoding[c] = nextIndex;
   }

   // Re-encode the special chracters.
   char const* specialChars = " !\"#$%&'()*+,-./:;<=>?[\\]^_`{|}~";
   for ( char* cp = specialChars; *cp != '\0'; ++cp, ++nextIndex )
   {
      encoding[*cp] = nextIndex;
   }
}

bool mycompare(char const* s1, char const* s2)
{
   static char encoding[256];
   static bool initialized = false;
   if ( !initialized )
   {
      initializeEncoding(encoding);
      initialized = true;
   }

   for ( ; *s1 != '\0' && *s2 != '\0'; ++s1, ++s2 )
   {
      if ( encoding[*s1] != encoding[*s2] )
      {
         break;
      }
   }

   return ((encoding[*s1] - encoding[*s2]) < 0);
}

bool mycompare(std::string const& s1, std::string const& s2)
{
   return mycompare(s1.c_str(), s2.c_str());
}