delete elements less than a given element in C++ set

Question

I have a set in C++. I want to delete all the elements from the set which are less than a specified value. E.g.

std::set setElem;
setElem.insert(1);
setElem.insert(45);
setElem.insert(47);
//setElem contains {1,45,47}
//delete all elements less than 46 such that the set now becomes: {47}

I know we can iterate over the set and delete the elements by verifying whether they are less than 46 or not. Is there some other more efficient way in C++ to do the same.

gcc version which I am using is: gcc (Ubuntu/Linaro 4.6.4-6ubuntu2) 4.6.4

Whenever you need an algorithm like this, it's worth looking at the [standard library's](http://en.cppreference.com/w/cpp/algorithm). — chris, Apr 03 '15 at 12:52
Downvoted because you did not even bother to _glance_ at a standard library reference's algorithms list. — Lightness Races in Orbit, Apr 03 '15 at 12:52
[http://www.cplusplus.com/reference/algorithm/remove_if/](http://www.cplusplus.com/reference/algorithm/remove_if/) — jhnnslschnr, Apr 03 '15 at 12:53
@LightningRacisinObrit That's true, problem is most people still don't seem to know the difference between the core language and the standard library. Let aside the place to look up the standard libraries from; many still go to the erroneous cplusplus.com :( — legends2k, Apr 03 '15 at 12:55
@legends2k: Even a visit to cplusplus.com (which is much better nowadays, as long as you avoid the forums) would have resolved this problem in short order. — Lightness Races in Orbit, Apr 03 '15 at 12:55
@Dieter Lucking why using std::set::lower_bound is more efficient? — MrGreen, Apr 03 '15 at 12:59
@MrGreen: Cos binary search, bro. And the subsequent erasure will be a lot cheaper than N erasures. — Lightness Races in Orbit, Apr 03 '15 at 13:02
@LightningRacisinObrit: You need to pass over all the elements you need erase and delete them one by one. So if you iterate from set.begin() and keep deleting the element at set.begin() until the element in set.begin() becomes greater or equal to the desired value, the running time will be O(number of deleted elements). So there is no need to add the log(n) factor comming from lower_bound. — MrGreen, Apr 03 '15 at 13:11
@MrGreen: What you've just said to me is, effectively, "You can do it in O(n) so there is no need to do it in O(log(n))." Which is ludicrous, unless you have some prior knowledge of the data and can guarantee that the chopping point is always only one or two elements in. Certainly in the general case your suggestion is silly! — Lightness Races in Orbit, Apr 03 '15 at 13:15
@LightningRacisinObrit: If you notice in the solution below lower_bound() takes O(log n) and erase() takes O(number of deleted elements) so the total running time is O(log n + number of deleted elements). The solution I described is O(number of deleted elements). — MrGreen, Apr 03 '15 at 13:17
@MrGreen: Right, but that's not what's actually going to happen, is it? In your version, you perform one O(n) sweep, then _n_ O(1) erasures. If you use a binary search to first find your deletion point, then that's only a O(log n) scan before an O(n) set of erasures. In real time that's obviously going to be more efficient. Although we should measure it before continuing, probably; I didn't realise that erasure is only O(n) in deleted elements (that's awful -.-). — Lightness Races in Orbit, Apr 03 '15 at 13:19
@legends2k: What does the erase-remove idiom have to do with it here? We are talking about `std::set`!!! Nothing gets swapped to the end. — Lightness Races in Orbit, Apr 03 '15 at 13:20
@LightningRacisinObrit: No I sweep and erase at the same time till the value in set.begin() becomes larger or equal to the desired value. i.e. all the undesirable elements are deleted. — MrGreen, Apr 03 '15 at 13:21
@MrGreen: Yes, I know what your code _does_; we are talking about _how_ it does it and what the ramifications of that are. Just because you "sweep and erase at the same time" doesn't mean you are not performing a sweep and an erase, or that you no longer need to consider the performance implications of both operations independently. You might as well sweep _then_ erase; it's the same thing. Furthermore I suspect erasing 5 elements in one go rather than erasing 1 element 5 times will be faster in real time, though I haven't anything to back that up and it's just a suspicion at the moment. — Lightness Races in Orbit, Apr 03 '15 at 13:22
Either O(n) comparison + O(n) erase or O(log(n)) comparison + O(n) erase. Both is O(n) — , Apr 03 '15 at 13:27
@DieterLücking: Right. And, going further, that only describes the _growth_ of the algorithm. It doesn't actually tell you which is faster in real time. One could be, in fake notation, `O(50000n)` while the other `O(2n)`. — Lightness Races in Orbit, Apr 03 '15 at 13:35

Ali Akber · Accepted Answer · 2015-04-03T15:29:15.597

You can use lower_bound() and erase()

#include <set>
#include <iostream>
using namespace std;

int main()
{
    set<int>setElem;

    setElem.insert(1);
    setElem.insert(45);
    setElem.insert(46);
    setElem.insert(47);
    setElem.insert(50);
    setElem.insert(51);

    set<int>:: iterator it;
    it=setElem.lower_bound(46);

    //Erasing
    setElem.erase(setElem.begin(),it);

    //Printing
    for(set<int>::iterator it1=setElem.begin(); it1!=setElem.end(); ++it1)
      cout<< *it1 << "\n";
}

delete elements less than a given element in C++ set

1 Answers1