Закладываю в set 7 гарантированно различных элементов, а получаю только 6

199
24 июля 2018, 02:00

Имею структуру pair<int, pair<int, int>>, через typedef обозванную как guard. Имею set<guard, comp>, с компаратором, который сравнивает только по second.first.

Добавляю несколько guard в этот set. second.first могут повторяться (!), но first и second.second всегда строго различны. Не смотря на это, set куда-то "съедает" один элемент. Именно тот, у которого second.first повторяет оный у другого элемента. Полагаю, дело в компараторе.

Вот входные данные и наши некорректные выходные. Видно, что вводится 7 элементов, а в set остаётся только 6.

IN:

7 1
2 3 4 5 7 8 9
0 3 7 9 5 8 9

OUT:

9 9 6
8 8 5
7 5 4
5 9 3
4 7 2
3 3 1
2 0 0
!6

Вот код:

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
const double pi = 3.14159265358979323;
const double eps = 0.0000001;
typedef pair<int, pair<int, int>> guard;
#define money ss.ff
#define strength ff
#define num ss.ss
struct comp {
    bool operator() (guard a, guard b) const {
        return a.money > b.money;
    }
};
int main(int argc, char **argv) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //freopen("palin.in", "r", stdin);
    //freopen("palin.out", "w", stdout);
#endif
    int n, k;
    vector<guard> a;
    set<guard, comp> q;
    vector<int> m;
    cin >> n >> k;
    a.resize(n);
    m.assign(n, 0);
    for(int i = 0; i < a.size(); i++) {
        int x;
        cin >> x;
        a[i].num = i;
        a[i].strength = x;
    }
    for(int i = 0; i < a.size(); i++) {
        int x;
        cin >> x;
        a[i].money = x;
        m[i] = x;
    }
    for(auto &x : a) {
        q.insert(x);
    }
    sort(a.rbegin(), a.rend());
    for(auto &x : a) cout << x.strength << " " << x.money << " " << x.num << endl;
    cout << "!" << q.size() << endl;
    ...
    return 0;
}
Answer 1

std::set не проверяет элементы на уникальность, а проверяет элементы на эквивалентность. Эквивалентность как раз определяется через заданный вами функтор сравнения. Если ваш функтор сравнения говорит, что вставляемый элемент эквивалентен какому-то уже присутствующему в контейнере, то вставки делаться не будет. А равен ли этот элемент своему эквиваленту или нет (с точки зрения буквально хранящихся в нем данных) значения не имеет.

В данном случае вы написали функтор сравнения, который говорит, что все элементы с равными значениями в полях second.first эквивалентны. Это и обусловило наблюдаемое вами поведение.

READ ALSO
Не запускается программа

Не запускается программа

Пытаюсь нарисовать треугольник, но что то идет не так

248
Библиотека для визуализации графа на с++

Библиотека для визуализации графа на с++

стоит задача визуализировать граф как на изображении нижеЕсть код на с++, описывающий графы данного вида

180
Чем std::unique_lock отличается от std::lock_guard?

Чем std::unique_lock отличается от std::lock_guard?

Чем std::unique_lock отличается от std::lock_guard? В каких ситуациях лучше применять один класс, а в каких другой?

159
Не является приложением Win32

Не является приложением Win32

Такое дело, скомпилировал программу в на релиз x86 решил проверить на старом компьютере выводится сообщение "Не является приложением win32" когда...

165