Explicitly expose EraseIf in flat_map/flat_set
Before this CL, EraseIf was defined in flat_tree.h, but that file can
only be included by the flat_map/flat_set implementation, as it's an
internal file with limited visibility.
This CL will move the flat_tree's base EraseIf implementation to the
internal namespace and define specific variants of it in flat_map.h and
flat_set.h
Bug: webrtc:12689
Change-Id: Idf31915f4abe36ad302c1da669b702974a27c647
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/225206
Commit-Queue: Victor Boivie <boivie@webrtc.org>
Reviewed-by: Danil Chapovalov <danilchap@webrtc.org>
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#34431}
diff --git a/rtc_base/containers/flat_map.h b/rtc_base/containers/flat_map.h
index 9fa8056..1dfae51 100644
--- a/rtc_base/containers/flat_map.h
+++ b/rtc_base/containers/flat_map.h
@@ -359,6 +359,16 @@
tree::swap(other);
}
+// Erases all elements that match predicate. It has O(size) complexity.
+//
+// flat_map<int, Timestamp> last_times;
+// ...
+// EraseIf(last_times,
+// [&](const auto& element) { return now - element.second > kLimit; });
+
+// NOLINTNEXTLINE(misc-unused-using-decls)
+using ::webrtc::flat_containers_internal::EraseIf;
+
} // namespace webrtc
#endif // RTC_BASE_CONTAINERS_FLAT_MAP_H_
diff --git a/rtc_base/containers/flat_map_unittest.cc b/rtc_base/containers/flat_map_unittest.cc
index 3ece2ff..8f0b77f 100644
--- a/rtc_base/containers/flat_map_unittest.cc
+++ b/rtc_base/containers/flat_map_unittest.cc
@@ -429,5 +429,26 @@
m.erase(m.cbegin());
}
+TEST(FlatMap, SupportsEraseIf) {
+ flat_map<MoveOnlyInt, MoveOnlyInt> m;
+ m.insert(std::make_pair(MoveOnlyInt(1), MoveOnlyInt(1)));
+ m.insert(std::make_pair(MoveOnlyInt(2), MoveOnlyInt(2)));
+ m.insert(std::make_pair(MoveOnlyInt(3), MoveOnlyInt(3)));
+ m.insert(std::make_pair(MoveOnlyInt(4), MoveOnlyInt(4)));
+ m.insert(std::make_pair(MoveOnlyInt(5), MoveOnlyInt(5)));
+
+ EraseIf(m, [to_be_removed = MoveOnlyInt(2)](
+ const std::pair<MoveOnlyInt, MoveOnlyInt>& e) {
+ return e.first == to_be_removed;
+ });
+
+ EXPECT_EQ(m.size(), 4u);
+ ASSERT_TRUE(m.find(MoveOnlyInt(1)) != m.end());
+ ASSERT_FALSE(m.find(MoveOnlyInt(2)) != m.end());
+ ASSERT_TRUE(m.find(MoveOnlyInt(3)) != m.end());
+ ASSERT_TRUE(m.find(MoveOnlyInt(4)) != m.end());
+ ASSERT_TRUE(m.find(MoveOnlyInt(5)) != m.end());
+}
+
} // namespace
} // namespace webrtc
diff --git a/rtc_base/containers/flat_set.h b/rtc_base/containers/flat_set.h
index 5c43179..e088cc5 100644
--- a/rtc_base/containers/flat_set.h
+++ b/rtc_base/containers/flat_set.h
@@ -161,6 +161,18 @@
using flat_set = typename ::webrtc::flat_containers_internal::
flat_tree<Key, webrtc::identity, Compare, Container>;
+// ----------------------------------------------------------------------------
+// General operations.
+
+// Erases all elements that match predicate. It has O(size) complexity.
+//
+// flat_set<int> numbers;
+// ...
+// EraseIf(numbers, [](int number) { return number % 2 == 1; });
+
+// NOLINTNEXTLINE(misc-unused-using-decls)
+using ::webrtc::flat_containers_internal::EraseIf;
+
} // namespace webrtc
#endif // RTC_BASE_CONTAINERS_FLAT_SET_H_
diff --git a/rtc_base/containers/flat_set_unittest.cc b/rtc_base/containers/flat_set_unittest.cc
index 831afed..617db92 100644
--- a/rtc_base/containers/flat_set_unittest.cc
+++ b/rtc_base/containers/flat_set_unittest.cc
@@ -125,5 +125,25 @@
s.erase(s.begin());
s.erase(s.cbegin());
}
+
+TEST(FlatSet, SupportsEraseIf) {
+ flat_set<MoveOnlyInt> s;
+ s.emplace(MoveOnlyInt(1));
+ s.emplace(MoveOnlyInt(2));
+ s.emplace(MoveOnlyInt(3));
+ s.emplace(MoveOnlyInt(4));
+ s.emplace(MoveOnlyInt(5));
+
+ EraseIf(s, [to_be_removed = MoveOnlyInt(2)](const MoveOnlyInt& elem) {
+ return elem == to_be_removed;
+ });
+
+ EXPECT_EQ(s.size(), 4u);
+ ASSERT_TRUE(s.find(MoveOnlyInt(1)) != s.end());
+ ASSERT_FALSE(s.find(MoveOnlyInt(2)) != s.end());
+ ASSERT_TRUE(s.find(MoveOnlyInt(3)) != s.end());
+ ASSERT_TRUE(s.find(MoveOnlyInt(4)) != s.end());
+ ASSERT_TRUE(s.find(MoveOnlyInt(5)) != s.end());
+}
} // namespace
} // namespace webrtc
diff --git a/rtc_base/containers/flat_tree.h b/rtc_base/containers/flat_tree.h
index 046eef1..1b02cce 100644
--- a/rtc_base/containers/flat_tree.h
+++ b/rtc_base/containers/flat_tree.h
@@ -1076,8 +1076,6 @@
return emplace_key_args(key, std::forward<Args>(args)...);
}
-} // namespace flat_containers_internal
-
// ----------------------------------------------------------------------------
// Free functions.
@@ -1091,12 +1089,14 @@
webrtc::flat_containers_internal::
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>& container,
Predicate pred) {
- auto it = std::remove_if(container.begin(), container.end(), pred);
+ auto it = std::remove_if(container.begin(), container.end(),
+ std::forward<Predicate>(pred));
size_t removed = std::distance(it, container.end());
container.erase(it, container.end());
return removed;
}
+} // namespace flat_containers_internal
} // namespace webrtc
#endif // RTC_BASE_CONTAINERS_FLAT_TREE_H_
