0

I'm trying to sort a vector< pair<int,char> > but i want to change the behavior of the comparison operators of the pair type , so that if the first values equal and it'a comparing with (>) operator, i want it to compare the second value with (<) operator.

I'm trying to do this to solve the "What's Cryptanalysis?" problem on uva . Here is my approach :

string toLower(string in){
    string out;
    for(int i=0;i<in.length();i++){
        if(in.at(i)<='Z' && in.at(i)>='A'){
            out+=in.at(i)+('a'-'A');
        }
        else if(in.at(i)<='z' && in.at(i)>='a'){
            out+=in.at(i);
        }
    }
    return out;
}


int main(){
    //freopen("in.txt","r",stdin);
    //freopen("tmp.txt","w",stdout);
    vector< pair<int,char> >vp;
    pair<int,char> tp;

    for(char a='a';a<='z';a++){//buliding a table of values and chars
        tp= make_pair(0,a);
        vp.push_back(tp);
    }
    int T;
    cin >> T;
    string s;
    cin.ignore();
    for(int i=0;i<T;i++){
        getline(cin,s);
        s=toLower(s);//remove special chars and convert all to lower
        int l=s.length();
        for(int j=0;j<l;j++){
            vp[s[j]-'a'].first+=1;//increasing the value of each char found
        }
    }
    sort(vp.begin(),vp.end());//ascending sort
    for(int j=25;j>=0;j--){
        cout << (char)(vp[j].second -('a'-'A')) << " " <<vp[j].first << endl;//cout the Capital char and its value backwards (Descending)
    }
    //system("pause");
    return 0;
}

But this is how output looks like:

S 7
T 6
I 5
E 4
O 3
W 2
U 2
N 2
H 2
A 2
Y 1
Q 1
M 1
C 1
Z 0
X 0
V 0
R 0
P 0
L 0
K 0
J 0
G 0
F 0
D 0
B 0

so for example i want W U N H A to be A H N U W

i have read about overloading in other questions but i don't know to implement it here

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Ali Essam
  • 502
  • 1
  • 7
  • 17
  • 3
    you shouldn't overload an operator here. You should implement a custom comparison function and pass that to `std::find` or simply reverse the vector after sorting.. – stefan Feb 05 '13 at 13:31

3 Answers3

6

This is done by passing in a custom comparer function to sort. You can most easily do this with a lambda like this:

sort(
    vp.begin(),
    vp.end(),
    [](const pair<int,char>& lhs, const pair<int,char>& rhs) -> bool {
        return lhs.first != rhs.first 
            ? lhs.first < rhs.first 
            : lhs.second < rhs.second;
    }
);

This code sorts on ascending first and then on ascending second, but you can tweak the priority and direction of the two comparisons to sort whichever way you want.

Jon
  • 428,835
  • 81
  • 738
  • 806
  • I think `lhs.first < rhs.first` should be `lhs.first > rhs.first` - the asker wants descending order by first element in the pair. – Joseph Mansfield Feb 05 '13 at 13:38
  • @sftrabbit: Wasn't trying to nail down the exact sort; it's pretty easy to see how it can be changed. Added a clarification though, thanks. – Jon Feb 05 '13 at 13:41
  • thank you for your answer, i know your code should theoretically run faster because of using the simple if statement ,but i chose @sftrabbit code for being more readable by anyone, Thank you again :) . – Ali Essam Feb 05 '13 at 14:16
5

Just provide your own comparison function:

bool comp(const std::pair<int, char>& a, const std::pair<int, char>& b)
{
  if (a.first > b.first) {
    return true;
  } else if (a.first == b.first && a.second < b.second) {
    return true;
  }
  return false;
}

Then use it when you sort:

sort(vp.begin(),vp.end(), comp);
Joseph Mansfield
  • 108,238
  • 20
  • 242
  • 324
2

I'm trying to sort a vector< pair > but i want to change the behavior of the comparison

Just define a suitable binary predicate function and pass it as third argument to std::sort. Bear in mind that it should implement a strict weak ordering:

bool foo(const pair<int,char>& lhs, const pair<int,char>& rhs)
{
  // implement logic here
}

....

sort(vp.begin(),vp.end(), foo);
Community
  • 1
  • 1
juanchopanza
  • 223,364
  • 34
  • 402
  • 480