1

Как заполнить std::set элементами стуктуры struct para { bool flag, int x;} ? Причем para(true,100) и para(false,100) считаются разными элементами и должны успешно инсертиться. При вставке срабатывает operator< . видимо для того чтобы вставить элемент куда нужно. Но его использование делается странным.

struct para {
    bool flag;
    int x;
    para(bool i, int x) : flag(i), x(x) {};
    bool operator<(const para& r) const {
        return (r.flag == this->flag || r.x < this->x);                
    }
};
int main()
{
    std::set<para> store1;
    store1.insert(para(false, 10)); //+1 para (нет такой пары в наборе поэтому добавляем её)
    store1.insert(para(true, 10));  //+1 para (нет такой пары в наборе поэтому добавляем её)
    store1.insert(para(true, 11));  //+1 para (нет такой пары в наборе поэтому добавляем её)
    store1.insert(para(true, 10));  //ничего не добавляем в набор (т.к. элемент 
                                    //para(true,10) уже есть в наборе)
}

operator< тут работает не очень очевидно. вопрос как я должен оформить bool operator<(const para& r) const чтобы получить вот такой исход как описан в main (комменты)

15
  • 2
    operator< тут не работает, если поле flag одинаковое у объектов a и b, то a < b и b < a будут давать положительный результат, не обеспечивая требования упорядоченности, как того требует set. По-моему flag тут должен проверяться после x. 23 янв в 13:17
  • 1
    set сам проверяет. Гуглите про лексикографический порядок, и реализуйте его в своем operator<. 23 янв в 13:45
  • 3
    Не пес. Чтобы set мог нормально работать, порядок должен быть нормальным. У вас при flag == true одновременно истино a < b и b > 0 - это явно ненормальный порядок, вот set и ломается. 23 янв в 13:53
  • 2
    Факт того что вставлять не надо тоже задается оператором < - с его помощью определяется равенство вставляемого элемента и существующего. 23 янв в 14:01
  • 4
    !(a<b) && !(b<a) 23 янв в 14:25

2 ответа 2

3

Если у this и r различаются флаги, упорядочиваем их по флагам. Иначе по значениям x. Порядок получится таким:

  • (false, *) < (true, *)
  • (false, x) < (false, y) если x < y
  • (true, x) < (true, y) если x < y

(false, 1) < (false, 2) < (true, 1) < (true, 2)

Код:

bool operator <(const para& r) const {
    if (!flag && r.flag) {
        return true;
    }
    if (flag && !r.flag) {
        return false;
    }
    return x < r.x;                
}

У это порядка есть важное свойство: если this и r различаются, то или *this < r или r < *this. Если вы нарушаете это правило, set может посчитать различающиеся пары одинаковыми, и отказаться вставлять одну если внутри уже есть другая. Что вы и видели с вашим кодом порядка.

5
  • спасибо большое ! 23 янв в 17:42
  • )) мне вот так понятней : bool operator<(const para& r) const { if (flag == r.flag) return x < r.x; else if (r.flag) return true; else false; } 24 янв в 7:55
  • Вы хотели сказать: if (flag == r.flag) return x < r.x; return r.flag;. Да, так можно. 24 янв в 10:13
  • Или даже так: return (flag == r.flag) ? x < r.x : r.flag;. 24 янв в 10:15
  • Разговор не столько про форму кода, сколько про принцип: равенство как отсутствие неравенства. 24 янв в 10:17
2

Я предложил бы оптимизированный вариант первого ответа. В плане эффективности битовая операция, особенно с одним битом, куда быстрей чем несколько сравнений:

bool operator <(const para& r) const {        
    return (flag ^ r.flag) ? r.flag : x < r.x;                
}
4
  • спасибо за ответ 24 янв в 8:04
  • 2
    Можно переписать без смешивания с битовыми операциями: (flag != r.flag) ? r.flag : x < r.x;. 24 янв в 11:22
  • @Stanislav Volodarskiy, согласен, но, по идеи, та же операция выполнится 24 янв в 12:36
  • 2
    И я про тоже. Компилятору предоставлена вся информация. Он сам выберет оптимальную последовательность операций - битовых или байтовых. 24 янв в 12:51

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.