(@vmichal's #5987 is changing this code, but the issue is pre-existing and orthogonal. Update these citations after merging that PR.)
|
template <class _KeyTy>
|
|
_NODISCARD size_type _Count(const _KeyTy& _Key_val) const {
|
|
_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
|
|
return upper_bound(_Key_val) - lower_bound(_Key_val);
|
|
}
|
|
|
|
template <class _KeyTy>
|
|
_NODISCARD bool _Contains(const _KeyTy& _Key_val) const {
|
|
_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
|
|
return find(_Key_val) != cend();
|
|
}
|
|
template <class _KeyTy>
|
|
_NODISCARD pair<iterator, iterator> _Equal_range(const _KeyTy& _Key_val) {
|
|
_STL_INTERNAL_STATIC_ASSERT(is_same_v<_KeyTy, key_type> || _Transparent<key_compare>);
|
|
return {lower_bound(_Key_val), upper_bound(_Key_val)};
|
|
}
|
First, the implementations of count() and contains() are forming full key-value iterators, but they only need to care about the keys.
Second, count() and equal_range() are calling lower_bound() and upper_bound() independently, which performs two binary searches to get to the same general region. Going through ranges::equal_range would perform less work.
Third, count() should probably be optimized for non-multi flat_map, as it becomes morally equivalent to contains().
(@vmichal's #5987 is changing this code, but the issue is pre-existing and orthogonal. Update these citations after merging that PR.)
STL/stl/inc/flat_map
Lines 1124 to 1134 in 18e1eb5
STL/stl/inc/flat_map
Lines 1194 to 1198 in 18e1eb5
First, the implementations of
count()andcontains()are forming full key-value iterators, but they only need to care about the keys.Second,
count()andequal_range()are callinglower_bound()andupper_bound()independently, which performs two binary searches to get to the same general region. Going throughranges::equal_rangewould perform less work.Third,
count()should probably be optimized for non-multiflat_map, as it becomes morally equivalent tocontains().