erase vs. erase

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

re: erase vs. erase

al.cpwn@gmail.com wrote:[color=blue]
> 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)?
>[/color]

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

re: erase vs. erase

Mark P wrote:
[color=blue]
> al.cpwn@gmail.com wrote:[color=green]
>> 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)?
>>[/color]
>
> 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.[/color]

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

re: erase vs. erase

In message <e06439$m7a$00$1@news.t-online.com>, Rolf Magnus
<ramagnus@t-online.de> writes[color=blue]
>Mark P wrote:
>[color=green]
>> al.cpwn@gmail.com wrote:[color=darkred]
>>> 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)?
>>>[/color]
>>
>> 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.[/color]
>
>However, they could still have let set's erase return an iterator too, for
>the sake of constistency.[/color]

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

--
Richard Herring

re: erase vs. erase

Richard Herring wrote:[color=blue]
> In message <e06439$m7a$00$1@news.t-online.com>, Rolf Magnus
> <ramagnus@t-online.de> writes[color=green]
>> However, they could still have let set's erase return an iterator too,
>> for
>> the sake of constistency.[/color]
>
> But incrementing set::iterator may be costly, since it involves some
> O(log(N)) tree navigation. Why pay for something you don't need?
>[/color]

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.

re: erase vs. erase

red floyd wrote:[color=blue]
> Richard Herring wrote:
>[color=green]
>> In message <e06439$m7a$00$1@news.t-online.com>, Rolf Magnus
>> <ramagnus@t-online.de> writes
>>[color=darkred]
>>> However, they could still have let set's erase return an iterator
>>> too, for
>>> the sake of constistency.[/color]
>>
>>
>> But incrementing set::iterator may be costly, since it involves some
>> O(log(N)) tree navigation. Why pay for something you don't need?
>>[/color]
>
> 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.[/color]

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.

--

Pete Becker
Roundhouse Consulting, Ltd.

re: erase vs. erase

In message <-NqdnQyN28QZerfZnZ2dnUVZ_sSdnZ2d@giganews.com>, Pete Becker
<petebecker@acm.org> writes[color=blue]
>red floyd wrote:[color=green]
>> Richard Herring wrote:
>>[color=darkred]
>>> In message <e06439$m7a$00$1@news.t-online.com>, Rolf Magnus
>>><ramagnus@t-online.de> writes
>>>
>>>> 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?
>>>[/color]
>> 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.[/color]
>
>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.[/color]

Then I'm wrong about the cost. So why _doesn't_ set::erase return the
next iterator?[color=blue]
>[/color]

--
Richard Herring

re: erase vs. erase

Richard Herring wrote:[color=blue]
>
> So why _doesn't_ set::erase return the
> next iterator?
>[/color]

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.

--

Pete Becker
Roundhouse Consulting, Ltd.