268.md

Info

• Did you know that C++20 added std::erase_if for std::map and std::vector?

  • https://wg21.link/P1209
  • https://wg21.link/P1115

Example

int main() {
  std::vector v{1, 2, 3, 4};
  assert(4 == std::size(v));
  std::erase_if(v, [](const auto& e) { return e % 2;} );
  assert(2 == std::size(v));
  assert(v[0] == 2 and v[1] == 4);
}

https://godbolt.org/z/os1zzqTb6

Puzzle

• Can you implement erase_if for flat_map?

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type; // TODO

int main() {
  using namespace boost::ut;

  "empty"_test = [] {
    auto map = boost::container::flat_map<int, int>{};
    expect(0_u == std::size(map));
    expect(0_u == erase_if(map, [](auto){ return true; }));
    expect(0_u == std::size(map));
  };

  "one element"_test = [] {
    auto map = boost::container::flat_map<int, int>{{0, 0}};
    expect(1_u == std::size(map));
    expect(1_u == erase_if(map, [](const auto& el){ return el == std::pair{0, 0}; }));
    expect(0_u == std::size(map));
  };

  "unique elements"_test = [] {
    auto map = boost::container::flat_map<int, int>{{1, 2}, {2, 3}, {3, 4}};
    expect(3_u == std::size(map));
    expect(1_u == erase_if(map, [](const auto& el){ return el.first == 1; }));
    expect(2_u == std::size(map));
    expect(0_u == map.count(1));
    expect(1_u == map.count(2));
    expect(1_u == map.count(3));
  };

  "elements"_test = [] {
    auto map = boost::container::flat_map<int, int>{{1, 1}, {2, 2}, {3, 3}, {4, 4}};
    expect(4_u == std::size(map));
    expect(2_u == erase_if(map, [](const auto& el){ return el.first % 2 and el.second % 2; }));
    expect(2_u == std::size(map));
    expect(0_u == map.count(1));
    expect(1_u == map.count(2));
    expect(0_u == map.count(3));
    expect(1_u == map.count(4));
  };
}

https://godbolt.org/z/v1fbxh98f

Solutions

template <class... Ts>
[[nodiscard]] auto erase_if(
    boost::container::flat_map<Ts...> &map,
    std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto
        pred) -> typename boost::container::flat_map<Ts...>::size_type {
    auto num_erased = 0u;
    auto it = std::begin(map);
    while (it != std::end(map)) {
        if (pred(*it)) {
            it = map.erase(it);
            ++num_erased;
        } else {
            ++it;
        }
    }
    return num_erased;
}

https://godbolt.org/z/Gfs6GMbKK

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                           std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
 -> typename boost::container::flat_map<Ts...>::size_type {
   typename boost::container::flat_map<Ts...>::size_type erasedCount{};
   std::ranges::for_each(map, [&](const auto & m){ if (pred(m)) { erasedCount += map.erase(m.first); } });
   return erasedCount;
}

https://godbolt.org/z/TYbfM4WPz

template <class... Ts>
[[nodiscard]] constexpr auto erase_if(
    boost::container::flat_map<Ts...>& map,
    std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto
        pred) -> typename boost::container::flat_map<Ts...>::size_type {
    using map_t = std::remove_cvref_t<decltype(map)>;
    using const_iterator_t = typename map_t::const_iterator;

    auto iter = std::find_if(std::cbegin(map), std::cend(map), pred);
    typename map_t::size_type num_removed{};
    while (iter != std::cend(map)) {
        const const_iterator_t new_begin = map.erase(iter);
        num_removed += 1;
        iter = std::find_if(new_begin, std::cend(map), pred);
    }

    return num_removed;
}

https://godbolt.org/z/998GY8x7j

template <class... Ts>
[[nodiscard]] constexpr auto erase_if(
    boost::container::flat_map<Ts...>& map,
    std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto
        pred) -> typename boost::container::flat_map<Ts...>::size_type {
    using map_t = std::remove_cvref_t<decltype(map)>;
    using output_t = typename map_t::size_type;

    const auto remove_begin_iter =
        std::remove_if(std::begin(map), std::end(map), pred);
    const auto num_removed =
        static_cast<output_t>(std::distance(remove_begin_iter, std::end(map)));
    map.erase(remove_begin_iter, std::end(map));
    return num_removed;
}

https://godbolt.org/z/77Wq77Yq6

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type{
      auto erased_items = 0;
      for(const auto& item : map){
          if(pred(item)){
              map.erase(item.first);
              ++erased_items;
          }
      }
      return erased_items;
  }

https://godbolt.org/z/G488x8Tnc

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type {
  const auto end = std::remove_if(map.begin(), map.end(), pred);
  const auto n = map.size() - map.index_of(end);
  map.erase(end, map.end());
  return n;
}

https://godbolt.org/z/bYrnMn5hY

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type
  {
      auto size0 = map.size();
      for(auto iter = map.begin(); iter < map.end(); ){
          if( pred(*iter))
            iter = map.erase(iter);
          else
            iter++;
      }
      return size0 - map.size();
  }

https://godbolt.org/z/ozPfY67Kv

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type {
      auto removed_count { 0 };

      for(const auto &x : map){
        if(pred(x)){
          map.erase(x.first);
          ++removed_count;
        }
      }
      return removed_count;
  }

https://godbolt.org/z/9Ead15rEW

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type {
      const auto size = std::size(map);
      map.erase(std::remove_if(std::begin(map), std::end(map), pred), std::end(map));
      return size - std::size(map);
  }

https://godbolt.org/z/zKqob6xP8

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type{
      size_t s=0;
      auto it = map.begin();
      while(it != map.end()){
          if(pred(*it)){
              it = map.erase(it);
              s++;
          }
          else{
              it++;
          }
      }
      return s;
  }

https://godbolt.org/z/zvYodToWG

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type
{
    size_t num_erased{};
    for(auto const& el : map)
    {
        if( pred(el) )
        {
            num_erased += map.erase(el.first);
        }
    }
    return num_erased;
};

https://godbolt.org/z/Kqfz3Wdrq

template <class... Ts>
[[nodiscard]] auto erase_if(
    boost::container::flat_map<Ts...>& c,
    std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto
        pred) -> typename boost::container::flat_map<Ts...>::size_type {
  // https://en.cppreference.com/w/cpp/container/vector/erase2
  auto it = std::remove_if(c.begin(), c.end(), pred);
  auto r = std::distance(it, c.end());
  c.erase(it, c.end());
  return r;
}

https://godbolt.org/z/vfhd9bYz9

template<class... Ts>
[[nodiscard]] auto erase_if(boost::container::flat_map<Ts...>& map,
                            std::invocable<typename boost::container::flat_map<Ts...>::value_type> auto pred)
  -> typename boost::container::flat_map<Ts...>::size_type {
      auto i = std::remove_if(std::begin(map), std::end(map), pred);
      auto res = std::distance(i, std::end(map));
      map.erase(i, std::end(map));
      return res;
  }