Boost logo

Boost :

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2003-08-24 15:32:23

Hello Jano,

From: "Jan Gaspar" <jga_at_[hidden]>
Subject: circular_buffer ver. 3.3
> Another beast was born. You can find it at

This circular_buffer works on MSVC 6.5 and Intel C++ 7 and also compiles on
BC++B 6.4.

Few notes to latest source:

1. circular_buffer_adaptor.html: the link in

   "The circular_buffer_space_optimized is defined in
    the file boost/circular_buffer.hpp."

   points to wrong source file.

2. circular_buffer_adaptor.hpp should include
   circular_buffer_base.hpp, someone might
   use only this header.

3. It would be helpful (for MSVC) to put this into
   headers circular_buffer_fwd.hpp and

#if _MSC_VER >= 1020
#pragma once

4. Borland C++ Builder 6.4 requires to specify template parameters
   for cb_iterator:

a. in operator-():
   cb_iterator operator - (difference_type n) const { return
cb_iterator<Buff, Traits>(*this) -= n; }

b. in operator+():
    cb_iterator operator + (difference_type n) const { return
cb_iterator<Buff, Traits>(*this) += n; }

5. Borland C++ Builder 6.4 doesn't allow to bring
   operator[] via using.

This is workaround in circular_buffer_adaptor.hpp:

#include <boost/detail/workaround.hpp>


    reference operator [] (difference_type n) { circular_buffer<T,
Alloc>::operator[](n); }
    const reference operator [] (difference_type n) const {
circular_buffer<T, Alloc>::operator[](n); }
    using circular_buffer<T, Alloc>::operator[];

6. circular_buffer_adapter.hpp: member m_final_capacity
   may be named m_max_capacity.

7. Maybe there should be low treshold to capacity as well as high.
   Actual capacity may vary between these. This would avoid
   unnecessary reallocations when there are only few items.

min_capacity <= size <= current_capacity <= max_capacity

min_capacity is allowed to be 0.

Grow algorithm can be:
a. if new_size >= current_capacity then current_capacity =
std::min(max_capacity, current_size * 2)
b. avoid reallocating for only few items
  if new_size + new_size / 2 >= max_capacity then current_capacity =

The two check_low_capacity() functions can be merged into one
void check_low_capacity(size_type n = 1);

Also the "<< 1" and ">> 1" can be in this case safely replaced by * 2 and /
(it is unsigned).

Shrink algorithm can be:
a. allow hysteresis when shrinking
   if new_size < current_capacity / 3 then shrink_to(std::max(min_capacity,
current_capacity / 2))
b. if new_size < min_capacity then shrink_to(min_capacity)
c. if new_size == 0 && min_capacity == 0 then shrink_to(0)

The constructors and set_capacity() would need one more paramerer or
capacity() could return pair<>. clear() would need change.

8. circular_buffer_space_optimized<> constructor with circular_buffer<>
   parameter can be provided, similarly operators <, >, ==, !=,
   and possibly swap() (swaping only items).

   I don't know how much needed in practice this would be though.

9. circular_buffer_base.hpp and circular_buffer_adaptor.hpp:
   instead of check


is enough to use


(it is defined for MSVC).

10. cb_iterator::operator->() should also have asserts inside.

11. cb_iterator::operator+=() and operator-=(): the asserts should
    be moved at the beginning of these functions.

12. cb_iterator::operator--() should have assert:
    BOOST_ASSERT(m_it != m_buff.m_first); // is not begin()

13. cb_iterator::operator+=() should have assert:
    BOOST_ASSERT(distance(m_it - m_buff.begin()) + n <= size());

    Similarly in operator-=() and operator[].

   cb_iterator functions may also check if their m_it pointer is
   in valid range <begin(), end()).

14. Btw, isn't cb_iterator::operator[]() added by mistake?
    I have never seen such an operation for iterator.

15. circular_buffer::front(), back(), pop_front() and
    pop_back() can have asserts for empty buffer.

    insert()/rinsert()/erase() can check position iterator
    validity too.

16. RAII vs try blocks:

> > 1. IMO the macro based exception handling isn't needed, it is better
> > to use RAII, like:
> > ...
> >
> > can be replaced by:
> >
> > void set_capacity(size_type new_capacity) {
> > if (new_capacity == capacity()) return;
> > pointer buff = allocate(new_capacity);
> >
> > struct deleter_t {
> > pointer data;
> > size_type capacity;
> > deleter_t(pointer p, size_type s) : data(p), capacity(s) {}
> > ~deleter_t() { deallocate(data, capacity); }
> > };
> > deleter_t guard(buff, new_capacity);
> >
> > size_type new_size = new_capacity < size() ? new_capacity : size();
> > std::uninitialized_copy(end() - new_size, end(), buff);
> > destroy();
> > m_size = new_size;
> > m_buff = m_first = buff;
> > m_end = m_buff + new_capacity;
> > m_last = full() ? m_buff : m_buff + size();
> > = 0;
> > }
> >
> I think this is not a good idea because
> - it won't work - the ~deleter_t() destructor does not have access to
> the deallocate() method
> - the original macros are more explanatory (it is easier to understand)
> - every STL implementation is using such macros
It may be possible to pass member function pointer or make deleter friend.

(Another possibility would be to use Alexandrescu's ScopeGuard.)

There's one good reason to avoid catch(...): on Win32 it interferes with
system exceptions handling. If someone uses __try/__catch/__finally,
these won't be called after throw; and also it won't be possible
to fix and continue system exception.

If I remember right, Digital Unix compiler had similar option for signals.

16. circular_buffer.html: the sentence
    "The rules for iterator invalidation" should be:
    "The rules for iterator (and result of data()) invalidation".

17. Maybe function data() should return 0 if buffer is empty instead
    of pointer pointing to garbage. It would at least make app behavior

18. documentation: "allocates memory continuously" should be replaced
    by "allocates memory as needed (growing and shrinking)".

19. circular_buffer_adaptor.html: is the first rule for invalidation of
    iterators valid? Shouldn't there be "MAY invalidate all iterators
    when buffer grows/shrinks, the rules from circular_buffer<> apply as

    Second rule here is the same as for circular_buffer<>.

20. Documentation: at the beginning of circular_buffer.html can be picture
    to give quick clue to people who do not read documentation throroughly

    Something like attached PNG. The circular_buffer_space_optimized can
    something too.

21. Documentation: <hr> between sections would make reading easier.

22. The code can use static_asserts to check if InputIterator::value_type
    is convertible to T (using type traits, many places).

    This would make errors easier to spot.

23. Something to catch errors better: could function destroy() set all
    internal pointers to 0? (at least in debug mode). This would lead
    to predictable behavior with orphaned iterators.

    Similarly, circular_buffer_space_optimized can (before deallocating,
    in debug mode) fill old buffer with 0xCC or so.

24. Question: do you plan to add Mojo to circular_buffer?



Boost list run by bdawes at, gregod at, cpdaniel at, john at