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
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
Hi Gaspar,
Thanks for your answer.
On Thu, 24 Sep 2009 23:01:44 +0200, Jan Gaspar
/// 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
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
/// 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
participants (2)
-
Jan Gaspar -
Luca Cappa