CODEWITHSUNDEEP
c++algorithmsetstdcomparator
JunsungChoi
JunsungChoi

Reputation: 87

C++ std::set<string> Alphanumeric custom comparator

I'm solving a problem with a sorting non-redundant permutation of String Array. For example, if input string is "8aC", then output should be order like {"Ca8","C8a", "aC8", "a8C", "8Ca", "9aC"}.I chose C++ data structure set because each time I insert the String into std:set, set is automatically sorted and eliminating redundancy. The output is fine.

But I WANT TO SORT SET IN DIFFERENT ALPHANUMERIC ORDER which is different from default alphanumeric sorting order. I want to customize the comparator of set the order priority like: upper case> lower case > digit.

I tried to customize comparator but it was quite frustrating. How can I customize the sorting order of the set? Here's my code.

set<string, StringCompare> setl;
for (i = 0; i < f; i++)
{
    setl.insert(p[i]); //p is String Array. it has the information of permutation of String.
}
for (set<string>::iterator iter = setl.begin(); iter != setl.end(); ++iter)
       cout << *iter << endl; //printing set items. it works fine.

struct StringCompare
{
    bool operator () (const std::string s_left, const std::string s_right)
    {
        /*I want to use my character comparison function in here, but have no idea about that. 
          I'm not sure about that this is the right way to customize comparator either.*/
    }
};

int compare_char(const char x, const char y)
{
    if (char_type(x) == char_type(y))
    {
        return ( (int) x < (int) y) ? 1 : 0 ;
    }
    else return (char_type(x) > char_type(y)) ? 1 : 0;
}

int char_type(const char x)
{
    int ascii = (int)x;
    if (ascii >= 48 && ascii <= 57) // digit
    {
        return 1;
    }
    else if (ascii >= 97 && ascii <= 122) // lowercase
    {
        return 2;
    }
    else if (ascii >= 48 && ascii <= 57) // uppercase
    {
        return 3;
    }
    else
    {
        return 0;
    }
}

Upvotes: 1

Views: 2002

Answers (5)

robotician
robotician

Reputation: 42

You are almost there, but you should compare your string lexicographically. I roughly added small changes to your code.

int char_type( const char x )
{
    if ( isupper( x ) )
    {
        // upper case has the highest priority
        return 0;
    }

    if ( islower( x ) )
    {
        return 1;
    }

    if ( isdigit( x ) )
    {
        // digit has the lowest priority
        return 2;
    }

    // something else
    return 3;
}

bool compare_char( const char x, const char y )
{
    if ( char_type( x ) == char_type( y ) )
    {
        // same type so that we are going to compare characters
        return ( x < y );
    }
    else
    {
        // different types
        return char_type( x ) < char_type( y );
    }
}

struct StringCompare
{
    bool operator () ( const std::string& s_left, const std::string& s_right )
    {
        std::string::const_iterator iteLeft  = s_left.begin();
        std::string::const_iterator iteRight = s_right.begin();

        // we are going to compare each character in strings
        while ( iteLeft != s_left.end() && iteRight != s_right.end() )
        {
            if ( compare_char( *iteLeft, *iteRight ) )
            {
                return true;
            }

            if ( compare_char( *iteRight, *iteLeft ) )
            {
                return false;
            }

            ++iteLeft;
            ++iteRight;
        }

        // either of strings reached the end.
        if ( s_left.length() < s_right.length() )
        {
            return true;
         }

         // otherwise. 
         return false;
    }
};

Upvotes: 2

uSeemSurprised
uSeemSurprised

Reputation: 1834

This should work : 

bool operator () (const std::string s_left, const std::string s_right)
    {
        for(int i = 0;i < s_left.size();i++){
            if(isupper(s_left[i])){
                if(isupper(s_right[i])) return s_left[i] < s_right[i];
                else if(islower(s_right[i]) || isdigit(s_right[i]))return true;
            }
            else if(islower(s_left[i])){
                if(islower(s_right[i])) return s_left[i] < s_right[i];
                else if(isdigit(s_right[i])) return true;
                else if(isupper(s_right[i])) return false;
            }
            else if(isdigit(s_left[i])){
                if(isdigit(s_right[i])) return s_left[i] < s_right[i];
                else if(islower(s_right[i]) || isupper(s_right[i])) return false;
            }
        }
    }

Upvotes: 0

Aboudi
Aboudi

Reputation: 318

Not absoloutely sure about this, but you may be able to use an enumerated class towards your advantage or an array and choose to read from certain indices in which ever order you like.

You can use one enumerated class to define the order you would like to output data in and another that contains the data to be outputed, then you can set a loop that keeps on looping to assign the value to the output in a permuted way!

namespace CustomeType
{
    enum Outs { Ca8= 0,C8a, aC8, a8C, 8Ca, 9aC };
    enum Order{1 = 0 , 2, 3 , 4 , 5};   
    void PlayCard(Outs input)
    {
        if (input == Ca8) // Enumerator is visible without qualification
        {
            string[] permuted;
            permuted[0] = Outs[0];
            permuted[1] = Outs[1];
            permuted[2] = Outs[2];
            permuted[3] = Outs[3];
            permuted[4] = Outs[4];
        }// else use a different order
     else if (input == Ca8) // this might be much better
     {
       string[] permuted;
       for(int i = 0; i<LessThanOutputLength; i++)
       {
              //use order 1 to assign values from Outs
       }
     }
    }
}

Upvotes: 0

Tristan Brindle
Tristan Brindle

Reputation: 16834

You're very nearly there with what you have.

In your comparison functor you are given two std::strings. What you need to do is to find the first position where the two strings differ. For that, you can use std::mismatch from the standard library. This returns a std::pair filled with iterators pointing to the first two elements that are different:

auto iterators = std::mismatch(std::begin(s_left), std::end(s_left),
                               std::begin(s_right), std::end(s_right));

Now, you can dereference the two iterators we've been given to get the characters:

char c_left = *iterators.first;
char c_right = *iterators.second;

You can pass those two characters to your compare_char function and it should all work :-)

Upvotes: 0

marom
marom

Reputation: 5230

Your comparator is right. I would turn parameters to const ref like this

bool operator () (const std::string &s_left, const std::string &s_right)

and start by this simple implementation:

return s_left < s_right

This will give the default behaviour and give you confidence you are on the right track. Then start comparing one char at the time with a for loop over the shorter between the length of the two strings. You can get chars out the string simply with the operator[] (e.g. s_left[i])

Upvotes: 1

Related Questions