Deleting map elements in a range-based loop

Question

I would like to drop a number of elements from a map based on some condition:

#include <unordered_map>
#include <ranges>
#include <iostream>

int main() {

    std::unordered_map<int, int> numbers = {{1,2}, {2,1}, {3,2}, {4,5}};

    auto even = [](auto entry){return entry.second %2 == 0;};
    for(auto& [key, val] : numbers | std::views::filter(even)) {
        numbers.erase(val);
    }

    for(auto& [key, val] : numbers) {
        std::cout << key << " " << val << "\n";
    }
}

But it seems there I am invalidating iterators that the range-based loop needs:

4 5
3 2
1 2

I know how to do this explicitly using iterators, but is there a nice and concise range-based way to delete elements based on a filter?

How is this not a duplicate? – Peter Mortensen May 19 '23 at 16:33 — Peter Mortensen, May 19 '23 at 16:33

score 4 · Accepted Answer · edited Mar 23 '23 at 15:27

4

I suggest you use std::erase_if(), like below:

std::erase_if(numbers, [](auto entry) {return entry.second % 2 == 0; });

If you want a ranges solution, and you do not need in-place changing, you can do something like below (this code compiles only in C++23):

numbers = numbers | std::views::filter(even) | std::ranges::to<decltype(numbers)>();

I am not sure, but maybe the below code is better performance than normal ranges code as above, based on documentation:

auto temp_numbers = numbers | std::views::filter(even) | std::ranges::to<decltype(numbers)>();
numbers.swap(temp_numbers);

As you can see in the operator= for std::unordered_map, the complexity of its move assignment operator is linear, but the complexity of its move constructor is constant, and the complexity of its swap() method is constant, so it seems to be better performance. But, I do not have any benchmark for this.

edited Mar 23 '23 at 15:27

Remy Lebeau

555,201
31
458
770

answered Mar 23 '23 at 10:18

sorosh_sabz

2,356
2
32
53

`numbers=std::move(...);` might be better than `swap`. – Red.Wave Mar 23 '23 at 18:54
@Red.Wave as I surprise, the documentation says, move constructor, has **linear** complexity, instead of **constant`, so I have to use `swap`, did you have any idea, why? – sorosh_sabz Mar 24 '23 at 01:18
@sorosh_sabz, No. The linear time complexity belongs to allocator-using overload. The move constructor runs in constant-time. – Red.Wave Mar 24 '23 at 08:23
@Red.Wave I do not speak about move constructor, I speak about move assignment, `numbers=std::move(...);` calls move assignment, not move constructor, and move assignment as you can see in https://en.cppreference.com/w/cpp/container/unordered_map/operator%3D, has linear complexity, independent of allocator type. – sorosh_sabz Mar 24 '23 at 13:00

Deleting map elements in a range-based loop

1 Answers1