Is there a method to compare a vector to a string sequence using sort?

Question

I have a vector<string> containing several words that are based on user input. They are are all stored in the vector using a variable named container. I need to arrange the words in the string into an unconventional QWERTY-order, or in other words I need them to be sorted based on the string string sequence = "QWERTYUIOPASDFGHJKLZXCVBNM"; So a sample run would look like this

Enter a word: apple Enter a word: pear Enter a word: peach

Words sorted in QWERTY order: pear peach apple

I'm currently only able to store these character strings, and since they are not alphabetical I cannot use the character values in if-statements,

I was given a hint to use sort-selection or insertion to compare my vector-string to the QWERTY-sequence, but I'm unable to find any examples in my Textbook or online on how to apply this to my code. Any help would be greatly appreciated, thank you for your time.

Answer 1

One option is to replace every character by the corresponding one from your special alphabet. Then do a sort and change back.

For example:

we -> bc, er -> cd

Answer 2

Just use std::string::find to find index of a symbol and compare them:

bool sequenceLess( const std::string &s1, const std::string &s2 )
{
    static const std::string sequence = "QWERTYUIOPASDFGHJKLZXCVBNM";
    for( size_t i = 0; i < s1.length(); ++i ) {
        if( i >= s2.length() ) return false;
        auto idx1 = sequence.find( ::toupper( s1[i] ) );
        auto idx2 = sequence.find( ::toupper( s2[i] ) );
        if( idx1 == idx2 ) continue;
        return idx1 < idx2;
    }
    return true;
}

another version is to convert a string to vector of indexes and compare them:

std::vector<size_t> convert( const std::string &s )
{
    static const std::string sequence = "QWERTYUIOPASDFGHJKLZXCVBNM";
    std::vector<size_t> r( s.size() );
    std::transform( s.begin(), s.end(), r.begin(), [sequence]( char c ) {
         return sequence.find( ::toupper( c ) );
     } );
    return r;
}

// now comparison is obvious
bool sequenceLess( const std::string &s1, const std::string &s2 )
{
    return convert( s1 ) < convert( s2 );
}

this solution is inefficient, but for learning purpose should be ok.

Answer 3

You can try customize sort. Please refer to this link Sorting a vector of custom objects

Below is my code sample for your case, but I dint handle for lower case letters.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct mySort{
     inline bool operator() (const string& s1, const string& s2)
    {
        bool isSort = false;

        if(s1.length() < s2.length()){
            return true;
        }else if(s1.length() > s2.length()){
            return false;
        }

        //s1.length() == s1.length()
        string sequence = "QWERTYUIOPASDFGHJKLZXCVBNM";
        int index1 = 0 , index2 = 0;
        for(int i = 0 ; i < s1.length() ; i++){

            for(int j = 0 ; j < sequence.length() ; j++){
                if(s1[i] == sequence[j]){
                    index1 = j;

                }
                if(s2[i] == sequence[j]){
                    index2 = j;
                }
            }

            if(index1 < index2){return true;}
        }

        return false;
    }
};

int main(){


    vector<string> myVector;
    myVector.push_back("APPLE");
    myVector.push_back("PEAR");
    myVector.push_back("PEACH");
    sort(myVector.begin(), myVector.end(), mySort());
    for(int i = 0 ; i < myVector.size() ; i++){
        cout<<myVector[i]<<endl;
    }

    return 1;
}

Here is the result,

PS : Maybe I miss some conditions, but just share with you, how to apply the customize sort.

Answer 4

You can overload < operator for strings and then use c++ function sort() located in <algorithm> I don't quite understand how do you exactly want to sort strings with that rule, so it's up to you to encode the comparison of two strings, and that would be it.

Answer 5

Edit: Added the lookup table and corrected the tests in getless.

Here is another solution using std::sort and a function that tests each string and returns true if one string is less than the other in QWERTY order:

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

typedef std::vector<std::string> StringVect;
std::string sequence = "QWERTYUIOPASDFGHJKLZXCVBNM";
std::vector<int> lookup(26);

bool getless(const std::string& s1, const std::string& s2)
{
    for (size_t i = 0; i < std::min(s1.size(), s2.size()); ++i)
        if (s1[i] != s2[i])
            return (lookup[toupper(s1[i])-'A'] < lookup[toupper(s2[i])-'A']);
    return s1.size() < s2.size();
};

int main()
{
    StringVect sv = {{ "apple" },{ "pear" },{ "peach" }};

    // build the lookup table
    int i = 0;
    std::for_each(sequence.begin(), sequence.end(), [&](char ch) {lookup[ch-'A'] = i; ++i; });

    // sort the data
    std::sort(sv.begin(), sv.end(), getless);

    // output results
    for (auto& s : sv)
      std::cout << s << "\n";
}

Live Example

A lookup table is built that maps the character's relative ASCII position to where the character is found in the sequence string. So for example, lookup[0] is the position of A (which is 10), lookup[1] is the position of B (which is 23), etc.

The getless function scans the string and tests the character associated with the i'th character of each string with the corresponding lookup position.

The for loop basically "waits for" a character difference in the two strings being compared. If the character in the string for s1 has a lookup value less than the lookup value for the character in s2, then we immediately return "true", meaning that s1 < s2. Otherwise we return false if s1 > s2.

If the characters are equal, we keep looping until we run out of characters to compare. If both strings are equal up to the point we exit the for loop, we return true or false, depending on the length of the strings (a shorter string would mean s1 < s2).