Use multi-key tree search for {map, set}::{count, equal_range}
Patch from ngolovliov@gmail.com
Reviewed as: https://reviews.llvm.org/D42344
As described in llvm.org/PR30959, the current
implementation of std::{map, key}::{count, equal_range} in libcxx is
non-conforming. Quoting the C++14 standard [associative.reqmts]p3
> The phrase “equivalence of keys” means the equivalence relation imposed by
> the comparison and not the operator== on keys. That is, two keys k1 and k2 are
> considered to be equivalent if for the comparison object comp,
> comp(k1, k2) == false && comp(k2, k1) == false.
In the same section, the requirements table states the following:
> a.equal_range(k) equivalent to make_pair(a.lower_bound(k), a.upper_bound(k))
> a.count(k) returns the number of elements with key equivalent to k
The behaviour of libstdc++ seems to conform to the standard here.
llvm-svn: 324799
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: 9bfdb770cc7f513546468e9a4867fa9fdce6caaf
diff --git a/include/map b/include/map
index 9521493..8a72260 100644
--- a/include/map
+++ b/include/map
@@ -1228,7 +1228,7 @@
template <typename _K2>
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
- count(const _K2& __k) const {return __tree_.__count_unique(__k);}
+ count(const _K2& __k) const {return __tree_.__count_multi(__k);}
#endif
_LIBCPP_INLINE_VISIBILITY
iterator lower_bound(const key_type& __k)
@@ -1275,11 +1275,11 @@
template <typename _K2>
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
- equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
+ equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
template <typename _K2>
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
- equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
+ equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
#endif
private: