Я заметил, что 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()
.
std::set
равны значению диапазона, которое передается вequal_range
. Учитывая, чтоstd::set
должен содержать только уникальные значения, реализация libc может предположить, что как только она находит значение, которое сравнивается равным, это все, что есть в наборе. Я не нашел ничего в кратком обзоре того, что говорит N4659, что поддерживает это. Единственное, что я вижу, это то, чтоcomparator
должно определятьis_transparent
. Не уверен, но я укажу пальцем на libc. - person Sam Varshavchik   schedule 18.08.2019