Блог

Главная - Вопросы по программированию - Как upper_bound работает с пользовательским типом объекта val?

Как upper_bound работает с пользовательским типом объекта val?

#c #algorithm #c 17

#c #алгоритм #c 17

Вопрос:

В настоящее время я изучаю алгоритм upper_bound на c , и все довольно просто, если третий параметр val имеет тип Integer . Однако я наткнулся на пример с пользовательским типом val, и все немного запуталось. Пример кода.

 class Pocket
{
public:
    int value;
    Pocket(int value) : value(value) {};
    bool operator < (const Pocketamp; right) const
    {
        return value < right.value;
    }

    int getValue() const
    {
        return value;
    }
};

bool Compare(const Pocket amp;left, const Pocket amp;right)
{
    return int (left.getValue() > right.getValue());
}

void main()
{
    int a[] = { 3, 9, 2, 4, 4 };
    std::deque<Pocket> d(a, a   5);
    std::sort(d.begin(), d.end(), Compare);
    std::deque<Pocket>::iterator it = std::upper_bound(d.begin(), d.end(), Pocket(2));
}

Результирующий итератор будет указывать на элемент со значением 9. Как?

Комментарии:

1. Похоже на неопределенное поведение. Список не сортируется в том же порядке, что и upper_bound .

Ответ №1:

Ваша программа имеет неопределенное поведение. Диапазон, который вы передаете верхней границе, должен быть отсортирован по < (для перегрузки трех аргументов).

Комментарии:

1. нет, не обязательно с помощью < . std::upper_bound принимает компаратор, который должен приводить к тому же порядку, что и контейнер, который уже отсортирован

2. @idclev463035818 форма с тремя аргументами использует <

3. afaik это даже не обязательно должен быть один и тот же компаратор, если контейнер отсортирован по отношению к компаратору, используемому с std::upper_bound

4. о, хорошо, извините, я виноват. Недостаточно внимательно прочитал. Тем не менее, добавление этого также покажет OP, как это решить

5. о, понял. Компаратор испортил поведение верхней границы, изменил его на < и получил ожидаемый результат. Спасибо!