erase vs. erase

A

al.cpwn

Is there a reason why erase for vector returns an iterator but erase
for set doesn't? Is this something we should keep in mind while
designing our own containers (like binary tree for example)?
 
M

Mark P

Is there a reason why erase for vector returns an iterator but erase
for set doesn't? Is this something we should keep in mind while
designing our own containers (like binary tree for example)?

My guess is that this is because in the vector case, the call to erase
will invalidate all iterators at or beyond the location of the erasure.
Thus it's useful to return a new iterator to the location after the
erasure.

For a set, only iterators pointing to the location of the erasure are
invalidated, so this is easier to deal with manually. For example,
mySet.erase(myIter++); will result in myIter pointing to the location
after the erasure.

Mark
 
R

Rolf Magnus

Mark said:
My guess is that this is because in the vector case, the call to erase
will invalidate all iterators at or beyond the location of the erasure.
Thus it's useful to return a new iterator to the location after the
erasure.

For a set, only iterators pointing to the location of the erasure are
invalidated, so this is easier to deal with manually. For example,
mySet.erase(myIter++); will result in myIter pointing to the location
after the erasure.

However, they could still have let set's erase return an iterator too, for
the sake of constistency.
 
R

Richard Herring

Rolf Magnus said:
However, they could still have let set's erase return an iterator too, for
the sake of constistency.

But incrementing set::iterator may be costly, since it involves some
O(log(N)) tree navigation. Why pay for something you don't need?
 
R

red floyd

Richard said:
But incrementing set::iterator may be costly, since it involves some
O(log(N)) tree navigation. Why pay for something you don't need?

I don't know... That's an implementation issue. I could see an
implementation that trades space in the set node for constant time
incrementing. E.g. set searches are O(log n), and iteration is O(1) for
each ++ operatation (each node knows its predecessor and successor --
implemented as a linked list). Inserts and deletes would be a tad more
expensive (though still O(logN)).

I'm not saying that it *should* be done, I'm simply saying that I could
see *how* it could be done.
 
P

Pete Becker

red said:
I don't know... That's an implementation issue. I could see an
implementation that trades space in the set node for constant time
incrementing. E.g. set searches are O(log n), and iteration is O(1) for
each ++ operatation (each node knows its predecessor and successor --
implemented as a linked list). Inserts and deletes would be a tad more
expensive (though still O(logN)).

I'm not saying that it *should* be done, I'm simply saying that I could
see *how* it could be done.

erase has to look at adjacent nodes in order to stitch the tree back
together, and possibly rebalance it. Returning the next iterator is
usually trivial, because you already have it.
 
R

Richard Herring

Pete Becker said:
erase has to look at adjacent nodes in order to stitch the tree back
together, and possibly rebalance it. Returning the next iterator is
usually trivial, because you already have it.

Then I'm wrong about the cost. So why _doesn't_ set::erase return the
next iterator?
 
P

Pete Becker

Richard said:
So why _doesn't_ set::erase return the
next iterator?

It will. <g>

As to the reason, best guess is that it's not strictly needed in user
code, because if someone needs it, they can get it beforehand. So
frugality kept it out. In this case, I think the frugality, while
well-intentioned, was misplaced. Dinkumware's implementation has always
provided it.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top