CODEWITHSUNDEEP
c++stl
user3243499
user3243499

Reputation: 3151

How to effectively delete beginning and ending elements from a set in C++?

If I have set as follows:

set<int> dummyset = {2,3,4,5,6,7,8};

auto itr = dummyset.find(5);

And if I want to delete from 2 to 4, I would type dummyset.erase(dummyset.begin(), itr);

But this takes linear time.

Assuming I intend to always want to delete two chunks from either end can I just move the beginning pointer or ending pointer (constant time) instead of deleting each element (linear time)?

Example:

begin     end
|           |
V           V
1  2  3  4  5

// Delete {1,2} and {5} by moving pointers

1  2  3  4  5
      ^  ^
      |  |
  begin  end

Upvotes: 1

Views: 260

Answers (3)

Red.Wave
Red.Wave

Reputation: 4225

std algorithms are normally defined to operate on pairs of begin/end iterators. So you probably want to implement a view using a pair of iterators [in/de]cremented on demand.

Upvotes: 0

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385174

You can't, and you may not need to.

C++'s algorithms take iterator pairs. So, instead of dummyset.begin(), and dummyset.end(), pass them your adjusted iterators.

However if you are using set member functions (like member .find()), there's no way around it — you will need to actually erase. There's no way to tell those functions to temporarily act on a sub-range instead of the whole container (which I believe is what you were asking for).

Odds are this isn't as bad as you think. The implementation knows what it's doing, and should only rebalance its internal tree as much as is actually necessary, given a range of elements to remove.

Upvotes: 7

Drew Dormann
Drew Dormann

Reputation: 63775

how can I just skip actually erase and just reset the beginning pointer or ending pointer to itr which can be done in constant time?

For portable code, You would need to create a different container that exposes this functionality.

std::set intentionally restricts access to its underlying pointers, as manipulating them outside of the established interface would easily introduce object leaks, memory leaks, and undefined behavior that users of std::set are protected from.

Upvotes: 0

Related Questions