33

There are several answers on StackOverflow that suggest that the following loop is a fine way to erase elements from a std::unordered_map that satisfy some predicate pred:

std::unordered_map<...> m;
auto it = m.begin();
while (it != m.end())
{
    if (pred(*it))
        it = m.erase(it);
    else
        ++it;
}

I'm specifically interested in C++11 (as opposed to C++14), and the following ominous note on cppreference.com suggests that the above loop depends on undefined behavior and may not work in C++11 after all:

The order of the elements that are not erased is preserved (this makes it possible to erase individual elements while iterating through the container) (since C++14)

See also Title 2356. Stability of erasure in unordered associative containers which contains a requested wording change to Working Draft N3797 item 14 on page 754 (the additional phrase beginning ", and preserve the relative order ...").

This wording is relative to N3797.

Modify [unord.req], p14 as indicated:

-14- The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. The erase members shall invalidate only iterators and references to the erased elements, and preserve the relative order of the elements that are not erased.

If my interpretation of the note from cppreference.com is correct, and the above loop depends on undefined behavior in C++11, what's the most efficient way to solve this problem in C++11?

Richard Chambers
  • 16,643
  • 4
  • 81
  • 106
foxcub
  • 2,517
  • 2
  • 27
  • 27
  • 2
    Usually when a constraint is strengthened like that, it's because all the compilers represented by committee members are already conforming. You're right to be nervous though. – Mark Ransom Jul 19 '16 at 21:41
  • 1
    @MarkRansom Is there a way to be safe? I.e., what's the correct way to do this under the C++11 standard? – foxcub Jul 19 '16 at 21:44
  • I suspect there *wasn't* a way to be guaranteed safe, thus the change to the standard. – Mark Ransom Jul 19 '16 at 22:31
  • 1
    Found [another SO Q/A](http://stackoverflow.com/questions/25047241/c11-is-it-safe-to-remove-individual-elements-from-stdunordered-map-while-it?rq=1) that links to [Issue 2356](http://wg21.cmeerw.net/lwg/issue2356), which clarifies the bit about all the compilers being conforming. – foxcub Jul 20 '16 at 00:05
  • Can't you just take repeatedly `mymap.begin()` in a loop and remove it while it is not `mymap.end()`? – CygnusX1 Aug 25 '20 at 06:31

4 Answers4

19

To comply with C++11 you're unfortunately a bit limited in how you can tackle this. Your options basically boil down to:

  1. Iterate over the unordered_map and build a list of keys to delete like so:

    //std::unordered_map<...> mymap;
std::vector<decltype(mymap)::key_type> vec;
for (auto&& i : mymap)
    if (/*compare i*/)
        vec.emplace_back(i.first);
for (auto&& key : vec)
    mymap.erase(key);

  2. Iterate over the object and reset if we find something to remove - I'd really only recommend this for small datasets. those of you who feel goto is unconditionally bad, well, this option is arguably bad.

    //std::unordered_map<...> mymap;
reset:
for (auto&& i : mymap)
    if (/*compare i*/) {
        mymap.erase(i.first);
        goto reset;
    }

  3. As a somewhat out there option, you could also just create a new unordered_map and move the elements that you want to keep. This is arguably a good option when you have more to delete than to keep.

    //std::unordered_map<...> mymap;
decltype(mymap) newmap;
for (auto&& i : mymap)
    if (/*i is an element we want*/)
        newmap.emplace(std::move(i));
mymap.swap(newmap);
Olipro
  • 3,489
  • 19
  • 25
8

Use erase_if (c++20) instead of a loop (see https://en.cppreference.com/w/cpp/container/unordered_map/erase_if)

Example for removing odd keys from a map:

std::unordered_map<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                                    {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};

const auto count = std::erase_if(data, [](const auto& item) {
    auto const& [key, value] = item;
    return (key & 1) == 1;
});
Dmitrii A
  • 89
  • 1
  • 1
2

Well, you can always do this:

std::unordered_map<...> m;
std::vector<key_type> needs_removing;
for(auto&& pair : m)
{
    if (pred(pair))
        needs_removing.push_back(pair.first);
}
for(auto&& key : needs_removing)
    m.erase(key);

It's slower, but the complexity is the same.

Pubby
  • 51,882
  • 13
  • 139
  • 180
-4

Always consult the stl-algorithms first

This one seems to be the wanted: http://www.cplusplus.com/reference/algorithm/remove_if/

For an overview: http://www.cplusplus.com/reference/algorithm/

EDIT cppreference has an similar example at the bottom of the site. It works with a c++11 compiler.

jonas_toth
  • 872
  • 5
  • 8
  • 3
    That doesn't work with any associative container. http://en.cppreference.com/w/cpp/algorithm/remove – foxcub Jul 19 '16 at 21:36
  • Similar to what? What example works with C++11 compiler? – foxcub Jul 19 '16 at 21:38
  • 1
    Or rather how do you know that it works with C++11 compiler? And not that the compiler is implicitly using C++14 mode? – foxcub Jul 19 '16 at 21:39
  • you can choose the compiler version and in parantheses is the standard. i assume this information is correct there. it works with gcc-4.8, that one has only c++11 – jonas_toth Jul 19 '16 at 21:43
  • 2
    @jonas_toth From the std::remove_if page you linked: `These algorithms cannot be used with associative containers such as std::set and std::map because ForwardIt does not dereference to a MoveAssignable type (the keys in these containers are not modifiable)`. http://ideone.com/5cWOF9 vs http://ideone.com/B7AmNf. – kfsone Jul 19 '16 at 21:55
  • yes thats right. the looping approach seems to work though – jonas_toth Jul 19 '16 at 21:57
  • @jonas_toth so... your answer says that he wants to use remove_if, but you agree that's wrong. Interesting. – kfsone Jul 19 '16 at 22:17