summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-09-09 19:13:17 -0700
committerGravatar Derek Mauro <dmauro@google.com>2020-09-10 10:10:40 -0400
commitf2c9c663db28a8a898c1fc8c8e06ab9b93eb5610 (patch)
tree2a6917d880a84a4dc4c95d21ffed0a9fe07d470c /absl/container
parent3c8b5d7587dc8ecf730ce9996c89e156e408c3ed (diff)
Export of internal Abseil changes
-- cfb567ed02096320663d882d2c0c2fb7db7af1e4 by Derek Mauro <dmauro@google.com>: Upgrade to GCC 10.2.0, Bazel 3.5.0, and CMake 3.18.2 PiperOrigin-RevId: 330847323 -- 5dcb9ce14d92315163079366a91c43cbd5184ea4 by Evan Brown <ezb@google.com>: Optimize equal_range() by avoiding the call to upper_bound() when possible. We need to support heterogeneous comparators that have different behavior when comparing key_type to non-key_type. See the new test. Also update the comment for `key_compare_to_adapter`. PiperOrigin-RevId: 330794444 -- 744405dbda5513527d74094a5c3b9db1e0927693 by Gennadiy Rozental <rogeeff@google.com>: Introduce trampoline for friend access to avoid friending routines and classes from different namespace. PiperOrigin-RevId: 330773156 -- a195d1226576f8a7bb5671f3e42d1021b827fad9 by Abseil Team <absl-team@google.com>: Fix an incorrect version number test for std::variant availability in tvOs. PiperOrigin-RevId: 330759480 -- 58b02eb9159a577953676d9928cb26b30068b847 by Derek Mauro <dmauro@google.com>: Use c++20 instead of c++2a now that it is supported by GCC PiperOrigin-RevId: 330559797 GitOrigin-RevId: cfb567ed02096320663d882d2c0c2fb7db7af1e4 Change-Id: I0e0d68409c95da42f5609920155ba5694ade8df0
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/btree_test.cc34
-rw-r--r--absl/container/internal/btree.h54
-rw-r--r--absl/container/internal/btree_container.h2
3 files changed, 81 insertions, 9 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 43704206..1bfa0c20 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2580,6 +2580,40 @@ TEST(Btree, NodeHandleMutableKeyAccess) {
}
#endif
+struct MultiKey {
+ int i1;
+ int i2;
+};
+
+struct MultiKeyComp {
+ using is_transparent = void;
+ bool operator()(const MultiKey a, const MultiKey b) const {
+ if (a.i1 != b.i1) return a.i1 < b.i1;
+ return a.i2 < b.i2;
+ }
+ bool operator()(const int a, const MultiKey b) const { return a < b.i1; }
+ bool operator()(const MultiKey a, const int b) const { return a.i1 < b; }
+};
+
+// Test that when there's a heterogeneous comparator that behaves differently
+// for some heterogeneous operators, we get equal_range() right.
+TEST(Btree, MultiKeyEqualRange) {
+ absl::btree_set<MultiKey, MultiKeyComp> set;
+
+ for (int i = 0; i < 100; ++i) {
+ for (int j = 0; j < 100; ++j) {
+ set.insert({i, j});
+ }
+ }
+
+ for (int i = 0; i < 100; ++i) {
+ auto equal_range = set.equal_range(i);
+ EXPECT_EQ(equal_range.first->i1, i);
+ EXPECT_EQ(equal_range.first->i2, 0);
+ EXPECT_EQ(std::distance(equal_range.first, equal_range.second), 100) << i;
+ }
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 5986bb21..002ccc1e 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -137,15 +137,14 @@ struct StringBtreeDefaultGreater {
};
// A helper class to convert a boolean comparison into a three-way "compare-to"
-// comparison that returns a negative value to indicate less-than, zero to
-// indicate equality and a positive value to indicate greater-than. This helper
+// comparison that returns an `absl::weak_ordering`. This helper
// class is specialized for less<std::string>, greater<std::string>,
// less<string_view>, greater<string_view>, less<absl::Cord>, and
// greater<absl::Cord>.
//
// key_compare_to_adapter is provided so that btree users
// automatically get the more efficient compare-to code when using common
-// google string types with common comparison functors.
+// Abseil string types with common comparison functors.
// These string-like specializations also turn on heterogeneous lookup by
// default.
template <typename Compare>
@@ -189,6 +188,9 @@ struct common_params {
// If Compare is a common comparator for a string-like type, then we adapt it
// to use heterogeneous lookup and to be a key-compare-to comparator.
using key_compare = typename key_compare_to_adapter<Compare>::type;
+ // True when key_compare has been adapted to StringBtreeDefault{Less,Greater}.
+ using is_key_compare_adapted =
+ absl::negation<std::is_same<key_compare, Compare>>;
// A type which indicates if we have a key-compare-to functor or a plain old
// key-compare functor.
using is_key_compare_to = btree_is_key_compare_to<key_compare, Key>;
@@ -1015,6 +1017,8 @@ class btree {
using is_key_compare_to = typename Params::is_key_compare_to;
using init_type = typename Params::init_type;
using field_type = typename node_type::field_type;
+ using is_multi_container = typename Params::is_multi_container;
+ using is_key_compare_adapted = typename Params::is_key_compare_adapted;
// We use a static empty node for the root/leftmost/rightmost of empty btrees
// in order to avoid branching in begin()/end().
@@ -1164,15 +1168,13 @@ class btree {
}
// Finds the range of values which compare equal to key. The first member of
- // the returned pair is equal to lower_bound(key). The second member pair of
- // the pair is equal to upper_bound(key).
+ // the returned pair is equal to lower_bound(key). The second member of the
+ // pair is equal to upper_bound(key).
template <typename K>
- std::pair<iterator, iterator> equal_range(const K &key) {
- return {lower_bound(key), upper_bound(key)};
- }
+ std::pair<iterator, iterator> equal_range(const K &key);
template <typename K>
std::pair<const_iterator, const_iterator> equal_range(const K &key) const {
- return {lower_bound(key), upper_bound(key)};
+ return const_cast<btree *>(this)->equal_range(key);
}
// Inserts a value into the btree only if it does not already exist. The
@@ -1891,6 +1893,40 @@ btree<P>::btree(const btree &other)
}
template <typename P>
+template <typename K>
+auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> {
+ const iterator lower = lower_bound(key);
+ // TODO(ezb): we should be able to avoid this comparison when there's a
+ // three-way comparator.
+ if (lower == end() || compare_keys(key, lower.key())) return {lower, lower};
+
+ const iterator next = std::next(lower);
+ // When the comparator is heterogeneous, we can't assume that comparison with
+ // non-`key_type` will be equivalent to `key_type` comparisons so there
+ // could be multiple equivalent keys even in a unique-container. But for
+ // heterogeneous comparisons from the default string adapted comparators, we
+ // don't need to worry about this.
+ if (!is_multi_container::value &&
+ (std::is_same<K, key_type>::value || is_key_compare_adapted::value)) {
+ // The next iterator after lower must point to a key greater than `key`.
+ // Note: if this assert fails, then it may indicate that the comparator does
+ // not meet the equivalence requirements for Compare
+ // (see https://en.cppreference.com/w/cpp/named_req/Compare).
+ assert(next == end() || compare_keys(key, next.key()));
+ return {lower, next};
+ }
+ // Try once more to avoid the call to upper_bound() if there's only one
+ // equivalent key. This should prevent all calls to upper_bound() in cases of
+ // unique-containers with heterogeneous comparators in which all comparison
+ // operators are equivalent.
+ if (next == end() || compare_keys(key, next.key())) return {lower, next};
+
+ // In this case, we need to call upper_bound() to avoid worst case O(N)
+ // behavior if we were to iterate over equal keys.
+ return {lower, upper_bound(key)};
+}
+
+template <typename P>
template <typename K, typename... Args>
auto btree<P>::insert_unique(const K &key, Args &&... args)
-> std::pair<iterator, bool> {
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3b2e8a9e..137614f8 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -314,6 +314,8 @@ class btree_set_container : public btree_container<Tree> {
}
// Deletion routines.
+ // TODO(ezb): we should support heterogeneous comparators that have different
+ // behavior for K!=key_type.
template <typename K = key_type>
size_type erase(const key_arg<K> &key) {
return this->tree_.erase_unique(key);