Deleting the last element of an std::set
Giuliano Bertoletti
Hello,
another question: I wish to erase the last element of a set (last
according to some custom less operator I have defined for that set).
Is the following code correct ?
What worries me most is the --hi.end() construct.
std::set< sometype > hi;
if(!hi.empty()) {
hi.erase( --hi.end() );
}
At first I've tried with:
hi.erase( hi.rbegin() );
but there's no overloaded erase function which takes a reverse_iterator
as argument, so I guess the above is the only function which runs in
c*log(n) time.
Cheers,
Giulio.
Bo Persson
> Hello,
>
> another question: I wish to erase the last element of a set (last
> according to some custom less operator I have defined for that set).
>
> Is the following code correct ?
> What worries me most is the --hi.end() construct.
>
> std::set< sometype > hi;
>
> if(!hi.empty()) {
> hi.erase( --hi.end() );
> }
>
The potential problem is that if the iterator is actually a raw
pointer (could be for std::vector, but hardly for a std::set), you
cannot decrement the temporary returned by end(). If the iterator is a
class with an operator--() member function, is will be ok.
So, in practice, if the code compiles it works for the container you
are using.
Bo Persson
Jerry Coffin
@libero.it says...
[ ... ]
> At first I've tried with:
>
> hi.erase( hi.rbegin() );
>
> but there's no overloaded erase function which takes a reverse_iterator
> as argument, [ ... ]
You can convert from a reverse iterator to the base type with the
'base()' member function. Note that rbegin() is basically equivalent
to end() -- it points one past the end of the set, so you'd need:
hi.erase((++hi.rbegin()).base());
--
Later,
Jerry.
Giuliano Bertoletti
> Giuliano Bertoletti wrote:
>> Hello,
>>
>> another question: I wish to erase the last element of a set (last
>> according to some custom less operator I have defined for that set).
>>
>> Is the following code correct ?
>> What worries me most is the --hi.end() construct.
>>
>> std::set< sometype > hi;
>>
>> if(!hi.empty()) {
>> hi.erase( --hi.end() );
>> }
>>
>
> The potential problem is that if the iterator is actually a raw
> pointer (could be for std::vector, but hardly for a std::set), you
> cannot decrement the temporary returned by end().
> If the iterator is a
> class with an operator--() member function, is will be ok.
>
I'm not following you.
I'm not the designer of the container class but, why would a vector
iterator, which is also a random iterator, not support the -- operator ?
Cheers,
Giulio.
joseph cook
> In article <4a477c7c$0$1107$4fafb...@reader3.news.tin.it>, gbe32241
Oh no, that's not right!
rbegin() points to the last element, not end(). It wouldn't be very
useful to iterate from rbegin() to rend() otherwise, would it?
Joe Cook
James Kanze
> Giuliano Bertoletti wrote:
> > another question: I wish to erase the last element of a set
> > (last according to some custom less operator I have defined
> > for that set).
> > Is the following code correct ?
> > What worries me most is the --hi.end() construct.
> > std::set< sometype > hi;
> > if(!hi.empty()) {
> > hi.erase( --hi.end() );
> > }
> The potential problem is that if the iterator is actually a
> raw pointer (could be for std::vector, but hardly for a
> std::set), you cannot decrement the temporary returned by
> end(). If the iterator is a class with an operator--() member
> function, is will be ok.
And if the iterator is a class with a non-member operator--()
function, it won't be OK.
> So, in practice, if the code compiles it works for the
> container you are using.
IF the code compilers. (Formally, of course, it's undefined
behavior, but in practice, either it will compile and work, or
it will fail to compile.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
> > [ ... ]
> > > hi.erase( hi.rbegin() );
> > hi.erase((++hi.rbegin()).base());
Formally, rbegin() points to the first element---of the inverted
sequence. But it does this by containing an iterator to one
past the last element---this solution is necessary in order for
rend() to be possible.
Jerry Coffin
662bff...@f33g2000vbm.googlegroups.com>, joe...@gmail.com says...
[ ... ]
> Oh no, that's not right!
> rbegin() points to the last element, not end(). It wouldn't be very
> useful to iterate from rbegin() to rend() otherwise, would it?
Yes and no -- when you iterate from rbegin to rend, you do get the
elements of the set (or whatever) in reverse order, surely enough.
When you convert rbegin() to its base(), however, what you get is
basically the same as end() would return -- one past the end of the
set.
--
Later,
Jerry.
Bart van Ingen Schenau
It is not so much what operations the iterator type supports, but rather
what operations the language allows you to do on the return-value of a
function.
Container::end() returns an iterator by value (so as a temporary
object), and the only way you can modify such an object is by calling a
member-function on it.
If the iterator type has operator--() declared as a member, then the
expression '--hi.end()' is interpreted as 'hi.end().operaor--()', which
is a valid construct.
If operator--() is not a member function, then it can not be applied to
the result of Container::end(), so the expression '--hi.end()' must
result in a diagnostic.
If you want to get the before-last iterator without these considerations
with operator--, you can use this helper function:
template <typename It>
It prev(It iter)
{
return --iter;
}
/* use as: prev(hi.end()) */
>
> Cheers,
> Giulio.
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/