libc++ 的 std::map/set::equal_range 实现给出了意想不到的结果
libc++'s implementation of std::map/set::equal_range gives unexpected results
我注意到 clang 的 libc++ 中的 std::set::equal_range
(与 std::map
相同)给出的结果与 libstdc++ 不同。
我一直认为 equal_range
应该 return 等价于 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
return 2 个元素。
现在这是 libc++
中的错误还是 cppreference 在 https://en.cppreference.com/w/cpp/container/set/equal_range 中给出了错误提示:
Alternatively, the first iterator may be obtained with lower_bound()
, and the second with upper_bound()
.
你的代码没问题。
您正在过时的 libc++ 上进行测试。这是 bug 30959,已于 2018 年修复并在 clang 7 中可用。
Rextester 的叮当声显然是 3.8。
我注意到 clang 的 libc++ 中的 std::set::equal_range
(与 std::map
相同)给出的结果与 libstdc++ 不同。
我一直认为 equal_range
应该 return 等价于 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
return 2 个元素。
现在这是 libc++
中的错误还是 cppreference 在 https://en.cppreference.com/w/cpp/container/set/equal_range 中给出了错误提示:
Alternatively, the first iterator may be obtained with
lower_bound()
, and the second withupper_bound()
.
你的代码没问题。
您正在过时的 libc++ 上进行测试。这是 bug 30959,已于 2018 年修复并在 clang 7 中可用。
Rextester 的叮当声显然是 3.8。