Info
-
Did you know that C++20 added
std::erase_if
for std::map and std::vector?
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);
}
Puzzle
- Can you implement
erase_if
forflat_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));
};
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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();
}
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;
}
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);
}
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;
}
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;
};
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;
}
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;
}