Author: ericwf Date: Fri Feb 9 18:53:47 2018 New Revision: 324799 URL: http://llvm.org/viewvc/llvm-project?rev=324799&view=rev Log: Use multi-key tree search for {map, set}::{count, equal_range}
Patch from ngolovl...@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. Added: libcxx/trunk/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/multiset/count_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/set/count_transparent.pass.cpp libcxx/trunk/test/std/containers/associative/set/equal_range_transparent.pass.cpp Modified: libcxx/trunk/include/map libcxx/trunk/include/set Modified: libcxx/trunk/include/map URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/map?rev=324799&r1=324798&r2=324799&view=diff ============================================================================== --- libcxx/trunk/include/map (original) +++ libcxx/trunk/include/map Fri Feb 9 18:53:47 2018 @@ -1228,7 +1228,7 @@ public: 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 @@ public: 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: Modified: libcxx/trunk/include/set URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/set?rev=324799&r1=324798&r2=324799&view=diff ============================================================================== --- libcxx/trunk/include/set (original) +++ libcxx/trunk/include/set Fri Feb 9 18:53:47 2018 @@ -668,7 +668,7 @@ public: 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) @@ -715,11 +715,11 @@ public: 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 }; Added: libcxx/trunk/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -0,0 +1,50 @@ +//===----------------------------------------------------------------------===// +// +// 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); +} Added: libcxx/trunk/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} Added: libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/count_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -0,0 +1,50 @@ +//===----------------------------------------------------------------------===// +// +// 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); +} Added: libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/multimap/multimap.ops/equal_range_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} Added: libcxx/trunk/test/std/containers/associative/multiset/count_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/multiset/count_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/multiset/count_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/multiset/count_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} Added: libcxx/trunk/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/multiset/equal_range_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} Added: libcxx/trunk/test/std/containers/associative/set/count_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/set/count_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/set/count_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/set/count_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} Added: libcxx/trunk/test/std/containers/associative/set/equal_range_transparent.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/associative/set/equal_range_transparent.pass.cpp?rev=324799&view=auto ============================================================================== --- libcxx/trunk/test/std/containers/associative/set/equal_range_transparent.pass.cpp (added) +++ libcxx/trunk/test/std/containers/associative/set/equal_range_transparent.pass.cpp Fri Feb 9 18:53:47 2018 @@ -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 + +// <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); +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits