Реализация libc++ std::map/set::equal_range дает неожиданные результаты

Я заметил, что std::set::equal_range (то же самое для std::map) в clang libc++ дает другой результат, чем libstdc++. Я всегда предполагал, что equal_range должен возвращать эквивалент std::make_pair(set.lower_bound(key), set.upper_bound(key)), что говорит cppreference и делает libstdc++. Однако в libc++ у меня есть код, который дает другой результат.

#include <set>
#include <iostream>
#include <iterator>

struct comparator {
    using range_t = std::pair<int, int>;
    using is_transparent = std::true_type;
    bool operator()(int lhs, int rhs) const
    {
        return lhs < rhs;
    }
    bool operator()(int lhs, range_t rhs) const
    {
        return lhs < rhs.first;
    }
    bool operator()(range_t lhs, int rhs) const
    {
        return lhs.second < rhs;
    }
};

using range_set = std::set<int, comparator>;

int main()
{
    range_set set = { 1, 3, 6, 10 };
    auto range = comparator::range_t{2, 7};
    auto eq = set.equal_range(range);
    auto low = set.lower_bound(range);
    auto high = set.upper_bound(range);
    std::cout << "equal_range returned " << std::distance(eq.first, eq.second) << " elem(s): ";
    std::copy(eq.first, eq.second, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nlower/upper returned " << std::distance(low, high) << " elem(s): ";
    std::copy(low, high, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    return 0;
}

Как вы можете видеть на странице https://rextester.com/CLTS82056, это дает

equal_range returned 1 elem(s): 3 
lower/upper returned 2 elem(s): 3 6 

С libstdc++, а также с boost::container::set я получаю 2 элемента (что и ожидаю) в обоих случаях.

Конечно, я могу вручную вызвать lower_bound и upper_bound в своем коде, но использование equal_range короче, ясно показывает мое намерение (я хочу найти все элементы, которые попадают в заданный диапазон) и может быть быстрее (потому что метод equal_range можно было бы закодировать как одно дерево обход без фактических вызовов lower_bound и upper_bound).

Интересно, что изменение типа контейнера на std::multiset в этом случае приводит к тому, что equal_range возвращает 2 элемента.

Теперь это ошибка в libc++ или cppreference дает неправильную подсказку в https://en.cppreference.com/w/cpp/container/set/equal_range:

Альтернативно, первый итератор можно получить с помощью lower_bound(), а второй с помощью upper_bound().


person koval    schedule 18.08.2019    source источник
comment
Мне кажется, что эффективный результат строгого слабого упорядочения вашего компаратора диапазонов реализован таким образом, что 3 и 6 в сравнении std::set равны значению диапазона, которое передается в equal_range. Учитывая, что std::set должен содержать только уникальные значения, реализация libc может предположить, что как только она находит значение, которое сравнивается равным, это все, что есть в наборе. Я не нашел ничего в кратком обзоре того, что говорит N4659, что поддерживает это. Единственное, что я вижу, это то, что comparator должно определять is_transparent. Не уверен, но я укажу пальцем на libc.   -  person Sam Varshavchik    schedule 18.08.2019


Ответы (1)


Ваш код в порядке.

Вы тестируете устаревшую libc++. Это ошибка 30959, исправленная в 2018 году и доступная в clang 7.

Clang Ректестера видимо 3.8.

person T.C.    schedule 18.08.2019
comment
Приятно это слышать, я использовал clang 6 на своей стороне и, похоже, наконец пришло время обновиться. - person koval; 18.08.2019
comment
Хех, я мог бы поклясться, что давным-давно набросал что-то о том, что разделение является единственным требованием для прозрачных сравнений. Должно быть, это был плод моего воображения... - person Sam Varshavchik; 18.08.2019