Re: [Boost-users] circular_buffer::erase in constant time

Subject: Re: [Boost-users] circular_buffer::erase in constant time
From: Jan Gaspar (jano_gaspar_at_[hidden])
Date: 2009-09-24 17:01:44

Hi Luca,

it doesn't make sense to me to be honest.

> /// Erase the first pCount element from the buffer
> void begin_erase (size_t pCount)
> {
>  BOOST_ASSERT(pCount <= size ());
>  circular_buffer<Type>::add (m_first, pCount);
>  m_size -= pCount;;
> }
What you are suggesting here is linear in pCount. It is actually equivalent of erase(begin(), begin() + pCount). Not sure how you want to make the erase method constant.

Regards,

Jan



Original Message ----
From: Luca Cappa <luca.cappa_at_[hidden]>
To: boost-users_at_[hidden]
Sent: Thursday, 24 September, 2009 14:39:18
Subject: [Boost-users] circular_buffer::erase in constant time

Hello,

is it possible to remove the first bunch of elements of a circular_buffer with constant complexity time?
Unfortunately using any (r)erase function the complexity is linear.

To give an idea, it could be implemented like this:

/// Erase the first pCount element from the buffer
void begin_erase (size_t pCount)
{
  BOOST_ASSERT(pCount <= size ());
  circular_buffer<Type>::add (m_first, pCount);
  m_size -= pCount;;
}

but this is not taking into account deletion of the deleted items (could they be deleted when they are overwritten? Or the stored type does not need to be destroyed at all), and many other details which are known to me.

I am asking this 'cause I would like to make my circular_buffer class to be STL compliant container, but before doing it myself, I would like to evaluate if I could derive (or use aggregation) directly from circular_buffer and save me a lot of work.

Thanks,
Luca
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users