[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng added a comment. Could you please commit this on my behalf? I don't have commit access. https://reviews.llvm.org/D42344 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
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
_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 equal_range(const key_type& __k)
-{return __tree_.__equal_range_unique(__k);}
+{return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair 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
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare,
_K2>::value,pair>::type
-equal_range(const _K2& __k) {return
__tree_.__equal_range_unique(__k);}
+equal_range(const _K2& __k) {return
__tree_.__equal_range_multi(__k);}
template
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare,
_K2>::value,pair>::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
_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 equal_range(const key_type& __k)
-{return __tree_.__equal_range_unique(__k);}
+{return __tree_.__equal_range_multi(__k);}
_LIBCPP_INLINE_VISIBILITY
pair 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
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare,
_K2>::value,pair>::type
-equal_range(const _K2& __k) {return
__tree_.__equal_range_unique(__k);}
+equal_range(const _K2& __k) {return
__tree_.__equal_range_multi(__k);}
template
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare,
_K2>::value,pair>::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
_LIBCPP_INLINE_VISIBILITY
typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
-count(const _K2& __k) const {return __tree_.__count_unique(__k);}
+
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng updated this revision to Diff 130812.
ng added a comment.
As per the above suggestions, enabled _multi tree search only for transparent
comparator functions, and added tests.
https://reviews.llvm.org/D42344
Files:
libcxx/include/map
libcxx/include/set
libcxx/test/std/containers/associative/map/map.ops/transparent_count.pass.cpp
libcxx/test/std/containers/associative/map/map.ops/transparent_equal_range.pass.cpp
libcxx/test/std/containers/associative/set/transparent_count.pass.cpp
libcxx/test/std/containers/associative/set/transparent_equal_range.pass.cpp
Index: libcxx/test/std/containers/associative/set/transparent_equal_range.pass.cpp
===
--- libcxx/test/std/containers/associative/set/transparent_equal_range.pass.cpp
+++ libcxx/test/std/containers/associative/set/transparent_equal_range.pass.cpp
@@ -0,0 +1,63 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+//
+
+// class set
+
+// template
+// pair equal_range(const K& x);//
+// C++14
+// template
+// pair equal_range(const K& x) const; //
+// C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+#if TEST_STD_VER <= 11
+#error "This test requires is C++14 (or later)"
+#else
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto er = s.equal_range(1);
+ long nels = 0;
+
+ for (auto it = er.first; it != er.second; it++) {
+assert(it->first == 1);
+nels++;
+ }
+
+ assert(nels == 3);
+}
+#endif
Index: libcxx/test/std/containers/associative/set/transparent_count.pass.cpp
===
--- libcxx/test/std/containers/associative/set/transparent_count.pass.cpp
+++ libcxx/test/std/containers/associative/set/transparent_count.pass.cpp
@@ -0,0 +1,54 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+//
+
+// class set
+
+// template
+// iterator lower_bound(const K& x); // C++14
+// template
+// const_iterator lower_bound(const K& x) const; // C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+#if TEST_STD_VER <= 11
+#error "This test requires is C++14 (or later)"
+#else
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto cnt = s.count(1);
+ assert(cnt == 3);
+}
+#endif
Index: libcxx/test/std/containers/associative/map/map.ops/transparent_equal_range.pass.cpp
===
--- libcxx/test/std/containers/associative/map/map.ops/transparent_equal_range.pass.cpp
+++ libcxx/test/std/containers/associative/map/map.ops/transparent_equal_range.pass.cpp
@@ -0,0 +1,63 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+//
+
+// class map
+
+// template
+// pair equal_range(const K& x); // C++14
+// template
+// pair equal_range(const K& x) const;
+// // C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+#if TEST_STD_VER <= 11
+#error "This test requires is C++14 (or later)"
+#else
+
+struct Co
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng added a comment. In https://reviews.llvm.org/D42344#983264, @mclow.lists wrote: > Shouldn't there be tests for `multimap` and `multiset`, too? Sure; will the same tests as for map/set be alright? https://reviews.llvm.org/D42344 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng updated this revision to Diff 130814.
ng added a comment.
Renamed tests for map/set, and added multimap/multiset tests
https://reviews.llvm.org/D42344
Files:
libcxx/include/map
libcxx/include/set
libcxx/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp
libcxx/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/multiset/count_transparent.pass.cpp
libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
Index: libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
@@ -0,0 +1,60 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class set
+
+// template
+// pair equal_range(const K& x);//
+// C++14
+// template
+// pair equal_range(const K& x) const; //
+// C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto er = s.equal_range(1);
+ long nels = 0;
+
+ for (auto it = er.first; it != er.second; it++) {
+assert(it->first == 1);
+nels++;
+ }
+
+ assert(nels == 3);
+}
Index: libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
@@ -0,0 +1,51 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class set
+
+// template
+// iterator lower_bound(const K& x); // C++14
+// template
+// const_iterator lower_bound(const K& x) const; // C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto cnt = s.count(1);
+ assert(cnt == 3);
+}
Index: libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
@@ -0,0 +1,61 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class multiset
+
+// template
+// pair equal_range(const K& x);//
+// C++14
+// template
+// pair equal_range(const K& x) const; //
+// C++14
+
+#include
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng updated this revision to Diff 130817.
ng added a comment.
Fix multiset variable definition in tests
https://reviews.llvm.org/D42344
Files:
libcxx/include/map
libcxx/include/set
libcxx/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp
libcxx/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/multiset/count_transparent.pass.cpp
libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
Index: libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
@@ -0,0 +1,60 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class set
+
+// template
+// pair equal_range(const K& x);//
+// C++14
+// template
+// pair equal_range(const K& x) const; //
+// C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto er = s.equal_range(1);
+ long nels = 0;
+
+ for (auto it = er.first; it != er.second; it++) {
+assert(it->first == 1);
+nels++;
+ }
+
+ assert(nels == 3);
+}
Index: libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/set/count_transparent.pass.cpp
@@ -0,0 +1,51 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class set
+
+// template
+// iterator lower_bound(const K& x); // C++14
+// template
+// const_iterator lower_bound(const K& x) const; // C++14
+
+#include
+#include
+#include
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+ using is_transparent = void;
+
+ bool operator()(const std::pair &lhs,
+ const std::pair &rhs) const {
+return lhs < rhs;
+ }
+
+ bool operator()(const std::pair &lhs, int rhs) const {
+return lhs.first < rhs;
+ }
+
+ bool operator()(int lhs, const std::pair &rhs) const {
+return lhs < rhs.first;
+ }
+};
+
+int main() {
+ std::set, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+ auto cnt = s.count(1);
+ assert(cnt == 3);
+}
Index: libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
===
--- libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
+++ libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp
@@ -0,0 +1,60 @@
+//===--===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===--===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+//
+
+// class multiset
+
+// template
+// pair equal_range(const K& x);//
+// C++14
+// template
+// pair equal_range(const K& x) const; //
+// C++14
+
+#include
+#include
+#incl
[PATCH] D42344: [libc++] Use multi-key tree search for {map, set}::{count, equal_range}
ng added a comment. Ping https://reviews.llvm.org/D42344 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
