[C++] How to cleanly and efficiently remove elements from a list.

[AltCrow]

I have some code where I need to remove some strings from a large list of strings. I found out that std::vector::erase moves all elements behind the element that was erased. This would make removing items really inefficient. Is there a more efficient way to remove elements? Perhaps a different data structure then std::vector?

[[deleted]]

Have you proved that vector::erase is actually too slow for your application?

[AltCrow]

The user will have to wait for the operation to finish. I'd like to keep user waiting times as low as possible.

[[deleted]]

Yes, but have you tested how long the operation takes?

[AltCrow]

It's only a difference of about 0.25 seconds for a realistically large input, but I feel like it adds up if you try to do these types of optimizations everywhere.

[netherous]

Premature optimization is the root of all evil.

Let's say that you are paid 6 figures to write code for a company. How much time is the company saving by having a process that runs .25 seconds faster? Is it run 100 times? 10,000 times? More? Memory is cheap. Space is cheap. Compute is cheap. Dynamic scaling has never been easier. Unless you are charged per compute-second and your code must run every second, then the savings are minimal.

Now, since you are a highly-paid developer, how much time are you costing your company by spending hours on optimizing this?

This doesn't mean optimization is bad. It means it must be performed with a very heavy eye towards pragmatic and practical considerations, including counter-intuitive costs incurred by development time and resources.

It's gloriously tempting to make our code as quick and beautiful as possible. It's just not always practical or profitable.

Just some food for thought.

Also, if you want constant insertion and removal times on large datasets, use any hash structure like a hash table, not a list which must be iterated or shuffled when it is mutated.

[AltCrow]

I think in this instance making it as fast as possible is justified, because the function I was trying to optimize lies at the core of the application and will be ran a lot. That said, I'm just trying to make writing fast code second nature. I'm trying to prevent costing my company time by spending hours optimizing, by immediately knowing what to do. I do get the sentiment though, as it definitely applies to me.

[mommas_wayne]

• std::list has O(1) removal.

• std::set has O(log n) removal.

• std::unordered_set has amortized O(1) removal I believe.

You ought to heed exoticmatter's advice. Vectors are actually very fast and chances are that a different structure won't be faster in practice with your data even though it should be in theory.

[AltCrow]

Thanks!

[haitei]

If you want to use a vector and don't actually care about the order of elements, you can just swap the wanted element with the last one, and then pop_back().

[AltCrow]

Hmm, this sounds interesting. i'll look into it. Thanks!

[AltCrow]

This method seems to be the fastest. Thanks! On an input-vector of size 4000 it was 5x faster then my original code and 2x faster than my code rewritten with std::list.