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@sequoia.it> To: boost-users@lists.boost.org 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@yahoo.com> 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users