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-10-26 17:42:25

Hi Luca,

sorry for the late answer. I implemented the 'constant' erase methods - erase_begin() and erase_end(). You can find them in trunk branch. The documentation is updated as well.

Have a look and let me know if you like them.

Regards,

Jan



----- Original Message ----
From: Luca Cappa <luca.cappa_at_[hidden]>
To: boost-users_at_[hidden]
Sent: Friday, 25 September, 2009 10:12:59
Subject: Re: [Boost-users] circular_buffer::erase in constant time

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
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users