Cannot sort vector>

Question

I tried to sort a vector<pair<int, int>> by using STL sort with my own boolean function.

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int, int> u1, pair<int, int> u2){
    if(u1.first != u2.first) return u1.first < u2.first;
    return u2.second > u2.second;
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int univs, day, pay, max_income = 0, spent = 0;
    vector<pair<int, int>> day_pay;
    cin >> univs;
    for(int u = 0; u < univs; u++){
        cin >> pay >> day;
        day_pay.push_back(make_pair(day, pay));
    }
    for(int i = 0; i < univs; i++) cout << day_pay[i].first << " " << day_pay[i].second << endl;
    cout << endl;
    sort(day_pay.begin(), day_pay.end(), comp);
    for(int i = 0; i < univs; i++) cout << day_pay[i].first << " " << day_pay[i].second << endl;
    for(int u = 0; u < univs; u++){
        if(day_pay[u].first <= spent) continue;
        max_income += day_pay[u].second;
        spent++;
    }
    cout << max_income;
}

this is test case:

I want to sort this case as

What should I do for solving this problem?

[Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice), [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — HolyBlackCat, Apr 20 '20 at 14:57
To clarify - you want to sort such that the second element is first compared and lower numerically equals earlier in order, then if the second elements are equal you compare the first element and HIGHER numerically equals earlier in order? Can you add some pairs that share an equal first element and show in your example how you want them sorted? — JohnFilleau, Apr 20 '20 at 14:57
There needs to be a wiki page along the lines of "Why are competitive coding sites bad for learning?" — sweenish, Apr 20 '20 at 14:58
@sweenish Maybe they are typing so fast, they don't see the typos they are making. This error looks like a typo more than a concerted effort to compare the wrong items. — PaulMcKenzie, Apr 20 '20 at 15:21

score 0 · Answer 1 · answered Apr 20 '20 at 14:55

0

Look at your comp function. The line after the if:

return u2.second > u2.second;

shuldn't that be:

return u1.second > u2.second

answered Apr 20 '20 at 14:55

Andrija

15
6

score 0 · Accepted Answer · answered Apr 20 '20 at 14:55

0

The line

return u2.second > u2.second;

is suspicious. You most likely mean

return u1.second > u2.second;

answered Apr 20 '20 at 14:55

Caleth

52,200
2
44
75

brc-dd · Answer 3 · 2021-02-03T10:41:24.543

The actual fault was well pointed by Caleth in their answer. But I think that this much code is sufficient for sorting. You may modify it according to your question.

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::size_t n;
    std::cin >> n;

    std::vector<std::pair<int, int>> v(n);
    for (auto &&i : v) std::cin >> i.first >> i.second;

    std::sort(v.begin(), v.end(),
              [](std::pair<int, int> &a, std::pair<int, int> &b) {
                  return a.second != b.second ? a.second < b.second
                                              : a.first > b.first;
              });

    for (auto &&i : v) std::cout << i.first << ' ' << i.second << '\n';
}

If you're using C++ 14 or higher, you can directly use auto in lambda params.

Sample Run:

Sample Input:

Corresponding Output:

What aspect of this requires C++14? I'm not super familiar with the changes between 11 and 14. — JohnFilleau, Apr 20 '20 at 15:09
@JohnFilleau C++11 doesn't allow auto in lambda params. https://isocpp.org/wiki/faq/cpp14-language#generic-lambdas — brc-dd, Apr 20 '20 at 15:10

Cannot sort vector>

3 Answers3