erase vs. erase

[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)?

 

[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

 

[Rolf Magnus]

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.

 

[Richard Herring]

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?

 

[red floyd]

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.

 

[Pete Becker]

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.

 

[Richard Herring]

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?

 

[Pete Becker]

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.