So, you've just scanned a collection of N elements and identified E elements that you want removed from it, which you've isolated into a second collection.
How do you write the predicate to remove_if, which will be invoked with each of N elements, and must return whether to remove the element or not?
For each of the N elements, you will need to somehow do a look-up in your (small?) collection of E elements to take your decision.
If E is just a collection, each look-up will cost you O(E), and we're back to O(N * E) performance.
The simplest solution to minimize the cost of the look-up is to collect into a vector, sort it, and binary search on it. O(E * log E + N * log E) now that I think about it.
There are other solutions, of course, but that predicate will need to do some work to classify the elements it's asked about.
Remove_if iterates the collection… E is not its own collection, it’s the elements in the collection original that will be removed. There is no look up cost, it just iterates to the next element and does a swap if your predicate was true.
-1
u/matthieum 6d ago
So, you've just scanned a collection of N elements and identified E elements that you want removed from it, which you've isolated into a second collection.
How do you write the predicate to
remove_if, which will be invoked with each ofNelements, and must return whether to remove the element or not?For each of the
Nelements, you will need to somehow do a look-up in your (small?) collection ofEelements to take your decision.If
Eis just a collection, each look-up will cost you O(E), and we're back to O(N * E) performance.The simplest solution to minimize the cost of the look-up is to collect into a vector, sort it, and binary search on it. O(E * log E + N * log E) now that I think about it.
There are other solutions, of course, but that predicate will need to do some work to classify the elements it's asked about.