[libc++] Use multi-key tree search for {map, set}::{count, equal_range}

[ng]

Summary

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.

[EricWF]

Could you provide tests that demonstrate the previously incorrect behavior?

[rsmith]

Shouldn't we be changing only the heterogeneous functions here?

[EricWF]

@rsmith Yes. I agree this should only be applied in that case

[ng]

As per the above suggestions, enabled _multi tree search only for transparent comparator functions, and added tests.

[mclow.lists]

Sometimes you get lucky ;-)
I have a task for next week that says "The transparent lookup stuff in the associative containers needs tests", and here is this patch.

Instead of "transparent_count.pass.cpp", please name the test "count_transparent.pass.cpp" so it will sort with all the other count tests.

libcxx/test/std/containers/associative/map/map.ops/transparent_count.pass.cpp

25 ↗

(On Diff #130812)

Instead of this, just put

//  UNSUPPORTED:  c++98, c++03, c++11

near the top of the file.

libcxx/test/std/containers/associative/map/map.ops/transparent_equal_range.pass.cpp

28 ↗

(On Diff #130812)

Same here.

libcxx/test/std/containers/associative/set/transparent_count.pass.cpp

27 ↗

(On Diff #130812)

same here.

libcxx/test/std/containers/associative/set/transparent_equal_range.pass.cpp

29 ↗

(On Diff #130812)

and here.

[mclow.lists]

This comment has been deleted.

[ng]

In 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?

[mclow.lists]

In D42344#983265, @ng wrote:

In 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?

Actually, I think there are already tests for multimap and multiset.
(which is why I deleted my comment)

But the tests there are not like these, where the comparator uses only part of the key.
So, yes; same tests would be OK - but you might want to adjust the data so that there are duplicate keys.

[ng]

Renamed tests for map/set, and added multimap/multiset tests

[ng]

Fix multiset variable definition in tests

[ng]

Ping

[EricWF]

This LGTM.

[ng]

Could you please commit this on my behalf? I don't have commit access.

[EricWF]

Committed as r324799.

Thank you!

libcxx/include/map

#endif
 
     _LIBCPP_INLINE_VISIBILITY
     size_type      count(const key_type& __k) const
         {return __tree_.__count_unique(__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)
         {return __tree_.lower_bound(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator lower_bound(const key_type& __k) const
         {return __tree_.lower_bound(__k);}
 #if _LIBCPP_STD_VER > 11
pair<iterator,iterator> equal_range(const key_type& __k)
         {return __tree_.__equal_range_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
         {return __tree_.__equal_range_unique(__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:
     typedef typename __base::__node                    __node;
     typedef typename __base::__node_allocator          __node_allocator;
     typedef typename __base::__node_pointer            __node_pointer;
     typedef typename __base::__node_base_pointer       __node_base_pointer;
     typedef typename __base::__parent_pointer          __parent_pointer;

libcxx/include/set

#endif
 
     _LIBCPP_INLINE_VISIBILITY
     size_type      count(const key_type& __k) const
         {return __tree_.__count_unique(__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)
         {return __tree_.lower_bound(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator lower_bound(const key_type& __k) const
         {return __tree_.lower_bound(__k);}
 #if _LIBCPP_STD_VER > 11
pair<iterator,iterator> equal_range(const key_type& __k)
         {return __tree_.__equal_range_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
         {return __tree_.__equal_range_unique(__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
 };
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Compare, class _Allocator>
 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
     : __tree_(_VSTD::move(__s.__tree_), __a)

libcxx/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <map>
+
+// class map
+
+// template<typename K>
+//   size_type count(const K& x) const;        // C++14
+
+#include <cassert>
+#include <map>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::map<std::pair<int, int>, int, Comp> s{
+      {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}};
+
+  auto cnt = s.count(1);
+  assert(cnt == 3);
+}

libcxx/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <map>
+
+// class map
+
+// template<typename K>
+//         pair<iterator,iterator>             equal_range(const K& x); // C++14
+// template<typename K>
+//         pair<const_iterator,const_iterator> equal_range(const K& x) const;
+//         // C++14
+
+#include <cassert>
+#include <map>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::map<std::pair<int, int>, int, Comp> s{
+      {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}};
+
+  auto er = s.equal_range(1);
+  long nels = 0;
+
+  for (auto it = er.first; it != er.second; it++) {
+    assert(it->first.first == 1);
+    nels++;
+  }
+
+  assert(nels == 3);
+}

libcxx/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <map>
+
+// class multimap
+
+// template<typename K>
+//   size_type count(const K& x) const;        // C++14
+
+#include <cassert>
+#include <map>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::multimap<std::pair<int, int>, int, Comp> s{
+      {{2, 1}, 1}, {{1, 1}, 2}, {{1, 1}, 3}, {{1, 1}, 4}, {{2, 2}, 5}};
+
+  auto cnt = s.count(1);
+  assert(cnt == 3);
+}

libcxx/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <map>
+
+// class multimap
+
+// template<typename K>
+//         pair<iterator,iterator>             equal_range(const K& x); // C++14
+// template<typename K>
+//         pair<const_iterator,const_iterator> equal_range(const K& x) const;
+//         // C++14
+
+#include <cassert>
+#include <map>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::multimap<std::pair<int, int>, int, Comp> s{
+      {{2, 1}, 1}, {{1, 1}, 2}, {{1, 1}, 3}, {{1, 1}, 4}, {{2, 2}, 5}};
+
+  auto er = s.equal_range(1);
+  long nels = 0;
+
+  for (auto it = er.first; it != er.second; it++) {
+    assert(it->first.first == 1);
+    nels++;
+  }
+
+  assert(nels == 3);
+}

libcxx/test/std/containers/associative/multiset/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <set>
+
+// class multiset
+
+// template<typename K>
+//     iterator lower_bound(const K& x);              // C++14
+// template<typename K>
+//     const_iterator lower_bound(const K& x) const;  // C++14
+
+#include <cassert>
+#include <set>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::multiset<std::pair<int, int>, Comp> s{{2, 1}, {1, 1}, {1, 1}, {1, 1}, {2, 2}};
+
+  auto cnt = s.count(1);
+  assert(cnt == 3);
+}

libcxx/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <set>
+
+// class multiset
+
+// template<typename K>
+//     pair<iterator,iterator>             equal_range(const K& x);        //
+//     C++14
+// template<typename K>
+//     pair<const_iterator,const_iterator> equal_range(const K& x) const;  //
+//     C++14
+
+#include <cassert>
+#include <set>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::multiset<std::pair<int, int>, Comp> s{{2, 1}, {1, 1}, {1, 1}, {1, 1}, {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);
+}

libcxx/test/std/containers/associative/set/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <set>
+
+// class set
+
+// template<typename K>
+//     iterator lower_bound(const K& x);              // C++14
+// template<typename K>
+//     const_iterator lower_bound(const K& x) const;  // C++14
+
+#include <cassert>
+#include <set>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::set<std::pair<int, int>, Comp> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+  auto cnt = s.count(1);
+  assert(cnt == 3);
+}

libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+// <set>
+
+// class set
+
+// template<typename K>
+//     pair<iterator,iterator>             equal_range(const K& x);        //
+//     C++14
+// template<typename K>
+//     pair<const_iterator,const_iterator> equal_range(const K& x) const;  //
+//     C++14
+
+#include <cassert>
+#include <set>
+#include <utility>
+
+#include "min_allocator.h"
+#include "private_constructor.hpp"
+#include "test_macros.h"
+
+struct Comp {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int> &lhs,
+                  const std::pair<int, int> &rhs) const {
+    return lhs < rhs;
+  }
+
+  bool operator()(const std::pair<int, int> &lhs, int rhs) const {
+    return lhs.first < rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int> &rhs) const {
+    return lhs < rhs.first;
+  }
+};
+
+int main() {
+  std::set<std::pair<int, int>, 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);
+}