cxx20_erase_forward_list.h 1.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142
  1. // Copyright 2021 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_CONTAINERS_CXX20_ERASE_FORWARD_LIST_H_
  5. #define BASE_CONTAINERS_CXX20_ERASE_FORWARD_LIST_H_
  6. #include <forward_list>
  7. #include <iterator>
  8. namespace base {
  9. // Erase/EraseIf are based on C++20's uniform container erasure API:
  10. // - https://eel.is/c++draft/libraryindex#:erase
  11. // - https://eel.is/c++draft/libraryindex#:erase_if
  12. // They provide a generic way to erase elements from a container.
  13. // The functions here implement these for the standard containers until those
  14. // functions are available in the C++ standard.
  15. // Note: there is no std::erase for standard associative containers so we don't
  16. // have it either.
  17. template <class T, class Allocator, class Predicate>
  18. size_t EraseIf(std::forward_list<T, Allocator>& container, Predicate pred) {
  19. // Note: std::forward_list does not have a size() API, thus we need to use the
  20. // O(n) std::distance work-around. However, given that EraseIf is O(n)
  21. // already, this should not make a big difference.
  22. size_t old_size = std::distance(container.begin(), container.end());
  23. container.remove_if(pred);
  24. return old_size - std::distance(container.begin(), container.end());
  25. }
  26. template <class T, class Allocator, class Value>
  27. size_t Erase(std::forward_list<T, Allocator>& container, const Value& value) {
  28. // Unlike std::forward_list::remove, this function template accepts
  29. // heterogeneous types and does not force a conversion to the container's
  30. // value type before invoking the == operator.
  31. return EraseIf(container, [&](const T& cur) { return cur == value; });
  32. }
  33. } // namespace base
  34. #endif // BASE_CONTAINERS_CXX20_ERASE_FORWARD_LIST_H_