1 [article Boost.Circular Buffer
4 [copyright 2003-2013 Jan Gaspar]
6 Distributed under the Boost Software License, Version 1.0.
7 (See accompanying file LICENSE_1_0.txt or copy at
8 [@http://www.boost.org/LICENSE_1_0.txt])
10 [authors [Gaspar, Jan]]
14 [/ Links - by (most common) convention, prefixed with double underscore so not confused with other names.]
15 [def __alert [$./images/alert.png]] [/ Examples of your own images (in doc/html/images/ .]
16 [def __tip [$./images/tip.png]]
17 [/ If you provide a file type like .png, you will probably find that the file is missing in the pdf version.]
18 [/ This is because the default file type specified is .png in html, but .svg for pdf version.]
20 [/ Some links to external sources.]
21 [/ You often want to link more than once, so using a def ensures you always refer to the same location.]
22 [def __boost [@http://www.boost.org/ Boost]] [/Boost.org]
23 [def __boostroot [@boost: Boost root]] [/ Your boost root]
24 [/Note the custom boost root url schema for linking to files within the Boost distribution.]
25 [/Note It can't be used for images, nor for pdf, so not so useful.]
26 [/def __boostlicense [@http://www.boost.org/LICENSE_1_0.txt Boost License]]
27 [/ Or refer to your most recent version of Boost.]
28 [def __boostlicense [@boost:/LICENSE_1_0.txt Boost License]]
29 [def __boostbook [@http://www.boost.org/doc/html/boostbook.html BoostBook]]
30 [def __boostbook_docs [@http://www.boost.org/doc/libs/1_53_0/doc/html/boostbook.html BoostBook documentation]]
31 [def __quickbook [@http://www.boost.org/doc/tools/quickbook/index.html Quickbook]]
32 [def __quickbook_syntax [@http://www.boost.org/doc/libs/1_53_0/doc/html/quickbook/ref.html Quickbook Syntax Compendium]]
33 [def __docbook [@http://www.docbook.org/ DocBook]]
34 [def __doxygen [@http://www.doxygen.org/ Doxygen]]
35 [def __autoindex [@boost:/tools/auto_index/doc/html/index.html AutoIndex]]
36 [def __pdf [@http://www.adobe.com/products/acrobat/adobepdf.html PDF]]
37 [def __textpad [@http://www.textpad.com Textpad]]
38 [def __emacs [@http://www.gnu.org/software/emacs/ GNU emacs]]
39 [def __css [@http://en.wikipedia.org/wiki/Cascading_Style_Sheets Cascading Style Sheet]]
40 [def __intro [link circular_buffer.intro Introduction]] [/Link to a Quickbook section (see below).]
42 [def __docbook_params [@http://docbook.sourceforge.net/release/xsl/current/doc/ Docbook xsl:param format options]]
44 [def __cb [classref boost::circular_buffer circular_buffer]]
45 [def __cbso [classref boost::circular_buffer_space_optimized circular_buffer_space_optimized]]
46 [def __min_capacity [memberref boost::circular_buffer_space_optimized::min_capacity() min_capacity]]
47 [def __capacity_control [memberref boost::circular_buffer_space_optimized::capacity_control () capacity_control ]]
49 [def __debug_support [link circular_buffer.implmentation.debug_support debug support]]
51 [include ../../../tools/auto_index/include/auto_index_helpers.qbk]
52 [/ Must be first included file!]
54 [note A printer-friendly PDF version of this manual is also available.]
56 [section:intro Introduction]
62 The term [@http://en.wikipedia.org/wiki/Circular_buffer circular buffer]
63 (also called a ['ring] or ['cyclic buffer])
64 refers to an area in memory which is used to store incoming data.
65 When the buffer is filled,
66 new data is written starting at the beginning of the buffer and overwriting the old.
68 [classref boost::circular_buffer] is a STL compliant container.
70 It is a kind of sequence similar to [@http://www.sgi.com/tech/stl/List.html std::list]
71 or [@http://www.sgi.com/tech/stl/Deque.html std::deque].
72 It supports random access iterators, constant time insert and erase operations
73 at the beginning or the end of the buffer and interoperability with std algorithms.
75 The __cb is especially designed to provide [*fixed capacity] storage.
76 When its capacity is exhausted, newly inserted elements will cause elements
77 to be overwritten, either at the beginning or end of the buffer
78 (depending on what insert operation is used).
80 The __cb only allocates memory when created,
81 when the capacity is adjusted explicitly,
82 or as necessary to accommodate resizing or assign operations.
84 [$../../libs/circular_buffer/doc/images/circular_buffer.png]
86 There is also a __cbso version available.
88 [$../../libs/circular_buffer/doc/images/space_optimized.png]
90 __cbso is an adaptation of the __cb
91 which [*does not allocate memory all at once when created],
92 instead it allocates memory as needed.
94 The predictive memory allocation is similar to typical `std::vector` implementation.
95 Memory is automatically freed as the size of the container decreases.
97 The memory allocation process of the space-optimized circular buffer.
98 The __min_capacity of the capacity controller represents
99 the minimal guaranteed amount of allocated memory.
100 The allocated memory will never drop under this value.
101 The default value of the `min_capacity` is set to 0.
102 The `min_capacity` can be set using the constructor parameter __capacity_control
103 or the function `set_capacity`.
105 The space-optimized version is, of course, a little slower.
107 [endsect] [/section:intro Introduction]
109 [section:example Circular_buffer example]
111 Here is a simple example to introduce the class __cb.
113 [import ../example/circular_buffer_example.cpp]
115 [circular_buffer_example_1]
117 This example shows contruction, inserting elements, overwriting and popping.
119 [circular_buffer_example_2]
121 [/circular_buffer_example_output - there is no output for this example]
123 You can see the full example code at [@boost:libs/circular_buffer/example/circular_buffer_example.cpp circular_buffer_example.cpp].
125 The full annotated description is in the C++ Reference section.
127 [endsect] [/section:example circular_buffer example]
129 [section:rationale Rationale]
131 The basic motivation behind the __cb was to create a container which would [*work seamlessly with STL].
133 Additionally, the design of the __cb was guided by the following principles:
135 * Maximum ['efficiency] for envisaged applications.
136 * Suitable for ['general purpose use].
137 * The behaviour of the buffer as ['intuitive] as possible.
138 * Suitable for ['specialization] by means of adaptors. (The __cbso is such an example of the adaptor.)
139 * Easy to ['debug]. (See Debug Support for details.)
141 In order to achieve maximum efficiency, the __cb and __cbso store their elements in a
142 [*contiguous region of memory], which then enables:
144 * Use of fixed memory and no implicit or unexpected memory allocation.
145 * Fast constant-time insertion and removal of elements from the front and back.
146 * Fast constant-time random access of elements.
147 * Suitability for real-time and performance critical applications.
149 Possible applications of the circular buffer include:
151 * Storage of the ['most recently received samples], overwriting the oldest as new samples arrive.
152 * As an underlying container for a ['bounded buffer]
153 (see the Bounded Buffer example, code at [@boost:libs/circular_buffer/example/circular_buffer_bound_example.cpp circular_buffer_bound_example.cpp]).
154 * A kind of ['cache] storing a specified number of last inserted elements.
155 * Efficient fixed capacity ['FIFO (First In, First Out)],
156 * Efficient fixed capacity ['LIFO (Last In, First Out)] queue which removes the oldest (inserted as first) elements when full.
158 [endsect] [/section:rationale Rationale]
160 [section:implementation Implementation ]
162 The following paragraphs describe issues that had to be considered during the implementation of the circular_buffer:
166 The thread-safety of the __cb is the same as the thread-safety of containers in most STL implementations.
167 This means the __cb is not fully thread-safe.
168 The thread-safety is guaranteed only in the sense that simultaneous accesses
169 to distinct instances of the __cb are safe,
170 and simultaneous read accesses to a shared __cb are safe.
172 If multiple threads access a single __cb,
173 and at least one of the threads may potentially write,
174 then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.
175 The mutual exclusion between the threads can be achieved by wrapping
176 operations of the underlying __cb with a lock acquisition and release.
177 (See the Bounded Buffer example code at [@boost:libs/circular_buffer/example/circular_buffer_bound_example.cpp circular_buffer_bound_example.cpp])
179 [h3 Overwrite Operation]
181 Overwrite operation occurs when an element is inserted into a full __cb -
182 the old element is being overwritten by the new one.
183 There was a discussion what exactly "overwriting of an element" means during the formal review.
184 It may be either a destruction of the original element and
185 a consequent inplace construction of a new element
186 or it may be an assignment of a new element into an old one.
187 The __cb implements assignment because it is more effective.
189 From the point of business logic of a stored element,
190 the destruction/construction operation and assignment usually mean the same.
191 However, in very rare cases (if in any) they may differ.
192 If there is a requirement for elements to be destructed/constructed instead of being assigned,
193 consider implementing a wrapper of the element which would implement the assign operator,
194 and store the wrappers instead.
195 It is necessary to note that storing such wrappers has a drawback.
196 The destruction/construction will be invoked on every assignment of the wrapper -
197 not only when a wrapper is being overwritten (when the buffer is full)
198 but also when the stored wrappers are being shifted
199 (e.g. as a result of insertion into the middle of container).
201 [h3 Writing to a Full Buffer]
203 There are several options how to cope if a data source produces more data than can fit in the fixed-sized buffer:
205 * Inform the data source to wait until there is room in the buffer (e.g. by throwing an overflow exception).
206 * If the oldest data is the most important, ignore new data from the source until there is room in the buffer again.
207 * If the latest data is the most important, write over the oldest data.
208 * Let the producer to be responsible for checking the size of the buffer prior writing into it.
210 It is apparent that the __cb implements the third option.
211 But it may be less apparent it does not implement any other option -
212 especially the first two.
213 One can get an impression that the __cb should implement first three options
214 and offer a mechanism of choosing among them. This impression is wrong.
216 The __cb was designed and optimized to be circular
217 (which means overwriting the oldest data when full).
218 If such a controlling mechanism had been enabled,
219 it would just complicate the matters
220 and the usage of the __cb would be probably less straightforward.
222 Moreover, the first two options (and the fourth option as well)
223 do not require the buffer to be circular at all.
224 If there is a need for the first or second option, consider implementing an adaptor of e.g. std::vector.
225 In this case the __cb is not suitable for adapting, because,
226 contrary to std::vector, it bears an overhead for its circular behaviour.
228 [h3 Reading/Removing from an Empty Buffer]
230 When reading or removing an element from an empty buffer,
231 the buffer should be able to notify the data consumer
232 (e.g. by throwing underflow exception) that there are no elements stored in it.
233 The __cb does not implement such a behaviour for two reasons:
235 * It would introduce a performance overhead.
236 * No other std container implements it this way.
238 It is considered to be a bug to read or remove an element
239 (e.g. by calling [memberref boost::circular_buffer::front() front()]
240 or [memberref boost::circular_buffer::pop_back() pop_back()])
241 from an empty std container and from an empty __cb as well.
242 The data consumer has to test if the container is not empty before reading/removing from it by testing
243 [memberref boost::circular_buffer::empty empty()].
244 However, when reading from the __cb,
245 there is an option to rely on the [memberref boost::circular_buffer::at() at()]
246 method which throws an exception when the index is out of range.
248 [h3 Iterator Invalidation]
250 An iterator is usually considered to be invalidated if an element,
251 the iterator pointed to, had been removed or overwritten by an another element.
252 This definition is enforced by the Debug Support and is documented for every method.
253 However, some applications utilizing __cb may require less strict definition:
254 an iterator is invalid only if it points to an uninitialized memory.
256 Consider following example:
258 [import ../example/circular_buffer_iter_example.cpp]
260 [circular_buffer_iter_example_1]
262 The iterator does not point to the original element any more
263 (and is considered to be invalid from the "strict" point of view)
264 but it still points to the same valid place in the memory.
265 This "soft" definition of iterator invalidation is supported by the __cb
266 but should be considered as an implementation detail rather than a full-fledged feature.
267 The rules when the iterator is still valid can be inferred from the code in
268 [@boost:libs/circular_buffer/test/soft_iterator_invalidation.cpp soft_iterator_invalidation.cpp].
271 [h3 Move emulation and rvalues]
273 Since Boost 1.54.0 support for move semantics was implemented using
274 the [@boost:libs/move/index.html Boost.Move] library.
275 If rvalue references are available __cb will use them, but if not it uses a close,
276 but imperfect emulation. On such compilers:
278 * Non-copyable objects can be stored in the containers.
279 They can be constructed in place using `emplace`, or if they support
280 Boost.Move, moved into place.
281 * The containers themselves are not movable.
282 * Argument forwarding is not perfect.
284 __cb will use rvalues and move emulations for value types only if move constructor and move assignment operator of the value type do not throw;
285 or if the value type has no copy constructor.
287 Some methods won't use move constructor for the value type at all, if the constructor throws. This is
288 required for data consistency and avoidance of situations, when aftrer an exception __cb
289 contains moved away objects along with the good ones.
291 See documentation for [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_copy_constructible.html `is_copy_constructible`], [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_nothrow_move_assignable.html `is_nothrow_move_assignable`] and [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_nothrow_move_constructible.html `is_nothrow_move_constructible`] type triats.
292 There you'll find information about how to make constructor of class noexcept and how to make a non-copyable
293 class in C++03 and C++98.
295 Performance of __cb will *greatly improve* if value type has noexcept move constructor and noexcept move assignment.
297 [h3 Exceptions of move_if_noexcept(T&)]
299 Reference documentation of the __cb contains notes like "Throws: See Exceptions of `move_if_noexcept(T&)`".
300 That note means the following: `move_if_noexcept(T& value)` does not throws exceptions at all, but it returns
301 `value` as rvalue reference only if class `T` have noexcept move constructor and noexcept move assignment operator;
302 or if it has no copy constructor. Otherwise `move_if_noexcept(T& value)` returns `value` as const reference.
304 This leads us to the following situation:
306 * If `value` has a noexcept move constructor and noexcept move assignment operator, then no exceptions will be thrown at all.
307 * If `value` has a throwing move constructor and some copy constructor, then method may throw exceptions of copy constructor.
308 * If `value` has no copy constructor, then method may throw exceptions of move constructor.
310 `move_if_noexcept(T&)` uses [@boost:libs/move/index.html Boost.Move], [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_copy_constructible.html `is_copy_constructible`], [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_nothrow_move_assignable.html `is_nothrow_move_assignable`] and [@boost:libs/type_traits/doc/html/boost_typetraits/reference/is_nothrow_move_constructible.html `is_nothrow_move_constructible`] type triats.
315 The __cb should not be used for storing pointers to dynamically allocated objects.
316 When a circular buffer becomes full, further insertion will overwrite the stored pointers
317 - resulting in a [*memory leak]. One recommend alternative is the use of smart pointers, for example
318 [@http://www.boost.org/doc/libs/1_53_0/libs/smart_ptr/smart_ptr.htm Boost Smart pointers].
320 [@http://en.wikipedia.org/wiki/Std::auto_ptr std::auto_ptr]
322 [caution Any container of `std::auto_ptr` is considered particularly hazardous.]
324 [tip Never create a circular buffer of `std::auto_ptr`.
325 Refer to Scott Meyers' excellent book Effective STL for a detailed discussion.
326 (Meyers S., Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library.
327 Addison-Wesley, 2001.)
330 While internals of a __cb are circular, [*iterators are not].
331 Iterators of a __cb are only valid for the range `\[begin(), end()\]`,
332 so for example: iterators `(begin() - 1)` and `(end() + 1)` are both invalid.
336 In order to help a programmer to avoid and find common bugs,
337 the __cb can be enabled to provide a kind of debug support.
339 When the debugging functionality is enabled, the __cb maintains a list of valid iterators.
340 As soon as any element gets destroyed all iterators pointing to this element
341 are removed from this list and explicitly invalidated (an invalidation flag is set).
342 The debug support also consists of many assertions (`BOOST_ASSERT` macros)
343 which ensure the __cb and its iterators are used in the correct manner at runtime.
344 In case an invalid iterator is used, the assertion will report an error.
345 The connection of explicit iterator invalidation and assertions
346 makes a very robust debug technique which catches most of the errors.
348 Moreover, the uninitialized memory allocated by __cb is filled with the value `0xcc` in the debug mode.
349 When debugging the code, this can help the programmer to recognize the initialized memory from the uninitialized.
350 For details refer the source code [@boost:boost/circular_buffer/debug.hpp circular_buffer/debug.hpp].
352 [caution Since the debugging code makes __cb and its iterators more interconnected, thread safety guarantees of __cb
353 are different when debug support is enabled. In addition to the container itself, all iterators tracked by the container
354 (including any copies thereof) must be protected from concurrent access. In particular, this includes copying, destroying or
355 obtaining iterators from the container, even if for read-only access.]
357 The debug support is disabled by default. To enable it, one has to define `BOOST_CB_ENABLE_DEBUG` macro with the value of 1
358 while compiling the code using __cb.
360 [h3 Compatibility with Interprocess library]
362 The __cb is compatible with the [@boost:libs/interprocess/index.html Boost.Interprocess]
363 [/ This should be in @boost:libs/interprocess/doc/index.html ]
364 library used for interprocess communication.
365 Considering that the circular_buffer's debug support relies on 'raw' pointers
366 (which is not permited by the Interprocess library)
367 the code has to compiled with debug support disabled (i.e. with `BOOST_CB_ENABLE_DEBUG` macro not defined or defined to 0).
368 Not doing that will cause the compilation to fail.
370 [endsect] [/section:implementation Implementation ]
372 [section:examples More Examples]
374 [h3 Summing all the values in a circular buffer]
376 [import ../example/circular_buffer_sum_example.cpp]
378 [circular_buffer_sum_example_1]
380 [/circular_buffer_example_output - there is no output for this example]
382 The __cb has a capacity of three `int`.
383 Therefore, the size of the buffer will never exceed three.
384 The `std::accumulate` algorithm evaluates the sum of the stored elements.
385 The semantics of the __cb can be inferred from the assertions.
387 You can see the full example code at [@boost:libs/circular_buffer/example/circular_buffer_sum_example.cpp circular_buffer_sum_example.cpp].
389 [h3 Bounded Buffer Example]
391 The bounded buffer is normally used in a producer-consumer mode:
392 producer threads produce items and store them in the container
393 and consumer threads remove these items and process them.
394 The bounded buffer has to guarantee that
396 * producers do not insert items into the container when the container is full,
397 * consumers do not try to remove items when the container is empty,
398 * each produced item is consumed by exactly one consumer.
400 [import ../example/circular_buffer_bound_example.cpp]
402 [circular_buffer_bound_example_1]
404 [/ there is no output for this example]
406 The bounded_buffer relies on [@boost:/doc/html/thread.html Boost.Thread]
407 and [@boost:libs/bind/index.html Boost.Bind] libraries
408 and [@boost:libs/utility/call_traits.htm Boost.call_traits utility].
410 The [memberref boost::circular_buffer::push_front() push_front()]
411 method is called by the producer thread in order to insert a new item into the buffer.
412 The method locks the mutex and waits until there is a space for the new item.
413 (The mutex is unlocked during the waiting stage and has to be regained when the condition is met.)
414 If there is a space in the buffer available,
415 the execution continues and the method inserts the item at the end of the __cb.
416 Then it increments the number of unread items and unlocks the mutex
417 (in case an exception is thrown before the mutex is unlocked,
418 the mutex is unlocked automatically by the destructor of the scoped_lock).
419 At last the method notifies one of the consumer threads
420 waiting for a new item to be inserted into the buffer.
422 The [memberref boost::circular_buffer::pop_back() pop_back()]
423 method is called by the consumer thread in order to read the next item from the buffer.
424 The method locks the mutex and waits until there is an unread item in the buffer.
425 If there is at least one unread item,
426 the method decrements the number of unread items and reads the next item from the __cb.
427 Then it unlocks the mutex and notifies one of the producer threads
428 waiting for the buffer to free a space for the next item.
430 The `bounded buffer::pop_back()`
431 method [*does not remove the item] but the item is left
432 in the circular_buffer which then [*replaces it with a new one]
433 (inserted by a producer) when the circular_buffer is full.
434 This technique is more effective than removing the item
435 explicitly by calling the [memberref boost::circular_buffer::pop_back() circular_buffer::pop_back()]
438 This claim is based on the assumption that an assignment (replacement)
439 of a new item into an old one is more effective than a destruction
440 (removal) of an old item and a consequent inplace construction (insertion) of a new item.
442 For comparison of bounded buffers based on different containers compile and
443 run [@boost:libs/circular_buffer/test/bounded_buffer_comparison.cpp bounded_buffer_comparison.cpp].
444 The test should reveal the bounded buffer based on the __cb is most effective
445 closely followed by the `std::deque` based bounded buffer.
446 (In reality, the result may differ sometimes because the test
447 is always affected by external factors such as immediate CPU load.)
449 [import ../test/bounded_buffer_comparison.cpp]
451 You can see the full test code at [@boost:libs/circular_buffer/test/bounded_buffer_comparison.cpp bounded_buffer_comparison.cpp],
452 and an example of output is [bounded_buffer_comparison_output].
454 [endsect] [/section:examples More examples]
456 [section:headers Header Files]
458 The circular buffer library is defined in the file [@boost:boost/circular_buffer.hpp circular_buffer.hpp].
460 #include <boost/circular_buffer.hpp>
462 (There is also a forward declaration for the __cb
463 in the header file [@boost:boost/circular_buffer_fwd.hpp circular_buffer_fwd.hpp]).
465 The __cb is defined in the file [@boost:boost/circular_buffer/base.hpp base.hpp].
467 The __cbso is defined in the file [@boost:boost/circular_buffer/space_optimized.hpp space_optimized.hpp].
469 [endsect] [/section:headers Header Files]
471 [section:concepts Modelled Concepts]
473 [@http://www.sgi.com/tech/stl/RandomAccessContainer.html Random Access Container],
474 [@http://www.sgi.com/tech/stl/FrontInsertionSequence.html Front Insertion Sequence], and
475 [@http://www.sgi.com/tech/stl/BackInsertionSequence.html Back Insertion sequence]
477 [endsect] [/section:concepts Modelled Concepts]
479 [section:template_params Template Parameters]
481 [table:templ Template parameter requirements
482 [[parameter] [Requirements]]
483 [[T] [The type of the elements stored in the circular_buffer.
484 The T has to be [@boost:libs/utility/Assignable.html Assignable]
485 and [@boost:libs/utility/CopyConstructible.html CopyConstructible].
486 Moreover T has to be [@http://www.sgi.com/tech/stl/DefaultConstructible.html DefaultConstructible]
487 if supplied as a default parameter when invoking some of the circular_buffer's methods,
488 e.g. `insert(iterator pos, const value_type& item = value_type())`.
489 And [@http://www.sgi.com/tech/stl/EqualityComparable.html EqualityComparable]
490 and/or [@boost:libs/utility/LessThanComparable.html LessThanComparable]
491 if the circular_buffer will be compared with another container.]]
492 [[Alloc] [The allocator type used for all internal memory management.
493 The Alloc has to meet the allocator requirements imposed by STL.]]
496 [endsect] [/section:template_params Template Parameters]
498 [section:tickets Trac Tickets]
500 Report and view bugs and features by adding a ticket at [@https://svn.boost.org/trac/boost Boost.Trac].
502 Existing open tickets for this library alone can be viewed
503 [@https://svn.boost.org/trac/boost/query?status=assigned&status=new&status=reopened&component=circular_buffer&col=id&col=summary&col=status&col=owner&col=type&col=milestone&order=priority here].
504 Existing tickets for this library - including closed ones - can be viewed
505 [@https://svn.boost.org/trac/boost/query?status=assigned&status=closed&status=new&status=reopened&component=circular_buffer&col=id&col=summary&col=status&col=owner&col=type&col=milestone&order=priority here].
509 [@https://svn.boost.org/trac/boost/ticket/4100 #4100] Some boost classes have sizeof that depends on NDEBUG.
511 [@https://svn.boost.org/trac/boost/ticket/5362 #5362] circular_buffer does not compile with BOOST_NO_EXCEPTIONS.
513 [@https://svn.boost.org/trac/boost/ticket/6277 #6277] Checked iterators are not threadsafe.
515 [@https://svn.boost.org/trac/boost/ticket/6747 #6747] Circular_Buffer / Bounded_Buffer inside Template class problem.
517 [@https://svn.boost.org/trac/boost/ticket/7025 #7025] circular buffer reports warning: " type qualifiers ignored on function return type" while compile.
519 [@https://svn.boost.org/trac/boost/ticket/7950 #7950] Eliminate W4-warnings under VS2005.
521 [@https://svn.boost.org/trac/boost/ticket/8012 #8012] Inconsistency in `linearize()`.
523 [@https://svn.boost.org/trac/boost/ticket/8438 #8438] `vector` & __cb storage misbehave when using compiler optimizations.
525 Type: Feature Requests
527 [@https://svn.boost.org/trac/boost/ticket/5511 #5511] Documentation needs some improvement.
529 [@https://svn.boost.org/trac/boost/ticket/7888 #7888] circular_buffer should support move semantics.
533 [@https://svn.boost.org/trac/boost/ticket/8032 #8032] Warning fixes in circular_buffer.
535 [endsect] [/section:tickets Trac Tickets]
537 [section:release Release Notes]
541 * C++11 allocator model support implemented by Glen Fernandes using Boost allocator_traits.
545 * Documentation refactored by Paul A. Bristow using Quickbook, Doxygen and Autoindexing.
546 * Rvalue references emulation added by Antony Polukhin using Boost.Move.
550 * Added methods erase_begin(size_type) and erase_end(size_type) with constant complexity for such types of stored elements which do not need an explicit destruction e.g. int or double.
551 * Similarly changed implementation of the clear() method and the destructor so their complexity is now constant for such types of stored elements which do not require an explicit destruction (the complexity for other types remains linear).
555 *Added new methods is_linearized() and rotate(const_iterator).
557 [@https://svn.boost.org/trac/boost/ticket/1987 #1987] Patch to make circular_buffer.hpp #includes absolute.
558 [@https://svn.boost.org/trac/boost/ticket/1852 #1852] Copy constructor does not copy capacity.
562 * Changed behaviour of the circular_buffer(const allocator_type&) constructor.
563 Since this version the constructor does not allocate any memory and both capacity and size are set to zero.
565 [@https://svn.boost.org/trac/boost/ticket/191 #1919] Default constructed circular buffer throws std::bad_alloc.
570 [endsect] [/section:release Release Notes]
572 [section:acknowledgements Acknowledgements]
574 Thomas Witt in 2002 produced a prototype called cyclic buffer.
576 The circular_buffer has a short history. Its first version was a std::deque adaptor.
577 This container was not very effective because of many reallocations when inserting/removing an element.
578 Thomas Wenish did a review of this version and
579 motivated me to create a circular buffer which allocates memory at once when created.
581 The second version adapted `std::vector` but it has been abandoned soon
582 because of limited control over iterator invalidation.
583 The current version is a full-fledged STL compliant container.
585 Pavel Vozenilek did a thorough review of this version and came with many good ideas and improvements.
587 The idea of the space optimized circular buffer has been introduced by Pavel Vozenilek.
589 Also, I would like to thank Howard Hinnant, Nigel Stewart and everyone
590 who participated at the formal review for valuable comments and ideas.
592 Paul A. Bristow refactored the documentation in 2013 to use the full power of Quickbook, Doxygen and Autoindexing.
594 [endsect] [/section:acknowledgements Acknowledgements]
597 [section:version_id Documentation Version Info]
599 Last edit to Quickbook file __FILENAME__ was at __TIME__ on __DATE__.
601 [tip This should appear on the pdf version
602 (but may be redundant on a html version where the last edit date is on the first (home) page).]
604 [warning Home page "Last revised" is GMT, not local time. Last edit date is local time.]
605 [/See also Adobe Reader pdf File Properties for creation date, and PDF producer, version and page count.]
607 [endsect] [/section:version_id Version Info]
609 [xinclude autodoc.xml] [/ Using Doxygen reference documentation.]
610 [/ The position of this in the Quickbook determines the location of the Doxygen references section.]
611 [/ Index(es) should be invoked in the main module, not within a section.]
617 [/ circular_buffer.qbk
618 Copyright 2013 Paul A. Bristow.
619 Copyright 2003-2008 Jan Gaspar.
621 Distributed under the Boost Software License, Version 1.0.
622 (See accompanying file LICENSE_1_0.txt or copy at
623 http://www.boost.org/LICENSE_1_0.txt).