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

Subject: Re: [Boost-users] circular_buffer::erase in constant time
From: Luca Cappa (luca.cappa_at_[hidden])
Date: 2009-09-25 04:12:59

Hi Gaspar,

Thanks for your answer.

On Thu, 24 Sep 2009 23:01:44 +0200, Jan Gaspar <jano_gaspar_at_[hidden]>  
wrote:
>> /// 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.

No, it is not linear, it is constant. Basically there are two additions  
which modify the value of m_first and m_size,
and not loop whatsoever. Of course, one line of code should be

m_first = circular_buffer<Type>::add (m_first, pCount);

to really modify the m_first value.

Basically, if you have a circular buffer of 'int's, with capacity 4:

1) the empy buffer looks like this

| first/last _ | _ | _ | _ |

where 'first' is the pointer (or call it index) to the first busy bucket,  
and 'last' is the 'after the last occupied' bucket. '_' are free buckets.

2) after inserting the items (1,2,3) the buffer looks like:

| first 1 | 2 | 3 | last |

3) after inserting the item '4' (now the buffer is full):

| first/last 1 | 2 | 3 | 4 |

4) now if you erase the first three elements:

| last _ | _ | _ | first 4 |

This is what happen with my own circular buffer class. With  
boost::circular_buffer instead the result of erasing the first three  
elements is:

| first 4 | last | _ | _ |

> It is actually equivalent of erase(begin(), begin() + pCount).

As shown above, it is not the same: in fact erase(begin(), begin  
()+pCount) does this:

iterator erase(iterator first, iterator last)
{
[...]
         pointer p = first.m_it;
/// Replace the elements in the range [first, last) with the elements in  
the range [last, last - first + last)
         while (last.m_it != 0)
             replace((first++).m_it, *last++);
/// Destroy the elements in the range [last, last - first + last) (i.e.  
destroy the just moved elements).
         do {
             decrement(m_last);
             destroy_item(m_last);
             --m_size;
         } while(m_last != first.m_it);
[...]
}

In my case, the elements are primitive type (int/float/double), or some  
class which does not need any destruction, so that loop is completely  
useless. The erasing could be simply done moving forward (and wrapping if  
needed) the m_first pointer.

I hope this is more clearly explained now.

Greetings,
Luca