Efficient way to delete a value from an unordered_map, when given just the value C++

Question

I have an abstract class called Object and I am using std::unordered_map<int, Object*> objects to contain these Objects within a class called DataSet. Each object has an id associated with it.

Normally, when deleting an object from my unordered_map, I can just do iterator = find(id) and then call erase on that iterator.

This is easy and efficient. The problem is, I have to implement a method to delete an entry/pair by value, rather then by the key (which was my id). This gives me the following prototype:

int DataSet::DeleteObject(Object* object)

What is the most efficient way of accomplishing this though? I'm thinking I can do something like this:

if(object){
    for(auto kv : objects) {
        if(kv.second == object) {
            objects.erase(kv);
        }
    }
    return 1;
}

But it seems very inefficient. So what would be the most efficient way to accomplish this?

Are you sure there is only single object matching with your condition? If you need to remove multiple objects, why there is return after first erase? — Steephen
– Steephen, Commented May 19, 2015 at 20:14
More importantly, does it seem correct? What if the value exists multiple times? Or not at all? And erase(kv) doesn't work. You have to erase by key, not by value, i.e. erase(kv.first). — Kerrek SB
– Kerrek SB, Commented May 19, 2015 at 20:15
I don't think there is an efficient way to remove an object from a map with only its value. Specially if the map is unordered. — Alexandre Severino
– Alexandre Severino, Commented May 19, 2015 at 20:15

Kerrek SB · Accepted Answer · 2015-05-19 20:18:11Z

8

Don't perform the lookup twice; erase via iterator:

for (auto it = m.begin(); it != m.end(); )
{
    if (it->second == needle) { m.erase(it++); }
    else                      { ++it;          }
}

This deletes all occurrences of needle. If you want to erase at most the first occurrence, a simpler loop will do:

for (auto it = m.begin(); it != m.end(); ++it)
{
    if (it->second == needle) { m.erase(it); break; }
}

If you want to erase exactly one element, you need to add a check that you found any needles. This can be achieved with find_if, which may also be used as a variation of the previous algorithm:

auto it = std::find_if(m.begin(), m.end(),
                       [&needle](const auto & p) { return p.second == needle; });

if (it != m.end()) { m.erase(it); }
else               { /* no such element! */ }

answered May 19, 2015 at 20:18

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

finnan Over a year ago

It's a matter of taste but I prefer using it = m.erase(it) instead of m.erase(it++)

Collectives™ on Stack Overflow

Efficient way to delete a value from an unordered_map, when given just the value C++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related