Как правильно иметь набор структур в c ++?

Question

Мне нужен набор пользовательских структур, чтобы можно было быстро получить экземпляр с наименьшим заданным параметром. Однако я обнаружил, что std :: set считает некоторые экземпляры одинаковыми, даже если они имеют разные значения. Вот мой пример программы:

#include <set>
#include <iostream>

struct S
{
    int foo, bar;
    S(int foo, int bar): foo(foo), bar(bar) {}
};

inline bool operator<(const S& a, const S& b)
{
    return a.foo < b.foo;
}

int main()
{
    std::set<S> baz;
    baz.emplace(1, 2);
    baz.emplace(1, 3);
    std::cout << baz.size();

    return 0;
}

Эта программа печатает 1

std :: set считает S(1, 2) и S(1, 3) одинаковыми. Я предполагаю, что это потому, что bar не используется при их сравнении. Но мне нужен набор, чтобы сохранить оба элемента, как мне решить эту проблему?

РЕДАКТИРОВАТЬ: я чувствую, что не правильно сформулировал свой вопрос: я хочу сохранить экземпляры, которые не совсем совпадают, но std::multiset не работает для меня, потому что я не хочу, чтобы идентичные экземпляры были в контейнере

РЕШЕНИЕ: я думаю, что понимаю, что было не так. Я предположил, что если для 2 элементов a < b и b < a оба будут истинными, это приведет к неопределенному поведению. Но std :: set проверяет это, поэтому он удаляет один из элементов. Лучшее решение для меня - это изменить компаратор, который включает в себя bar.

Answer 1

Это не std::set, который рассматривает экземпляры S одинаково, если они имеют одинаковое foo, это ваше собственное operator<.

Так что вы должны:

• измените operator< (что также повлияет на сортировку), или
• используйте другой компаратор для вашего набора (параметр второго типа), или
• измените ваш operator<, чтобы он подходил для std::set, и используйте другой параметр Compare для std::sort (или же вы получите наименьший элемент).

Нижняя строка, если хотите различные функции сравнения для std::sort (или любого другого) и std::set, вам необходимо предоставить другую функциональность.

Поскольку вы не указали почему ваш operator< выглядит так (не считая S::bar), трудно сказать, что будет соответствовать вашим намерениям.

Answer 2

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

Answer 3

Немного упрощая, std::set сравнивает два элемента дважды при вставке:

1. a < b
2. b < a

Если 1. равно true, тогда a идет в порядке b.
Иначе, если 2. равно true, тогда b идет до a.
Остальное (оба значения false). a и b эквивалентны.

Поскольку S{1, 2} < S{1, 3} == false и S{1, 3} < S{1, 2} == false в соответствии с вашим определением operator <, они считаются эквивалентными и std::set::emplace не выполняется.

Answer 4

Возможно, как дополнение к другим ответам:

std::set сохраняет набор sorted и использует < -отношение, созданное operator< для сортировки элементов.

Итак, если даны два объекта a и b ... если ! (a < b) и ! (b < a), то ни a "меньше", чем b, ни b "меньше" чем a. Следовательно, a == b - с точки зрения отсортированного заказа.

Answer 5

Если foo и bar делают S уникальным, вы можете изменить operator<, чтобы использовать обе переменные, например:

inline bool operator<(const S& a, const S& b)
{
    if ( a.foo == b.foo )
       return a.bar < b.bar;
    return a.foo < b.foo;
}

Answer 6

Вы можете попробовать использовать std::multiset http://www.cplusplus.com/reference/set/multiset/