ng created this revision.
ng added a reviewer: mclow.lists.
Herald added a reviewer: EricWF.
As described in http://bugs.llvm.org/show_bug.cgi?id=30959, the current
implementation of std::{map, key}::{count, equal_range} in libcxx is
non-conforming. Quoting ISO/IEC 14882:2014 section 23.2.4:
> 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.
Repository:
rCXX libc++
https://reviews.llvm.org/D42344
Files:
include/map
include/set
Index: include/map
===================================================================
--- include/map
+++ include/map
@@ -1223,12 +1223,12 @@
_LIBCPP_INLINE_VISIBILITY
size_type count(const key_type& __k) const
- {return __tree_.__count_unique(__k);}
+ {return __tree_.__count_multi(__k);}
#if _LIBCPP_STD_VER > 11
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)
@@ -1267,19 +1267,19 @@
_LIBCPP_INLINE_VISIBILITY
pair<iterator,iterator> equal_range(const key_type& __k)
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
#if _LIBCPP_STD_VER > 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:
Index: include/set
===================================================================
--- include/set
+++ include/set
@@ -663,12 +663,12 @@
_LIBCPP_INLINE_VISIBILITY
size_type count(const key_type& __k) const
- {return __tree_.__count_unique(__k);}
+ {return __tree_.__count_multi(__k);}
#if _LIBCPP_STD_VER > 11
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)
@@ -707,19 +707,19 @@
_LIBCPP_INLINE_VISIBILITY
pair<iterator,iterator> equal_range(const key_type& __k)
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
#if _LIBCPP_STD_VER > 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
};
Index: include/map
===================================================================
--- include/map
+++ include/map
@@ -1223,12 +1223,12 @@
_LIBCPP_INLINE_VISIBILITY
size_type count(const key_type& __k) const
- {return __tree_.__count_unique(__k);}
+ {return __tree_.__count_multi(__k);}
#if _LIBCPP_STD_VER > 11
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)
@@ -1267,19 +1267,19 @@
_LIBCPP_INLINE_VISIBILITY
pair<iterator,iterator> equal_range(const key_type& __k)
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
#if _LIBCPP_STD_VER > 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:
Index: include/set
===================================================================
--- include/set
+++ include/set
@@ -663,12 +663,12 @@
_LIBCPP_INLINE_VISIBILITY
size_type count(const key_type& __k) const
- {return __tree_.__count_unique(__k);}
+ {return __tree_.__count_multi(__k);}
#if _LIBCPP_STD_VER > 11
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)
@@ -707,19 +707,19 @@
_LIBCPP_INLINE_VISIBILITY
pair<iterator,iterator> equal_range(const key_type& __k)
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
- {return __tree_.__equal_range_unique(__k);}
+ {return __tree_.__equal_range_multi(__k);}
#if _LIBCPP_STD_VER > 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
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
