Queue  1.0.0
A C++17 Library of various `queue` containers
circular_queue.h
Go to the documentation of this file.
1 //--------------------------------------------------------------------------------------------------
2 //
3 // QUEUE
4 //
5 //--------------------------------------------------------------------------------------------------
6 //
7 // The MIT License (MIT)
8 //
9 // Permission is hereby granted, free of charge, to any person obtaining a copy of this software
10 // and associated documentation files (the "Software"), to deal in the Software without
11 // restriction, including without limitation the rights to use, copy, modify, merge, publish,
12 // distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the
13 // Software is furnished to do so, subject to the following conditions:
14 //
15 // The above copyright notice and this permission notice shall be included in all copies or
16 // substantial portions of the Software.
17 //
18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
19 // BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
21 // DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
22 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 //
24 //--------------------------------------------------------------------------------------------------
25 //
26 // Copyright (c) 2015 Nic Holthaus
27 //
28 //--------------------------------------------------------------------------------------------------
29 //
30 // ATTRIBUTION:
31 //
32 //
33 //--------------------------------------------------------------------------------------------------
34 //
35 /// @file circular_queue.h
36 /// @brief An STL-style fixed-size circular queue
37 //
38 //--------------------------------------------------------------------------------------------------
39 
40 #pragma once
41 #ifndef circular_queue_h__
42 #define circular_queue_h__
43 
44 //------------------------
45 // INCLUDES
46 //------------------------
47 #include <algorithm>
48 #include <cassert>
49 #include <cstddef>
50 #include <cstring>
51 #include <initializer_list>
52 #include <iterator>
53 #include <stdexcept>
54 #include <cstdint>
55 #include <type_traits>
56 
57 // ----------------------------------------------------------------------------
58 // CLASS circular_queue
59 // ----------------------------------------------------------------------------
60 /// @brief Fixed capacity, STL-style, templated circular buffer.
61 /// @details see http://en.wikipedia.org/wiki/Circular_buffer for details of
62 /// how circular buffers work.\n\n
63 ///
64 /// This implementation shares many features of a double-ended queue.
65 /// This structure allows for the individual elements to be accessed directly through
66 /// random access iterators, with storage handled automatically by over-writing elements
67 /// from the opposite end of the container as it grows. As long as elements are added
68 /// consistently to EITHER the front or the back, once full, the container will expand
69 /// by over-writing the oldest element. If elements are added to both sides of the
70 /// buffer, the behavior is effectively user defined.\n\n
71 ///
72 /// Therefore, the circular_queue provides a functionality similar to vectors,
73 /// but with efficient insertion and deletion of elements also at the beginning of the
74 /// sequence, and not only at its end. Also, like vectors (and unlike dequeues), all
75 /// elements are stored in contiguous memory locations, and offset access IS allowed.\n\n
76 ///
77 /// Both vectors and the circular_queue provide a very similar interface and
78 /// can be used for similar purposes, but internally both work in quite different ways :
79 /// While vectors use a single array that needs to be occasionally reallocated for growth,
80 /// the elements of a circular_queue are over-written once the buffer reaches
81 /// its maximum capacity, ensuring elements are inserted and accessed in constant time and
82 /// with a uniform sequential interface (through iterators), as opposed to the vector's
83 /// amortized constant time. This allows them to grow more efficiently under certain
84 /// circumstances, especially with very long sequences, where reallocation's become more
85 /// expensive, and real-time applications where stale data is not as useful as current data.\n\n
86 ///
87 /// For operations that involve frequent insertion or removals of elements at positions
88 /// other than the beginning or the end, circular_queues perform worse and
89 /// have less consistent iterators and references than lists and forward lists.\n\n
90 ///
91 /// This class can be moved very quickly (constant time). It may be slow to copy.\n
92 ///
93 /// <b>Container properties</b>\n
94 /// <i>Sequence</i>\n
95 /// Elements in sequence containers are ordered in a strict linear sequence. Individual
96 /// elements are accessed by their position in this sequence.\n
97 /// <i>Fixed-capacity array</i>\n
98 /// Allows direct access to any element in the sequence and provides fast addition /
99 /// removal of elements at the beginning or the end of the sequence.\n
100 /// <i>Allocator - aware</i>\n
101 /// The container uses an allocator object to dynamically handle its storage needs.\n
102 // ----------------------------------------------------------------------------
103 
104 template<class T, class Alloc = std::allocator<T>>
105 class circular_queue
106 {
107 public:
108  //////////////////////////////////////////////////////////////////////////
109  // FORWARD DECLARATIONS
110  //////////////////////////////////////////////////////////////////////////
111  class iterator;
112  class const_iterator;
113 
114  //////////////////////////////////////////////////////////////////////////
115  // TYPEDEFS
116  //////////////////////////////////////////////////////////////////////////
117 
118  using allocator_type = Alloc; ///< Type of object used to dynamically allocate memory.
119  using difference_type = ptrdiff_t; ///< A signed integral type, identical to:iterator_traits<iterator>::difference_type
120  using size_type = size_t; ///< An unsigned integral type that can represent any non-negative value of difference_type.
121  using value_type = T; ///< The template parameter (T), representing the values stored in the container.
122  using pointer = T*; ///< For the default allocator: value_type*.
123  using const_pointer = const T*; ///< Type for pointer to constant T object.
124  using reference = T&; ///< Type for data references.
125  using const_reference = const T&; ///< Type for reference to constant T object.
126  using reverse_iterator = std::reverse_iterator<iterator>; ///< Type for reverse iterators.
127  using const_reverse_iterator = std::reverse_iterator<const_iterator>; ///< Type for constant reverse iterators.
128 
129  /// pointer with parity
130  struct queue_pointer
131  {
132  queue_pointer(pointer p, bool par)
133  : ptr(p)
134  , parity(par){};
135  pointer ptr;
136  bool parity;
137  };
138 
139  /// constant pointer with parity
140  struct const_queue_pointer
141  {
142  const_queue_pointer(pointer p, bool par)
143  : ptr(p)
144  , parity(par){};
145  const_pointer ptr;
146  bool parity;
147  };
148 
149  // ----------------------------------------------------------------------------
150  // CLASS const_iterator
151  // ----------------------------------------------------------------------------
152  /// @brief constant iterator for the circular_queue class.
153  /// @details
154  // ----------------------------------------------------------------------------
155  class const_iterator
156  {
157  public:
158  //////////////////////////////////////////////////////////////////////////
159  // TYPEDEFS
160  //////////////////////////////////////////////////////////////////////////
161 
162  using iterator_category = std::random_access_iterator_tag;
163  using value_type = const T;
164  using difference_type = ptrdiff_t;
165  using pointer = const T*;
166  using reference = const T&;
167 
168  //////////////////////////////////////////////////////////////////////////
169  // FRIENDS
170  //////////////////////////////////////////////////////////////////////////
171 
172  friend class circular_queue;
173 
174  //////////////////////////////////////////////////////////////////////////
175  // MEMBERS
176  //////////////////////////////////////////////////////////////////////////
177 
178  /**
179  * @brief Constructor
180  * @details Creates an initialized iterator.
181  * <b> Complexity:</b> Constant.\n
182  * <b> Iterator Validity:</b> N/A.\n
183  * <b> Data Races:</b> N/A.\n
184  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
185  * exceptions.\n
186  * @param[in] buffer pointer to the underlying container.
187  * @param[in] start pointer to the iterators starting offset
188  */
189  const_iterator(const circular_queue* buffer, pointer start, bool parity) noexcept
190  : m_buffer(buffer)
191  , m_pointer(start, parity){
192 
193  };
194 
195  const_iterator(const circular_queue* buffer, queue_pointer pointer) noexcept
196  : m_buffer(buffer)
197  , m_pointer(pointer){
198 
199  };
200 
201  const_iterator()
202  : m_buffer(nullptr)
203  , m_pointer(nullptr, false){
204 
205  };
206 
207  const_iterator(const const_iterator& other) = default;
208 
209  const_iterator& operator=(const const_iterator& other) = default;
210 
211  const_iterator(const_iterator&& other) noexcept
212  : m_buffer(std::move(other.m_buffer))
213  , m_pointer(std::move(other.m_pointer))
214  {
215  }
216 
217  const_iterator& operator=(const_iterator&& other) noexcept
218  {
219  m_buffer = std::move(other.m_buffer);
220  m_pointer = std::move(other.m_pointer);
221  return *this;
222  }
223 
224  /**
225  * @brief destructor.
226  * <b> Complexity:</b> Constant.\n
227  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
228  * exceptions.\n
229  */
230  inline ~const_iterator() noexcept = default;
231 
232  /**
233  * @brief Dereference operator
234  * @details Returns a reference to the element pointed to by the iterator.
235  * <b> Complexity:</b> Constant.\n
236  * <b> Iterator Validity:</b> No changes.\n
237  * <b> Data Races:</b> The object is accessed.\n
238  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
239  * @returns A reference to the element pointed by the iterator.
240  */
241  inline reference operator*() const
242  {
243  assert(m_buffer);
244  return *(this->m_pointer.ptr);
245  }
246 
247  /**
248  * @brief Dereference operator
249  * @details Returns a pointer to the element pointed to by the iterator.
250  * <b> Complexity:</b> Constant.\n
251  * <b> Iterator Validity:</b> Unchanged.\n
252  * <b> Data Races:</b> The object is accessed.\n
253  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
254  * @returns A pointer to the element pointed by the iterator.
255  */
256  inline pointer operator&() const
257  {
258  assert(m_buffer);
259  return this->m_pointer.ptr;
260  }
261 
262  /**
263  * @brief Dereference operator
264  * @details Returns a pointer to the element pointed to by the iterator.
265  * <b> Complexity:</b> Constant.\n
266  * <b> Iterator Validity:</b> Unchanged.\n
267  * <b> Data Races:</b> The object is accessed.\n
268  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
269  * @returns A pointer to the element pointed by the iterator.
270  */
271  inline pointer operator->() const
272  {
273  assert(m_buffer);
274  return this->m_pointer.ptr;
275  }
276 
277  /**
278  * @brief Dereference iterator with offset
279  * @details Accesses the element located n positions away from the element currently pointed
280  * to by the iterator. If such an element does not exist, it causes <i>undefined
281  * behavior</i>.
282  * <b> Complexity:</b> Constant.\n
283  * <b> Iterator Validity:</b> Unchanged.\n
284  * <b> Data Races:</b> The object is accessed. Depending on the return type, the
285  * value returned may be used to access or modify elements.\n
286  * <b> Exception Safety:</b> Undefined behavior if <i>n</i> is out of range.\n
287  * @param[in] n Number of elements to offset. Member type difference_type is an alias of the
288  * base container's own difference type.
289  * @returns The element n positions away from the element currently pointed by the iterator.
290  */
291  inline reference operator[](difference_type n) const
292  {
293  assert(m_buffer);
294  const_iterator tmp = *this + n;
295  return *tmp;
296  }
297 
298  /**
299  * @brief equality operator
300  * @details Two iterators are equal if they point to the same object and have the same
301  * parity value (i.e. one isn't wrapped around the buffer from the other).\n
302  * <b> Complexity:</b> Constant.\n
303  * <b> Iterator Validity:</b> No changes.\n
304  * <b> Data Races:</b> The container is accessed.\n
305  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
306  * exceptions.\n
307  * @param[in] rhs right-hand-side of the equation.
308  * @returns true if both iterators point to the same object.
309  */
310  inline bool operator==(const const_iterator& rhs) const noexcept
311  {
312  // member-wise ==
313  assert(this->m_buffer == rhs.m_buffer);
314  return ((this->m_pointer.ptr == rhs.m_pointer.ptr) && (this->m_pointer.parity == rhs.m_pointer.parity));
315  }
316 
317  /**
318  * @brief inequality operator
319  * <b> Complexity:</b> Constant.\n
320  * <b> Iterator Validity:</b> No changes.\n
321  * <b> Data Races:</b> The container is accessed.\n
322  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
323  * exceptions.\n
324  * @param[in] rhs right-hand-side of the equation.
325  * @returns true if both iterators point to different objects.
326  */
327  inline bool operator!=(const const_iterator& rhs) const
328  {
329  return !(operator==(rhs));
330  }
331 
332  /**
333  * @brief Increment iterator position (prefix)
334  * @details Advances the iterator by 1 position.
335  * <b> Complexity:</b> Constant.\n
336  * <b> Iterator Validity:</b> Valid IFF the iterator is incrementable.\n
337  * <b> Data Races:</b> The object is modified.\n
338  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
339  * exceptions.\n
340  * @returns A reference to the incremented iterator.
341  */
342  inline const_iterator& operator++() noexcept
343  {
344  return operator+=(1);
345  }
346 
347  /**
348  * @brief Increment iterator position (postfix)
349  * @details Advances the iterator by 1 position.
350  * <b> Complexity:</b> Constant.\n
351  * <b> Iterator Validity:</b> Valid IFF the iterator is incrementable.\n
352  * <b> Data Races:</b> The object is modified.\n
353  * <b> Exception Safety:</b> Strong guarantee: if the function throws an
354  * exception, there are no side effects.\n
355  * @returns A copy of the iterator before it was incremented.
356  */
357  inline const_iterator operator++(int)
358  {
359  const_iterator tmp(*this);
360  operator++();
361  return tmp;
362  }
363 
364  /**
365  * @brief Advance iterator.
366  * @details Advances the iterator by n element positions.\n
367  * <b> Complexity:</b> Constant.\n
368  * <b> Iterator Validity:</b> Results in undefined behavior if the element at
369  * position <i>n</i> does not exist.\n
370  * <b> Data Races:</b> The object is modified.\n
371  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
372  * exceptions.\n
373  * @param[] n
374  * @returns circular_queueIterator&
375  */
376  inline const_iterator& operator+=(difference_type n) noexcept
377  {
378  assert(m_buffer && m_pointer.ptr);
379  m_pointer = m_buffer->increment(m_pointer, n);
380 
381  return *this;
382  }
383 
384  /**
385  * @brief Addition operator.
386  * @details Returns an iterator pointing to the element located n positions away from the
387  * element the iterator currently points to.\n
388  * <b> Complexity:</b> Constant.\n
389  * <b> Iterator Validity:</b> Undefined behavior if the element <i>n</i> positions
390  * away is out of bounds.\n
391  * <b> Data Races:</b> The object is accessed but NOT modified.\n
392  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
393  * exception, there are no side effects.\n
394  * @param[in] n number of elements to offset.
395  * @returns An iterator pointing to the element n positions away.
396  */
397  inline const_iterator operator+(difference_type n) const noexcept
398  {
399  assert(m_buffer && m_pointer.ptr);
400  queue_pointer p(m_pointer);
401 
402  p = m_buffer->increment(p, n);
403 
404  return const_iterator(m_buffer, p);
405  }
406 
407  /**
408  * @brief Decrease iterator position (prefix)
409  * @details Decreases the iterator by one position.\n
410  * <b> Complexity:</b> Constant.\n
411  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
412  * decrementable, otherwise no changes.\n
413  * <b> Data Races:</b> The object is modified.\n
414  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
415  * exceptions.\n
416  * @returns A reference to an iterator pointing to the post-decrement iterator.
417  */
418  inline const_iterator& operator--() noexcept
419  {
420  return operator-=(1);
421  }
422 
423  /**
424  * @brief Decrease iterator position (postfix)
425  * @details Decreases the iterator by one position.\n
426  * <b> Complexity:</b> Constant.\n
427  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
428  * decrementable, otherwise no changes.\n
429  * <b> Data Races:</b> The object is accessed but NOT modified.\n
430  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
431  * exception, there are no side effects.\n
432  * @returns A iterator pointing to the pre-decremented element.
433  */
434  inline const_iterator operator--(int)
435  {
436  const_iterator tmp(*this);
437  operator--();
438  return tmp;
439  }
440 
441  /**
442  * @brief Retrocede iterator
443  * @details Decreases the iterator by n element positions.
444  * <b> Complexity:</b> Constant.\n
445  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
446  * decrementable, otherwise no changes.\n
447  * <b> Data Races:</b> The object is modified.\n
448  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
449  * exceptions.\n
450  * @param[in] n Number of elements to offset. Member type difference_type is an alias of the
451  * base container's own difference type.\n
452  * @returns the iterator itself, decremented by n positions.
453  */
454  inline const_iterator& operator-=(difference_type n) noexcept
455  {
456  assert(m_buffer && m_pointer.ptr);
457  m_pointer = m_buffer->decrement(m_pointer, n);
458 
459  return *this;
460  }
461 
462  /**
463  * @brief subtraction operator
464  * @details Returns an iterator whose position is n elements before the current position
465  * <b> Complexity:</b> Constant.\n
466  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
467  * decrementable, otherwise no changes.\n
468  * <b> Data Races:</b> the object is accessed but NOT modified.\n
469  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
470  * exception, there are no side effects.\n
471  * @param[in] nNumber of elements to offset. Member type difference_type is an alias of the
472  * base container's own difference type.\n
473  * @returns An iterator decremented n positions from the current iterator position.
474  */
475  inline const_iterator operator-(difference_type n) const
476  {
477  assert(m_buffer && m_pointer.ptr);
478  queue_pointer p(m_pointer);
479 
480  p = m_buffer->decrement(p, n);
481 
482  return const_iterator(m_buffer, p);
483  }
484 
485  /**
486  * @brief subtraction operator
487  * @details Returns the distance between two iterators.
488  * <b> Complexity:</b> Constant.\n
489  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
490  * decrementable, otherwise no changes.\n
491  * <b> Data Races:</b> the object is accessed but NOT modified.\n
492  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
493  * exception, there are no side effects.\n
494  * @param[in] other iterator to determine distance from.\n
495  * @returns number of elements between the two iterators.
496  */
497  inline difference_type operator-(const const_iterator& other) const
498  {
499  assert(m_buffer);
500  assert(m_buffer == other.m_buffer);
501  assert(m_pointer.ptr && other.m_pointer.ptr);
502 
503  if (m_pointer.parity == other.m_pointer.parity)
504  {
505  return (m_pointer.ptr - other.m_pointer.ptr);
506  }
507  else
508  {
509  return (m_buffer->m_capacity - (other.m_pointer.ptr - m_pointer.ptr));
510  }
511  }
512 
513  /**
514  * @brief less-than operator
515  * @details Performs the appropriate comparison.
516  * <b> Complexity:</b> Constant.\n
517  * <b> Iterator Validity:</b> No changes.\n
518  * <b> Data Races:</b> The object is accessed.\n
519  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
520  * exceptions.\n
521  * @param[in] rhs iterator for the right-hand side of the comparison.
522  * @returns true if this iterator is less than <i>rhs</i>.
523  */
524  inline bool operator<(const const_iterator& rhs) const noexcept
525  {
526  // check that the iterators are compatible
527  assert(this->m_buffer == rhs.m_buffer);
528 
529  // it's possible the buffer is wrapped around, such that:
530  // T H
531  // begin|--2--|---------------------|---------1---|end
532  // this can be tested for by checking the parity bit. If the parity's match, they are not
533  // wrapped. If the parity's don't match, they are wrapped.
534  if (this->m_pointer.parity == rhs.m_pointer.parity)
535  {
536  return (this->m_pointer.ptr < rhs.m_pointer.ptr);
537  }
538  else
539  {
540  return this->m_pointer.ptr > rhs.m_pointer.ptr;
541  }
542  }
543 
544  /**
545  * @brief less-than-or-equal operator
546  * @details Performs the appropriate comparison.
547  * <b> Complexity:</b> Constant.\n
548  * <b> Iterator Validity:</b> No changes.\n
549  * <b> Data Races:</b> The object is accessed.\n
550  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
551  * exceptions.\n
552  * @param[in] rhs iterator for the right-hand side of the comparison.
553  * @returns true if this iterator is less than or equal to <i>rhs</i>.
554  */
555  inline bool operator<=(const const_iterator& rhs) const
556  {
557  // define in terms of less than
558  return (this->m_pointer.ptr == rhs.m_pointer.ptr || operator<(rhs));
559  }
560 
561  /**
562  * @brief greater-than operator
563  * @details Performs the appropriate comparison.
564  * <b> Complexity:</b> Constant.\n
565  * <b> Iterator Validity:</b> No changes.\n
566  * <b> Data Races:</b> The object is accessed.\n
567  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
568  * exceptions.\n
569  * @param[in] rhs iterator for the right-hand side of the comparison.
570  * @returns true if this iterator is greater than <i>rhs</i>.
571  */
572  inline bool operator>(const const_iterator& rhs) const
573  {
574  // define in terms of less than
575  return !(operator<=(rhs));
576  }
577 
578  /**
579  * @brief greater-than-or-equal operator
580  * @details Performs the appropriate comparison.
581  * <b> Complexity:</b> Constant.\n
582  * <b> Iterator Validity:</b> No changes.\n
583  * <b> Data Races:</b> The object is accessed.\n
584  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
585  * exceptions.\n
586  * @param[in] rhs iterator for the right-hand side of the comparison.
587  * @returns true if this iterator is greater than or equal to <i>rhs</i>.
588  */
589  inline bool operator>=(const const_iterator& rhs) const
590  {
591  // define in terms of less than
592  return !(operator<(rhs));
593  }
594 
595  protected:
596  const circular_queue* m_buffer = nullptr; ///< pointer to the buffer object that this iterates on.
597  queue_pointer m_pointer; ///< Iterator position.
598  };
599 
600  // ----------------------------------------------------------------------------
601  // CLASS iterator
602  // ----------------------------------------------------------------------------
603  /// @brief iterator for the circular_queue class.
604  /// @details
605  // ----------------------------------------------------------------------------
606  class iterator
607  {
608  public:
609  //////////////////////////////////////////////////////////////////////////
610  // TYPEDEFS
611  //////////////////////////////////////////////////////////////////////////
612 
613  using iterator_category = std::random_access_iterator_tag;
614  using value_type = T;
615  using difference_type = ptrdiff_t;
616  using pointer = T*;
617  using reference = T&;
618 
619  //////////////////////////////////////////////////////////////////////////
620  // FRIENDS
621  //////////////////////////////////////////////////////////////////////////
622 
623  friend class circular_queue;
624 
625  //////////////////////////////////////////////////////////////////////////
626  // MEMBERS
627  //////////////////////////////////////////////////////////////////////////
628 
629  /**
630  * @brief Constructor
631  * @details Creates an initialized iterator.
632  * <b> Complexity:</b> Constant.\n
633  * <b> Iterator Validity:</b> N/A.\n
634  * <b> Data Races:</b> N/A.\n
635  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
636  * exceptions.\n
637  * @param[in] buffer pointer to the underlying container.
638  * @param[in] start pointer to the iterator's starting offset
639  */
640  iterator(const circular_queue* const buffer, pointer start, bool parity) noexcept
641  : m_buffer(buffer)
642  , m_pointer(start, parity){
643 
644  };
645 
646  iterator(const circular_queue* const buffer, queue_pointer pointer) noexcept
647  : m_buffer(buffer)
648  , m_pointer(pointer){
649 
650  };
651 
652  iterator()
653  : m_buffer(nullptr)
654  , m_pointer(nullptr, false){
655 
656  };
657 
658  iterator(const iterator& other) = default;
659  iterator& operator=(const iterator& other) = default;
660 
661  iterator(iterator&& other) noexcept
662  : m_buffer(std::move(other.m_buffer))
663  , m_pointer(std::move(other.m_pointer))
664  {
665  }
666 
667  iterator& operator=(iterator&& other) noexcept
668  {
669  m_buffer = std::move(other.m_buffer);
670  m_pointer = std::move(other.m_pointer);
671  return *this;
672  }
673 
674  /**
675  * @brief destructor.
676  * <b> Complexity:</b> Constant.\n
677  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
678  * exceptions.\n
679  */
680  inline ~iterator() noexcept = default;
681 
682  /**
683  * @brief Dereference operator
684  * @details Returns a reference to the element pointed to by the iterator.
685  * <b> Complexity:</b> Constant.\n
686  * <b> Iterator Validity:</b> No changes.\n
687  * <b> Data Races:</b> The object is accessed.\n
688  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
689  * @returns A reference to the element pointed by the iterator.
690  */
691  inline reference operator*() const
692  {
693  assert(m_buffer);
694  return *(this->m_pointer.ptr);
695  }
696 
697  /**
698  * @brief Dereference operator
699  * @details Returns a pointer to the element pointed to by the iterator.
700  * <b> Complexity:</b> Constant.\n
701  * <b> Iterator Validity:</b> Unchanged.\n
702  * <b> Data Races:</b> The object is accessed.\n
703  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
704  * @returns A pointer to the element pointed by the iterator.
705  */
706  inline pointer operator&() const
707  {
708  assert(m_buffer);
709  return this->m_pointer.ptr;
710  }
711 
712  /**
713  * @brief Dereference operator
714  * @details Returns a pointer to the element pointed to by the iterator.
715  * <b> Complexity:</b> Constant.\n
716  * <b> Iterator Validity:</b> Unchanged.\n
717  * <b> Data Races:</b> The object is accessed.\n
718  * <b> Exception Safety:</b> Undefined if the iterator is not valid.\n
719  * @returns A pointer to the element pointed by the iterator.
720  */
721  inline pointer operator->() const
722  {
723  assert(m_buffer);
724  return this->m_pointer.ptr;
725  }
726 
727  /**
728  * @brief Dereference iterator with offset
729  * @details Accesses the element located n positions away from the element currently pointed
730  * to by the iterator. If such an element does not exist, it causes <i>undefined
731  * behavior</i>.
732  * <b> Complexity:</b> Constant.\n
733  * <b> Iterator Validity:</b> Unchanged.\n
734  * <b> Data Races:</b> The object is accessed. Depending on the return type, the
735  * value returned may be used to access or modify elements.\n
736  * <b> Exception Safety:</b> Undefined behavior if <i>n</i> is out of range.\n
737  * @param[in] n Number of elements to offset. Member type difference_type is an alias of the
738  * base container's own difference type.
739  * @returns The element n positions away from the element currently pointed by the iterator.
740  */
741  inline reference operator[](difference_type n) const
742  {
743  assert(m_buffer);
744  iterator tmp = *this + n;
745  return *tmp;
746  }
747 
748  /**
749  * @brief equality operator
750  * @details Two iterators are equal if they point to the same object and have the same
751  * parity value (i.e. one isn't wrapped around the buffer from the other).\n
752  * <b> Complexity:</b> Constant.\n
753  * <b> Iterator Validity:</b> No changes.\n
754  * <b> Data Races:</b> The container is accessed.\n
755  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
756  * exceptions.\n
757  * @param[in] rhs right-hand-side of the equation.
758  * @returns true if both iterators point to the same object.
759  */
760  inline bool operator==(const iterator& rhs) const noexcept
761  {
762  // memberwise ==
763  assert(this->m_buffer == rhs.m_buffer);
764  return ((this->m_pointer.ptr == rhs.m_pointer.ptr) && (this->m_pointer.parity == rhs.m_pointer.parity));
765  }
766 
767  /**
768  * @brief inequality operator
769  * <b> Complexity:</b> Constant.\n
770  * <b> Iterator Validity:</b> No changes.\n
771  * <b> Data Races:</b> The container is accessed.\n
772  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
773  * exceptions.\n
774  * @param[in] rhs right-hand-side of the equation.
775  * @returns true if both iterators point to different objects.
776  */
777  inline bool operator!=(const iterator& rhs) const
778  {
779  // always define != in terms of == (unless you want awesomely undebuggable errors!)
780  return !(operator==(rhs));
781  }
782 
783  /**
784  * @brief Increment iterator position (prefix)
785  * @details Advances the iterator by 1 position.
786  * <b> Complexity:</b> Constant.\n
787  * <b> Iterator Validity:</b> Valid IFF the iterator is incrementable.\n
788  * <b> Data Races:</b> The object is modified.\n
789  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
790  * exceptions.\n
791  * @returns A reference to the incremented iterator.
792  */
793  inline iterator& operator++() noexcept
794  {
795  return operator+=(1);
796  }
797 
798  /**
799  * @brief Increment iterator position (postfix)
800  * @details Advances the iterator by 1 position.
801  * <b> Complexity:</b> Constant.\n
802  * <b> Iterator Validity:</b> Valid IFF the iterator is incrementable.\n
803  * <b> Data Races:</b> The object is modified.\n
804  * <b> Exception Safety:</b> Strong guarantee: if the function throws an
805  * exception, there are no side effects.\n
806  * @returns A copy of the iterator before it was incremented.
807  */
808  inline iterator operator++(int)
809  {
810  auto tmp(*this);
811  operator++();
812  return tmp;
813  }
814 
815  /**
816  * @brief Advance iterator.
817  * @details Advances the iterator by n element positions.\n
818  * <b> Complexity:</b> Constant.\n
819  * <b> Iterator Validity:</b> Results in undefined behavior if the element at
820  * position <i>n</i> does not exist.\n
821  * <b> Data Races:</b> The object is modified.\n
822  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
823  * exceptions.\n
824  * @param[] n
825  * @returns circular_queueIterator&
826  */
827  inline iterator& operator+=(difference_type n) noexcept
828  {
829  assert(m_buffer && m_pointer.ptr);
830  m_pointer = m_buffer->increment(m_pointer, n);
831 
832  return *this;
833  }
834 
835  /**
836  * @brief Addition operator.
837  * @details Returns an iterator pointing to the element located n positions away from the
838  * element the iterator currently points to.\n
839  * <b> Complexity:</b> Constant.\n
840  * <b> Iterator Validity:</b> Undefined behavior if the element <i>n</i> positions
841  * away is out of bounds.\n
842  * <b> Data Races:</b> The object is accessed but NOT modified.\n
843  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
844  * exception, there are no side effects.\n
845  * @param[in] n number of elements to offset.
846  * @returns An iterator pointing to the element n positions away.
847  */
848  inline iterator operator+(difference_type n) const noexcept
849  {
850  assert(m_buffer && m_pointer.ptr);
851 
852  queue_pointer p = m_buffer->increment(m_pointer, n);
853 
854  return iterator(m_buffer, p);
855  }
856 
857  /**
858  * @brief Decrease iterator position (prefix)
859  * @details Decreases the iterator by one position.\n
860  * <b> Complexity:</b> Constant.\n
861  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
862  * decrementable, otherwise no changes.\n
863  * <b> Data Races:</b> The object is modified.\n
864  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
865  * exceptions.\n
866  * @returns A reference to an iterator pointing to the post-decrement iterator.
867  */
868  inline iterator& operator--() noexcept
869  {
870  return operator-=(1);
871  }
872 
873  /**
874  * @brief Decrease iterator position (postfix)
875  * @details Decreases the iterator by one position.\n
876  * <b> Complexity:</b> Constant.\n
877  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
878  * decrementable, otherwise no changes.\n
879  * <b> Data Races:</b> The object is accessed but NOT modified.\n
880  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
881  * exception, there are no side effects.\n
882  * @returns A iterator pointing to the pre-decremented element.
883  */
884  inline iterator operator--(int)
885  {
886  auto tmp(*this);
887  operator--();
888  return tmp;
889  }
890 
891  /**
892  * @brief Retrocede iterator
893  * @details Decreases the iterator by n element positions.
894  * <b> Complexity:</b> Constant.\n
895  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
896  * decrementable, otherwise no changes.\n
897  * <b> Data Races:</b> The object is modified.\n
898  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
899  * exceptions.\n
900  * @param[in] n Number of elements to offset. Member type difference_type is an alias of the
901  * base container's own difference type.\n
902  * @returns the iterator itself, decremented by n positions.
903  */
904  inline iterator& operator-=(difference_type n) noexcept
905  {
906  assert(m_buffer && m_pointer.ptr);
907  m_pointer = m_buffer->decrement(m_pointer, n);
908 
909  return *this;
910  }
911 
912  /**
913  * @brief subtraction operator
914  * @details Returns an iterator whose position is n elements before the current position
915  * <b> Complexity:</b> Constant.\n
916  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
917  * decrementable, otherwise no changes.\n
918  * <b> Data Races:</b> the object is accessed but NOT modified.\n
919  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
920  * exception, there are no side effects.\n
921  * @param[in] nNumber of elements to offset. Member type difference_type is an alias of the
922  * base container's own difference type.\n
923  * @returns An iterator decremented n positions from the current iterator position.
924  */
925  inline iterator operator-(difference_type n) const
926  {
927  assert(m_buffer && m_pointer.ptr);
928  queue_pointer p = m_pointer;
929 
930  p = m_buffer->decrement(p, n);
931 
932  return iterator(m_buffer, p);
933  }
934 
935  /**
936  * @brief subtraction operator
937  * @details Returns the distance between two iterators.
938  * <b> Complexity:</b> Constant.\n
939  * <b> Iterator Validity:</b> Undefined behavior if the iterator is not
940  * decrementable, otherwise no changes.\n
941  * <b> Data Races:</b> the object is accessed but NOT modified.\n
942  * <b> Exception Safety:</b> Strong guarantee: if the constructor throws an
943  * exception, there are no side effects.\n
944  * @param[in] other iterator to determine distance from.\n
945  * @returns number of elements between the two iterators.
946  */
947  inline difference_type operator-(const iterator& other) const
948  {
949  assert(m_buffer);
950  assert(m_buffer == other.m_buffer);
951  assert(m_pointer.ptr && other.m_pointer.ptr);
952 
953  if (m_pointer.parity == other.m_pointer.parity)
954  {
955  return (m_pointer.ptr - other.m_pointer.ptr);
956  }
957  else
958  {
959  return (m_buffer->m_capacity - (other.m_pointer.ptr - m_pointer.ptr));
960  }
961  }
962 
963  /**
964  * @brief less-than operator
965  * @details Performs the appropriate comparison.
966  * <b> Complexity:</b> Constant.\n
967  * <b> Iterator Validity:</b> No changes.\n
968  * <b> Data Races:</b> The object is accessed.\n
969  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
970  * exceptions.\n
971  * @param[in] rhs iterator for the right-hand side of the comparison.
972  * @returns true if this iterator is less than <i>rhs</i>.
973  */
974  inline bool operator<(const iterator& rhs) const noexcept
975  {
976  // check that the iterators are compatible
977  assert(this->m_buffer == rhs.m_buffer);
978 
979  // it's possible the buffer is wrapped around, such that:
980  // T H
981  // begin|--2--|---------------------|---------1---|end
982  // this can be tested for by checking the parity bit. If the parity's match, they are not
983  // wrapped. If the parity's don't match, they are wrapped.
984  if (this->m_pointer.parity == rhs.m_pointer.parity)
985  {
986  return (this->m_pointer.ptr < rhs.m_pointer.ptr);
987  }
988  else
989  {
990  return this->m_pointer.ptr > rhs.m_pointer.ptr;
991  }
992  }
993 
994  /**
995  * @brief less-than-or-equal operator
996  * @details Performs the appropriate comparison.
997  * <b> Complexity:</b> Constant.\n
998  * <b> Iterator Validity:</b> No changes.\n
999  * <b> Data Races:</b> The object is accessed.\n
1000  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1001  * exceptions.\n
1002  * @param[in] rhs iterator for the right-hand side of the comparison.
1003  * @returns true if this iterator is less than or equal to <i>rhs</i>.
1004  */
1005  inline bool operator<=(const iterator& rhs) const
1006  {
1007  // define in terms of less than
1008  return (this->m_pointer.ptr == rhs.m_pointer.ptr || operator<(rhs));
1009  }
1010 
1011  /**
1012  * @brief greater-than operator
1013  * @details Performs the appropriate comparison.
1014  * <b> Complexity:</b> Constant.\n
1015  * <b> Iterator Validity:</b> No changes.\n
1016  * <b> Data Races:</b> The object is accessed.\n
1017  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1018  * exceptions.\n
1019  * @param[in] rhs iterator for the right-hand side of the comparison.
1020  * @returns true if this iterator is greater than <i>rhs</i>.
1021  */
1022  inline bool operator>(const iterator& rhs) const
1023  {
1024  // define in terms of less than
1025  return !(operator<=(rhs));
1026  }
1027 
1028  /**
1029  * @brief greater-than-or-equal operator
1030  * @details Performs the appropriate comparison.
1031  * <b> Complexity:</b> Constant.\n
1032  * <b> Iterator Validity:</b> No changes.\n
1033  * <b> Data Races:</b> The object is accessed.\n
1034  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1035  * exceptions.\n
1036  * @param[in] rhs iterator for the right-hand side of the comparison.
1037  * @returns true if this iterator is greater than or equal to <i>rhs</i>.
1038  */
1039  inline bool operator>=(const iterator& rhs) const
1040  {
1041  // define in terms of less than
1042  return !(operator<(rhs));
1043  }
1044 
1045  /// Allow implicit conversion from iterator to const_iterator as required by STL
1046  operator const_iterator() const
1047  {
1048  return const_iterator(m_buffer, m_pointer);
1049  }
1050 
1051  protected:
1052  const circular_queue* m_buffer = nullptr; //< pointer to the buffer object that this iterates on.
1053  queue_pointer m_pointer; ///< Iterator position.
1054  };
1055 
1056 public:
1057  //////////////////////////////////////////////////////////////////////////
1058  // #CONSTRUCTORS
1059  //////////////////////////////////////////////////////////////////////////
1060 
1061  /**
1062  * @{
1063  * @name Constructors
1064  * @brief Methods to construct, destruct, and assign the container.
1065  */
1066 
1067  /**
1068  * @brief Constructor
1069  * @details
1070  * <b> Complexity:</b> O(N) with buffer capacity (memory allocation).\n
1071  * <b> Iterator Validity:</b> N/A.\n
1072  * <b> Data Races:</b> N/A.\n
1073  * <b> Exception Safety:</b> Throws std::bad_alloc if allocation fails. In this
1074  * case, no object is created.\n
1075  * @param[in] capacity number of elements that can be stored in the queue.
1076  * @param[in] alloc Allocator object. The container keeps and uses an internal copy of this
1077  * allocator.
1078  */
1079  explicit circular_queue(size_type capacity, const allocator_type& alloc = allocator_type())
1080  : m_alloc(alloc)
1081  , m_capacity(capacity)
1082  , m_head(nullptr, false)
1083  , m_tail(nullptr, false)
1084  {
1085  if (m_capacity == 0)
1086  {
1087  throw std::bad_alloc();
1088  }
1089 
1090  // allocate raw memory near this class. No point in default constructing anything, especially since this buffer
1091  // may be HUGE.
1092  try
1093  {
1094  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1095  }
1096  catch (...)
1097  {
1098  // Since constructor failed, no object will be created. Memory wasn't allocated, so no
1099  // cleanup is required.
1100  // transparent exceptions
1101  throw std::bad_alloc();
1102  }
1103 
1104  m_head.ptr = m_tail.ptr = m_data;
1105  }
1106 
1107  /**
1108  * @brief fill constructor
1109  * @details Creates an array of size <i>capacity</i> and fills it with copies of <i>val</i>.\n
1110  * <b> Complexity:</b> O(N) with size.\n
1111  * <b> Iterator Validity:</b> N/A.\n
1112  * <b> Data Races:</b> N/A.\n
1113  * <b> Exception Safety:</b> Throws std::bad_alloc if allocation fails. In this
1114  * case, no object is created.\n
1115  * @param[in] val this value will be copied into all the container elements.
1116  * @param[in] capacity size of the container.
1117  * @param[in] alloc Allocator object. The container keeps and uses an internal copy of this
1118  * allocator.
1119  */
1120  explicit circular_queue(size_type capacity, const value_type& val, const allocator_type& alloc = allocator_type())
1121  : m_alloc(alloc)
1122  , m_capacity(capacity)
1123  , m_head(nullptr, false)
1124  , m_tail(nullptr, false)
1125  {
1126  if (m_capacity == 0)
1127  {
1128  throw std::bad_alloc();
1129  }
1130 
1131  // allocate raw memory near this class.
1132  try
1133  {
1134  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1135  }
1136  catch (...)
1137  {
1138  // Since constructor failed, no object will be created. Memory wasn't allocated, so no
1139  // cleanup is required.
1140  // transparent exceptions
1141  throw std::bad_alloc();
1142  }
1143 
1144  m_head.ptr = m_tail.ptr = m_data;
1145 
1146  // fill class by copy-constructing from val
1147  try
1148  {
1149  // fill container by copy constructing value
1150  for (int i = 0; i < m_capacity; ++i)
1151  {
1152  emplace_back(val);
1153  }
1154  }
1155  catch (...)
1156  {
1157  // if this fails, cleanup what's been done and then re-throw
1158  this->~circular_queue();
1159  throw;
1160  }
1161  }
1162 
1163  /**
1164  * @brief Range Constructor
1165  * @details Creates a container by copying the objects in the range of the InputIterators [first, last).
1166  * The size and capacity of the container will be equal to the size of the range.\n
1167  * <b> Complexity:</b> O(N) with range.\n
1168  * <b> Iterator Validity:</b> No changes.\n
1169  * <b> Data Races:</b> N/A.\n
1170  * <b> Exception Safety:</b> Throws std::bad_alloc if allocation fails. In this
1171  * case, no object is created.\n
1172  * @param[in] first iterator to the beginning of the range to copy.
1173  * @param[in] last iterator to the end (one past the last element) of the range to copy.
1174  * @param[in] alloc Allocator object. The container keeps and uses an internal copy of this
1175  * allocator.
1176  */
1177  template<class InputIterator>
1178  explicit circular_queue(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type(), typename std::enable_if<!std::is_integral<InputIterator>::value>::type* = 0)
1179  : m_alloc(alloc)
1180  , m_capacity(last - first)
1181  , m_head(nullptr, false)
1182  , m_tail(nullptr, false)
1183  {
1184  static_assert(std::is_convertible<value_type, typename std::iterator_traits<InputIterator>::value_type>::value,
1185  "InputIterator::value_type is not compatible with this container's value_type");
1186 
1187  if (m_capacity == 0)
1188  {
1189  throw std::bad_alloc();
1190  }
1191 
1192  // allocate raw memory near this class.
1193  try
1194  {
1195  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1196  }
1197  catch (...)
1198  {
1199  // Since constructor failed, no object will be created. Memory wasn't allocated, so no
1200  // cleanup is required.
1201  // transparent exceptions
1202  throw std::bad_alloc();
1203  }
1204  m_head.ptr = m_tail.ptr = m_data;
1205 
1206  // fill class by copy-constructing from val
1207  try
1208  {
1209  // fill container by copy constructing from the iterators
1210  for (auto itr = first; itr != last; ++itr)
1211  {
1212  emplace_back(*itr);
1213  }
1214  }
1215  catch (...)
1216  {
1217  // if this fails, cleanup what's been done and then re-throw
1218  this->~circular_queue();
1219  throw;
1220  }
1221  }
1222 
1223  /**
1224  * @brief construct from initializer list
1225  * @details constructs the circular_queue by copying elements from the initializer_list. The
1226  * size and capacity of the queue will be equal to the initializer_list size.\n
1227  * <b> Complexity:</b> Linear with size of <i>il</i> (constructions).\n
1228  * <b> Iterator Validity:</b> N/A.\n
1229  * <b> Data Races:</b> N/A.\n
1230  * <b> Exception Safety:</b> Throws std::bad_alloc if allocation fails. In this
1231  * case, no object is created.\n
1232  * @param[in] il initializer_list object.
1233  * @param[in] alloc Allocator object. The container keeps and uses an internal copy of this
1234  */
1235  circular_queue(std::initializer_list<value_type> il, const allocator_type& alloc = allocator_type())
1236  : m_alloc(alloc)
1237  , m_capacity(il.size())
1238  , m_head(nullptr, false)
1239  , m_tail(nullptr, false)
1240  {
1241  if (m_capacity == 0)
1242  {
1243  throw std::bad_alloc();
1244  }
1245 
1246  // allocate raw memory near this class.
1247  try
1248  {
1249  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1250  }
1251  catch (...)
1252  {
1253  // Since constructor failed, no object will be created. Memory wasn't allocated, so no
1254  // cleanup is required.
1255  // transparent exceptions
1256  throw std::bad_alloc();
1257  }
1258 
1259  m_head.ptr = m_tail.ptr = m_data;
1260 
1261  // fill class by copy-constructing from val
1262  try
1263  {
1264  // fill container by copy constructing from the iterators
1265  for (auto itr = il.begin(); itr != il.end(); ++itr)
1266  {
1267  emplace_back(*itr);
1268  }
1269  }
1270  catch (...)
1271  {
1272  // if this fails, cleanup what's been done and then re-throw
1273  this->~circular_queue();
1274  throw;
1275  }
1276  }
1277 
1278  /**
1279  * @brief Copy Constructor
1280  * @details Creates a deep copy of another circular_queue.\n
1281  * <b> Complexity:</b> O(N) with buffer capacity (memory allocation/copy).\n
1282  * <b> Iterator Validity:</b> N/A.\n
1283  * <b> Data Races:</b> N/A.\n
1284  * <b> Exception Safety:</b> Throws std::bad_alloc if allocation fails. In this
1285  * case, no object is created.\n
1286  * @param[in] other buffer to be copied
1287  */
1288  circular_queue(const circular_queue& other)
1289  : m_alloc(std::allocator_traits<decltype(other.m_alloc)>::select_on_container_copy_construction(other.m_alloc))
1290  , m_capacity(other.m_capacity)
1291  , m_head(other.m_head)
1292  , m_tail(other.m_tail)
1293  {
1294  // allocate raw memory near this class. No point in default constructing anything, especially since this buffer
1295  // may be HUGE.
1296  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1297 
1298  // correct head/tail pointers
1299  m_head.ptr = m_data + (other.m_head.ptr - other.m_data);
1300  m_tail.ptr = m_data + (other.m_tail.ptr - other.m_data);
1301 
1302  // Deep copy the other data - need to copy construct each individual element. No memcpy!!
1303  for (const_iterator itr = this->begin(), otherItr = other.begin(); otherItr != other.end(); ++itr, ++otherItr)
1304  {
1305  // copy construct
1306  std::allocator_traits<Alloc>::construct(m_alloc, &itr, *otherItr);
1307  }
1308  }
1309 
1310  /**
1311  * @brief move constructor
1312  * @details constructs a circular_queue and obtains its resources by moving them from another
1313  * instance.\n
1314  * <b> Complexity:</b> Constant.\n
1315  * <b> Iterator Validity:</b> All iterators to the other container are invalidated.\n
1316  * <b> Data Races:</b> Container <i>other</i> is modified.\n
1317  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1318  * exceptions.\n
1319  * @param[in] other circular_queue to be moved.
1320  */
1321  circular_queue(circular_queue&& other) noexcept
1322  : m_alloc(std::move(other.m_alloc))
1323  , m_capacity(std::move(other.m_capacity))
1324  , m_head(std::move(other.m_head))
1325  , m_tail(std::move(other.m_tail))
1326  {
1327  // self assignment could be bad.
1328  if (this != &other)
1329  {
1330  // steal allocated storage from other class
1331  m_data = other.m_data;
1332  other.m_data = nullptr;
1333  other.m_capacity = 0;
1334  other.m_head.ptr = nullptr;
1335  other.m_tail.ptr = nullptr;
1336  other.m_head.parity = false;
1337  other.m_tail.parity = false;
1338  }
1339  }
1340 
1341  /** @} */ // END OF CONSTRUCTORS
1342 
1343  //////////////////////////////////////////////////////////////////////////
1344  // #DESTRUCTORS
1345  //////////////////////////////////////////////////////////////////////////
1346 
1347  /**
1348  * @{
1349  * @name Destructor
1350  */
1351 
1352  /**
1353  * @brief destructor
1354  * @details Yeah, you know what this is.
1355  */
1356  virtual ~circular_queue()
1357  {
1358  // destroy contents
1359  clear();
1360  // deallocate memory
1361  m_alloc.deallocate(m_data, m_capacity);
1362  }
1363 
1364  /** @} */ // end of destructors
1365 
1366  //////////////////////////////////////////////////////////////////////////
1367  // #OPERATORS
1368  //////////////////////////////////////////////////////////////////////////
1369 
1370  /**
1371  * @{
1372  * @name Operators
1373  */
1374 
1375  /**
1376  * @brief Assign content
1377  * @details copies all the elements from <i>other</i> into the container (with <i>other</i>
1378  * preserving its contents).\n
1379  * <b> Complexity:</b> Linear in initial and final sizes (destructions, copy constructions).\n
1380  * <b> Iterator Validity:</b> All iterators, references and pointers related to
1381  * this container before the call are invalidated.\n
1382  * <b> Data Races:</b> All copied elements are accessed. The container and all its
1383  * elements are modified.\n
1384  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
1385  * container is in a valid state. If allocator_traits::construct is not
1386  * supported with the appropriate arguments for the element constructions, or
1387  * if value_type is not copy assignable, it causes undefined behavior.\n
1388  * @param[in] other container to copy
1389  * @sa
1390  * @returns *this
1391  */
1392  circular_queue& operator=(const circular_queue& other)
1393  {
1394  // destroy and deallocate current container first
1395  this->~circular_queue();
1396 
1397  if (std::allocator_traits<decltype(other.m_alloc)>::propagate_on_container_copy_assignment::value)
1398  {
1399  m_alloc = other.m_alloc;
1400  }
1401 
1402  m_capacity = other.m_capacity;
1403  m_head.parity = other.m_head.parity;
1404  m_tail.parity = other.m_tail.parity;
1405 
1406  // allocate raw memory near this class. No point in default constructing anything, especially since this buffer
1407  // may be HUGE.
1408  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
1409 
1410  // correct head/tail pointers
1411  m_head.ptr = m_data + (other.m_head.ptr - other.m_data);
1412  m_tail.ptr = m_data + (other.m_tail.ptr - other.m_data);
1413 
1414  // Deep copy the other data - need to copy construct each individual element. No memcpy!!
1415  for (const_iterator itr = this->begin(), otherItr = other.begin(); otherItr != other.end(); ++itr, ++otherItr)
1416  {
1417  // copy construct
1418  std::allocator_traits<Alloc>::construct(m_alloc, &itr, *otherItr);
1419  }
1420 
1421  return *this;
1422  }
1423 
1424  /**
1425  * @brief Assign content
1426  * @details moves all the elements from <i>other</i> into the container (with <i>other</i>
1427  * in an unspecified but valid state).\n
1428  * <b> Complexity:</b> Linear in Size (destructions).\n
1429  * <b> Iterator Validity:</b> All iterators, references and pointers related to
1430  * this container before the call are invalidated.\n
1431  * <b> Data Races:</b> All copied elements are accessed. The container and all its
1432  * elements are modified.\n
1433  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
1434  * container is in a valid state. If allocator_traits::construct is not
1435  * supported with the appropriate arguments for the element constructions, or
1436  * if value_type is not move assignable, it causes undefined behavior.\n
1437  * @param[in] other container to move
1438  * @sa assign()
1439  * @returns *this
1440  */
1441  circular_queue& operator=(circular_queue&& other) noexcept
1442  {
1443  // destroy and deallocate current container first
1444  this->~circular_queue();
1445 
1446  if (std::allocator_traits<decltype(other.m_alloc)>::propagate_on_container_move_assignment::value)
1447  {
1448  m_alloc = std::move(other.m_alloc);
1449  }
1450 
1451  m_capacity = std::move(other.m_capacity);
1452  m_head = std::move(other.m_head);
1453  m_tail = std::move(other.m_tail);
1454 
1455  // steal allocated storage from other class
1456  m_data = other.m_data;
1457 
1458  // set everything in the other class to null
1459  other.m_data = nullptr;
1460  other.m_capacity = 0;
1461  other.m_head.ptr = nullptr;
1462  other.m_tail.ptr = nullptr;
1463  other.m_head.parity = false;
1464  other.m_tail.parity = false;
1465 
1466  return *this;
1467  }
1468 
1469  /**
1470  * @brief Assign content
1471  * @details Assigns new contents to the container, replacing its current contents, and
1472  * modifying its size accordingly. The new contents are copies of the values passed
1473  * as initializer list, in the same order.\n
1474  * <b> Complexity:</b> Linear in initial and final sizes (destructions, constructions).\n
1475  * <b> Iterator Validity:</b> All iterators, references and pointers related to
1476  * this container before the call are invalidated.
1477  * <b> Data Races:</b> All copied elements are accessed. The container and all its
1478  * elements are modified.\n
1479  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
1480  * container is in a valid state. If allocator_traits::construct is not
1481  * supported with the appropriate arguments for the element constructions, or
1482  * if value_type is not move assignable, it causes undefined behavior.\n
1483  * @param[in] il initializer list object.
1484  * @returns circular_queue&
1485  */
1486  circular_queue& operator=(std::initializer_list<value_type> il)
1487  {
1488  assign(std::forward<std::initializer_list<value_type>>(il));
1489  return *this;
1490  }
1491 
1492  /**
1493  * @brief Access element
1494  * @details Returns a reference to the element at position n in the container. A similar
1495  * member function, at(), has the same behavior as this operator function, except
1496  * that at() is bound-checked and signals if the requested position is out of range
1497  * by throwing an out_of_range exception. Portable programs should never call this
1498  * function with an argument n that is out of range, since this causes undefined
1499  * behavior.\n
1500  * <b> Complexity:</b> Constant.\n
1501  * <b> Iterator Validity:</b> No changes.\n
1502  * <b> Data Races:</b> The container is accessed (neither the const nor the
1503  * non-const versions modify the container). The reference returned can be used to
1504  * access or modify elements. Concurrently accessing or modifying different
1505  * elements is safe.\n
1506  * <b> Exception Safety:</b> If the container size is greater than n, the function
1507  * never throws exceptions (no-throw guarantee). Otherwise, the behavior is
1508  * undefined.\n
1509  * @param[in] n Position of an element in the container. Notice that the first element has a
1510  * position of 0 (not 1). Member type size_type is an unsigned integral type.
1511  * @returns The element at the specified position in the circular_queue.
1512  */
1513  reference operator[](size_type n)
1514  {
1515  assert(n < m_capacity);
1516  return *(m_data + ((m_head.ptr - m_data + n) % m_capacity));
1517  }
1518 
1519  /// @overload
1520  const_reference operator[](size_type n) const
1521  {
1522  assert(n < m_capacity);
1523  return *(m_data + ((m_head.ptr - m_data + n) % m_capacity));
1524  }
1525 
1526  /** @} */ // end of operators
1527 
1528  //////////////////////////////////////////////////////////////////////////
1529  // #ITERATORS
1530  //////////////////////////////////////////////////////////////////////////
1531 
1532  /**
1533  * @{
1534  * @name Iterators
1535  * @brief Methods to construct iterators to the container.
1536  */
1537 
1538  /**
1539  * @brief Returns iterator to beginning
1540  * @details Returns an iterator to the head (first element) in the container.\n
1541  * <b> Complexity:</b> Constant.\n
1542  * <b> Iterator Validity:</b> No changes.\n
1543  * <b> Data Races:</b> The container is accessed (neither the const nor the
1544  * non-const versions modify the container). No contained elements are accessed by
1545  * the call, but the iterator returned can be used to access or modify elements.
1546  * Concurrently accessing or modifying different elements is safe.\n
1547  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1548  * exceptions. The copy construction or assignment of the returned iterator is also
1549  * guaranteed to never throw.\n
1550  * @returns An iterator to the beginning of the sequence container.
1551  */
1552  iterator begin() noexcept
1553  {
1554  return iterator(this, m_head);
1555  }
1556 
1557  /// @overload
1558  const_iterator begin() const noexcept
1559  {
1560  return const_iterator(this, m_head);
1561  }
1562 
1563  /**
1564  * @brief Returns iterator to end
1565  * @details Returns an iterator to the tail (last element) in the container.\n
1566  * <b> Complexity:</b> Constant.\n
1567  * <b> Iterator Validity:</b> No changes.\n
1568  * <b> Data Races:</b> The container is accessed (neither the const nor the
1569  * non-const versions modify the container). No contained elements are accessed by
1570  * the call, but the iterator returned can be used to access or modify elements.
1571  * Concurrently accessing or modifying different elements is safe.\n
1572  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1573  * exceptions. The copy construction or assignment of the returned iterator is also
1574  * guaranteed to never throw.\n
1575  * @returns An iterator to the end of the sequence container.
1576  */
1577  iterator end() noexcept
1578  {
1579  return iterator(this, m_tail);
1580  }
1581 
1582  /// @overload
1583  const_iterator end() const noexcept
1584  {
1585  return const_iterator(this, m_tail);
1586  }
1587 
1588  /**
1589  * @function rbegin
1590  * @brief Returns reverse iterator to beginning
1591  * @details Returns a reverse iterator to the reverse beginning (last element) in the
1592  * container. rbegin points to the element right before the one that would be
1593  * pointed to by end().\n
1594  * <b> Complexity:</b> Constant.\n
1595  * <b> Iterator Validity:</b> No changes.\n
1596  * <b> Data Races:</b> The container is accessed (neither the const nor the
1597  * non-const versions modify the container). No contained elements are accessed by
1598  * the call, but the iterator returned can be used to access or modify elements.
1599  * Concurrently accessing or modifying different elements is safe.\n
1600  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1601  * exceptions. The copy construction or assignment of the returned iterator is also
1602  * guaranteed to never throw.\n
1603  * @returns A reverse iterator to the beginning of the sequence container.
1604  */
1605  reverse_iterator rbegin() noexcept
1606  {
1607  return reverse_iterator(end());
1608  }
1609 
1610  /// @overload
1611  const_reverse_iterator rbegin() const noexcept
1612  {
1613  return const_reverse_iterator(end());
1614  }
1615 
1616  /**
1617  * @brief Returns reverse iterator to end
1618  * @details Returns a reverse iterator pointing to the theoretical element preceding the
1619  * first element in the container (which is considered its reverse end).\n
1620  * <b> Complexity:</b> Constant.\n
1621  * <b> Iterator Validity:</b> No changes.\n
1622  * <b> Data Races:</b> The container is accessed (neither the const nor the
1623  * non-const versions modify the container). No contained elements are accessed by
1624  * the call, but the iterator returned can be used to access or modify elements.
1625  * Concurrently accessing or modifying different elements is safe.\n
1626  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1627  * exceptions. The copy construction or assignment of the returned iterator is also
1628  * guaranteed to never throw.\n
1629  * @returns A reverse iterator to the end of the sequence container.
1630  */
1631  reverse_iterator rend() noexcept
1632  {
1633  return reverse_iterator(begin());
1634  }
1635 
1636  /// @overload
1637  const_reverse_iterator rend() const noexcept
1638  {
1639  return const_reverse_iterator(begin());
1640  }
1641 
1642  /**
1643  * @brief Returns constant iterator to beginning
1644  * @details Returns a constant iterator to the head (first element) in the container. A
1645  * const_iterator is an iterator that points to const content. This iterator can be
1646  * increased and decreased (unless it is itself also const), just like the iterator
1647  * returned by begin(), but it cannot be used to modify the contents it points to,
1648  * even if the container object is not itself const.\n
1649  * <b> Complexity:</b> Constant.\n
1650  * <b> Iterator Validity:</b> No changes.\n
1651  * <b> Data Races:</b> The container is accessed (neither the const nor the
1652  * non-const versions modify the container). No contained elements are accessed by
1653  * the call, but the iterator returned can be used to access or modify elements.
1654  * Concurrently accessing or modifying different elements is safe.\n
1655  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1656  * exceptions. The copy construction or assignment of the returned iterator is also
1657  * guaranteed to never throw.\n
1658  * @returns A constant iterator to the beginning of the sequence container.
1659  */
1660  const_iterator cbegin() const noexcept
1661  {
1662  return const_iterator(this, m_head);
1663  }
1664 
1665  /**
1666  * @brief Returns constant iterator to end
1667  * @details Returns a constant iterator to the tail (last element) in the container.A
1668  * const_iterator is an iterator that points to const content. This iterator can be
1669  * increased and decreased (unless it is itself also const), just like the iterator
1670  * returned by begin(), but it cannot be used to modify the contents it points to,
1671  * even if the container object is not itself const.\n
1672  * <b> Complexity:</b> Constant.\n
1673  * <b> Iterator Validity:</b> No changes.\n
1674  * <b> Data Races:</b> The container is accessed (neither the const nor the
1675  * non-const versions modify the container). No contained elements are accessed by
1676  * the call, but the iterator returned can be used to access or modify elements.
1677  * Concurrently accessing or modifying different elements is safe.\n
1678  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1679  * exceptions. The copy construction or assignment of the returned iterator is also
1680  * guaranteed to never throw.\n
1681  * @returns A constant iterator to the end of the sequence container.
1682  */
1683  const_iterator cend() const noexcept
1684  {
1685  return const_iterator(this, m_tail);
1686  }
1687 
1688  /**
1689  * @brief Returns constant iterator to beginning
1690  * @details Returns a reverse iterator to the reverse beginning (last element) in the
1691  * container. crbegin points to the element right before the one that would be
1692  * pointed to by end(). A const_reverse_iterator is an iterator that points to const content.
1693  * This iterator can be increased and decreased (unless it is itself also const),
1694  * just like the iterator returned by begin(), but it cannot be used to modify the
1695  * contents it points to, even if the container object is not itself const.\n
1696  * <b> Complexity:</b> Constant.\n
1697  * <b> Iterator Validity:</b> No changes.\n
1698  * <b> Data Races:</b> The container is accessed (neither the const nor the
1699  * non-const versions modify the container). No contained elements are accessed by
1700  * the call, but the iterator returned can be used to access or modify elements.
1701  * Concurrently accessing or modifying different elements is safe.\n
1702  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1703  * exceptions. The copy construction or assignment of the returned iterator is also
1704  * guaranteed to never throw.\n
1705  * @returns A constant iterator to the beginning of the sequence container.
1706  */
1707  const_reverse_iterator crbegin() const noexcept
1708  {
1709  return const_reverse_iterator(end());
1710  }
1711 
1712  /**
1713  * @brief Returns constant iterator to end
1714  * @details Returns a reverse iterator pointing to the theoretical element preceding the
1715  * first element in the container (which is considered its reverse end). A
1716  * const_reverse_iterator is an iterator that points to const content. This iterator can be
1717  * increased and decreased (unless it is itself also const), just like the iterator
1718  * returned by begin(), but it cannot be used to modify the contents it points to,
1719  * even if the object is not itself const.\n
1720  * <b> Complexity:</b> Constant.\n
1721  * <b> Iterator Validity:</b> No changes.\n
1722  * <b> Data Races:</b> The container is accessed (neither the const nor the
1723  * non-const versions modify the container). No contained elements are accessed by
1724  * the call, but the iterator returned can be used to access or modify elements.
1725  * Concurrently accessing or modifying different elements is safe.\n
1726  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1727  * exceptions. The copy construction or assignment of the returned iterator is also
1728  * guaranteed to never throw.\n
1729  * @returns A constant iterator to the end of the sequence container.
1730  */
1731  const_reverse_iterator crend() const noexcept
1732  {
1733  return const_reverse_iterator(begin());
1734  }
1735 
1736  /** @} */ // END OF ITERATORS
1737 
1738  //////////////////////////////////////////////////////////////////////////
1739  // #CAPACITY
1740  //////////////////////////////////////////////////////////////////////////
1741 
1742  /**
1743  * @{
1744  * @name Capacity
1745  * @brief Methods to determine the capacity of the container
1746  */
1747 
1748  /**
1749  * @brief Return size
1750  * @details Returns the number of elements in the container.\n
1751  * <b> Complexity:</b> Constant.\n
1752  * <b> Iterator Validity:</b> No changes.\n
1753  * <b> Data Races:</b> The container is accessed. No contained elements are accessed:
1754  * concurrently accessing or modifying them is safe.\n
1755  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
1756  * exceptions..\n
1757  * @returns The number of elements in the container. Member type size_type is an unsigned
1758  * integral type.
1759  */
1760  [[nodiscard]] inline size_type size() const noexcept
1761  {
1762  if (m_head.parity == m_tail.parity)
1763  {
1764  // difference between head and tail represents amount used.
1765  return static_cast<size_type>(m_tail.ptr - m_head.ptr);
1766  }
1767  else
1768  {
1769  // difference between head and tail represents amount unused.
1770  return (m_capacity - static_cast<size_type>(m_head.ptr - m_tail.ptr));
1771  }
1772  }
1773 
1774  /**
1775  * @brief Get buffer capacity
1776  * @details Returns the allocated size of the buffer. For the amount of the buffer in use,
1777  * see size().\n
1778  * <b> Complexity:</b> Constant.\n
1779  * <b> Iterator Validity:</b> No changes.\n
1780  * <b> Data Races:</b> The container object is accessed.\n
1781  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1782  * exceptions.\n
1783  * @sa size()
1784  * @returns capacity of the buffer in terms of how many objects of <i>value_type</i> it can contain.
1785  */
1786  [[nodiscard]] size_type capacity() const noexcept
1787  {
1788  return m_capacity;
1789  }
1790 
1791  /**
1792  * @brief Return maximum capacity
1793  * @details Returns the maximum number of elements that the container can hold. This
1794  * is the maximum potential capacity the container can reach due to known system or
1795  * library implementation limitations, but the container is by no means guaranteed
1796  * to be able to reach that capacity: it can still fail to allocate storage at any
1797  * point before that capacity is reached.\n
1798  * <b> Complexity:</b> Constant.\n
1799  * <b> Iterator Validity:</b> No changes.\n
1800  * <b> Data Races:</b> The container is accessed, but no contained elements are
1801  * accessed. Concurrently accessing or modifying them is safe.\n
1802  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1803  * exceptions.\n
1804  * @returns Maximum number of elements of type <i>value_type</i> that can be stored in the
1805  * container.
1806  */
1807  [[nodiscard]] size_type max_size() const noexcept
1808  {
1809  return std::allocator_traits<Alloc>::max_size(m_alloc);
1810  }
1811 
1812  /**
1813  * @brief Test whether container is empty
1814  * @details Returns whether the container is empty (i.e. whether its size is 0).\n
1815  * <b> Complexity:</b> Constant.\n
1816  * <b> Iterator Validity:</b> No changes.\n
1817  * <b> Data Races:</b> The container object is accessed, but no elements are accessed.\n
1818  * <b> Exception Safety:</b> No-throw guarantee: This function never throws
1819  * exceptions.\n
1820  * @returns true if the buffer is empty, false otherwise.
1821  */
1822  [[nodiscard]] inline bool empty() const noexcept
1823  {
1824  return (size() == 0);
1825  }
1826 
1827  /**
1828  * @brief Test whether container is full
1829  * @details Returns whether the container is empty (i.e. whether its size is equal to it's capacity).\n
1830  * <b> Complexity:</b> Constant.\n
1831  * <b> Iterator Validity:</b> No changes.\n
1832  * <b> Data Races:</b> The container object is accessed, but no elements are accessed.\n
1833  * <b> Exception Safety:</b> .\n
1834  * @returns bool
1835  */
1836  [[nodiscard]] inline bool full() const noexcept
1837  {
1838  return (size() >= m_capacity);
1839  }
1840 
1841  /**
1842  * @brief Request a change in capacity
1843  * @details Requests that the vector capacity be at least enough to contain n elements. If
1844  * n is greater than the current capacity, the function causes the container to
1845  * reallocate its storage increasing its capacity to n. In all other cases, the
1846  * function call does not cause a reallocation and the vector capacity is not
1847  * affected.\n
1848  * <b> Complexity:</b> If a reallocation happens, linear in size at most..\n
1849  * <b> Iterator Validity:</b> If a reallocation happens, all iterators, pointers
1850  * and references related to the container are invalidated. Otherwise, they all
1851  * keep referring to the same elements they were referring to before the call.\n
1852  * <b> Data Races:</b> If a reallocation happens, the container and all its
1853  * contained elements are modified.\n
1854  * <b> Exception Safety:</b> If no reallocations happen or if the type of the
1855  * elements has either a non-throwing move constructor or a copy constructor,
1856  * there are no changes in the container in case of exception (strong guarantee).
1857  * Otherwise, the container is guaranteed to end in a valid state (basic guarantee).
1858  * Under the basic guarantee, if this function throws, it's possible that all the
1859  * container contents will be destroyed as a side-effect.
1860  * The function throws bad_alloc if it fails to allocate the new size.\n
1861  * @param[in] n Minimum capacity for the container.
1862  */
1863  void reserve(size_type n)
1864  {
1865  if (n <= size())
1866  {
1867  return;
1868  }
1869 
1870  reallocate(n);
1871  }
1872 
1873  /**
1874  * @brief Change size
1875  * @details Changes <i>both</i> the size and capacity of the container, resizing the
1876  * container so that it contains n elements. If n is smaller than the current
1877  * container size, the content is reduced to its first n elements, removing those
1878  * beyond (and destroying them). If n is greater than the current container size,
1879  * the content is expanded by inserting at the end as many elements as needed to
1880  * reach a size of n. If val is specified, the new elements are initialized as
1881  * copies of val, otherwise, they are value-initialized. Regardless of the value of n
1882  * (except n == size()), an automatic reallocation of the allocated
1883  * storage space takes place. Notice that this function changes the actual content
1884  * of the container by inserting or erasing elements from it.\n
1885  * <b> Complexity:</b> Linear on the number of elements inserted/erased
1886  * (constructions/destructions). If a reallocation happens, the reallocation
1887  * is itself up to linear in the entire container size.\n
1888  * <b> Iterator Validity:</b> Resizing causes reallocation, and so all iterators, pointers and references
1889  * related to this container are also invalidated.\n
1890  * <b> Data Races:</b> The container is modified. If a reallocation happens, all
1891  * contained elements are modified.\n
1892  * <b> Exception Safety:</b> If n is less than or equal to the size of the container,
1893  * the function never throws exceptions (no-throw guarantee). If n is greater
1894  * and a reallocation happens, there are no changes in the container in case of
1895  * exception (strong guarantee) if the type of the elements is either copyable
1896  * or no-throw movable. Otherwise, if an exception is thrown, the container is
1897  * left with a valid state (basic guarantee).\n
1898  * @param[in] n New container size, expressed in number of elements. Member type <i>size_type</i>
1899  * is an unsigned integral type.
1900  * @param[in] val Object whose content is copied to the added elements in case that n is
1901  * greater than the current container size. If not specified, the default
1902  * constructor is used instead.
1903  */
1904  void resize(size_type n, const value_type& val = value_type())
1905  {
1906  // just because they tell you to jump off a bridge...
1907  if (n == size())
1908  {
1909  return;
1910  }
1911  // if we're making it bigger, it's just a reserve + copy fill
1912  else if (n > size())
1913  {
1914  // reserve moves all the existing elements in
1915  reserve(n);
1916  // fill the rest with val copies
1917  while (size() < capacity())
1918  {
1919  emplace_back(val);
1920  }
1921  }
1922  // if we're making it smaller, pop the back until it's the right size, then deallocate the
1923  // extra.
1924  else
1925  {
1926  while (size() > n)
1927  {
1928  pop_back();
1929  }
1930  shrink_to_fit();
1931  }
1932  }
1933 
1934  /**
1935  * @brief Shrink container to fit
1936  * @details Requests the container to reduce its capacity to fit its size. Unlike vector,
1937  * the request is binding. This will never cause a reallocation, and has no effect
1938  * on the size or element contents.\n
1939  * <b> Complexity:</b> At most, linear in container size..\n
1940  * <b> Iterator Validity:</b> All iterators, pointers and references related to the
1941  * container are invalidated.\n
1942  * <b> Data Races:</b> The container is modified. All contained objects are moved.\n
1943  * <b> Exception Safety:</b> If the type of the elements is either copyable or
1944  * no-throw movable, there are no changes in the container in case of exception
1945  * (strong guarantee). Otherwise, if an exception is thrown, the container is
1946  * left with a valid state (basic guarantee).\n
1947  */
1948  void shrink_to_fit()
1949  {
1950  if (capacity() == size())
1951  {
1952  return;
1953  }
1954 
1955  reallocate(size());
1956  }
1957 
1958  /** @} */ // END OF CAPACITY
1959 
1960  //////////////////////////////////////////////////////////////////////////
1961  // #ELEMENT ACCESS
1962  //////////////////////////////////////////////////////////////////////////
1963 
1964  /**
1965  * @{
1966  * @name Element Access
1967  * @brief Members that provide access to individual elements contained withing the circular_queue
1968  */
1969 
1970  /**
1971  * @brief Access element
1972  * @details Returns a reference to the element at position n in the container object.
1973  * The function automatically checks whether n is within the bounds of valid
1974  * elements in the container, throwing an out_of_range exception if it is not
1975  * (i.e., if n is greater or equal than its size). This is in contrast with member
1976  * operator[], that does not check against bounds.\n
1977  * <b> Complexity:</b> Constant.\n
1978  * <b> Iterator Validity:</b> .\n
1979  * <b> Data Races:</b> .\n
1980  * <b> Exception Safety:</b> .\n
1981  * @param[in] n Position of an element in the container. If this is greater than the container
1982  * size, an exception of type out_of_range is thrown. Notice that the first element
1983  * has a position of 0 (not 1). Member type size_type is an unsigned integral type.
1984  * @returns The element at the specified position in the container. If the circular_queue
1985  * object is const-qualified, the function returns a const_reference. Otherwise,
1986  * it returns a reference.
1987  */
1988  reference at(size_type n)
1989  {
1990  if (n >= size())
1991  {
1992  throw std::out_of_range("index larger than container size");
1993  }
1994 
1995  return *(m_data + ((m_head.ptr - m_data + n) % m_capacity));
1996  }
1997 
1998  /// @overload
1999  const_reference at(size_type n) const
2000  {
2001  if (n >= size())
2002  {
2003  throw std::out_of_range("index larger than container size");
2004  }
2005 
2006  return *(m_data + ((m_head.ptr - m_data + n) % m_capacity));
2007  }
2008 
2009  /**
2010  * @brief Access first element
2011  * @details Returns a reference to the first element in the circular_queue. Unlike member
2012  * begin(), which returns an iterator to this same element, this function returns
2013  * a direct reference. Calling this function on an empty container causes undefined
2014  * behavior.\n
2015  * <b> Complexity:</b> Constant.\n
2016  * <b> Iterator Validity:</b> No changes.\n
2017  * <b> Data Races:</b> The container is accessed (neither the const nor the
2018  * non-const versions modify the container). The reference returned can be used
2019  * to access or modify elements. Concurrently accessing or modifying different
2020  * elements is safe.\n
2021  * <b> Exception Safety:</b> If the container is not empty, the function never
2022  * throws exceptions (no-throw guarantee). Otherwise, it causes undefined
2023  * behavior.\n
2024  * @returns A reference to the first element in the circular_queue.
2025  */
2026  reference front() noexcept
2027  {
2028  return *m_head.ptr;
2029  }
2030 
2031  /// @overload
2032  const_reference front() const noexcept
2033  {
2034  return *m_head.ptr;
2035  }
2036 
2037  /**
2038  * @brief Access last element
2039  * @details Returns a reference to the last element in the circular_queue. Unlike member
2040  * end(), which returns an iterator just past this element, this function returns
2041  * a direct reference. Calling this function on an empty container causes undefined
2042  * behavior.\n
2043  * <b> Complexity:</b> Constant.\n
2044  * <b> Iterator Validity:</b> No changes.\n
2045  * <b> Data Races:</b> The container is accessed (neither the const nor the
2046  * non-const versions modify the container). The reference returned can be used
2047  * to access or modify elements. Concurrently accessing or modifying different
2048  * elements is safe.\n
2049  * <b> Exception Safety:</b> If the container is not empty, the function never
2050  * throws exceptions (no-throw guarantee). Otherwise, it causes undefined
2051  * behavior.\n
2052  * @returns A reference to the last element in the circular_queue.
2053  */
2054  reference back()
2055  {
2056  queue_pointer p = decrement(m_tail, 1);
2057  return *p.ptr;
2058  }
2059 
2060  /// @overload
2061  const_reference back() const
2062  {
2063  queue_pointer p = decrement(m_tail, 1);
2064  return *p.ptr;
2065  }
2066 
2067  /** @} */ // end of element_access
2068 
2069  //////////////////////////////////////////////////////////////////////////
2070  // #MODIFIERS
2071  //////////////////////////////////////////////////////////////////////////
2072 
2073  /**
2074  * @{
2075  * @name Modifiers
2076  * @brief Member functions that modify the container.
2077  */
2078 
2079  /**
2080  * @brief Assign container content range
2081  * @details Assigns new contents to the container, replacing its current contents, and
2082  * modifying its size and capacity accordingly.The new contents are elements
2083  * constructed from each of the elements in the range
2084  * between first and last, in the same order. The range used is [first, last).\n
2085  * <b> Complexity:</b> Linear in initial and final sizes (destructions, constructions).\n
2086  * <b> Iterator Validity:</b> All iterators are invalidated.\n
2087  * <b> Data Races:</b> The container and all elements are modified. All copied
2088  * elements are accessed.\n
2089  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
2090  * container is in a valid state. If allocator_traits::construct is not
2091  * supported with the appropriate arguments for the element constructions, or
2092  * if the range specified by [first,last) is not valid, it causes undefined
2093  * behavior. Throws std::length_error if first == last.\n
2094  * @param[in] first beginning of the range to copy.
2095  * @param[in] last end (exclusive) of the range to be copied.
2096  * @sa operator=
2097  */
2098  template<class InputIterator>
2099  void assign(InputIterator first, InputIterator last)
2100  {
2101  static_assert(std::is_convertible<value_type, typename std::iterator_traits<InputIterator>::value_type>::value,
2102  "InputIterator::value_type is not compatible with this container's value_type");
2103 
2104  // check that there is a valid range
2105  difference_type distance = last - first;
2106  if (distance == 0)
2107  {
2108  throw std::length_error("Cannot assign capacity of 0");
2109  }
2110 
2111  // delete and deallocate current contents
2112  this->~circular_queue();
2113 
2114  // set new capacity
2115  m_capacity = distance;
2116 
2117  // allocate raw memory near this class.
2118  try
2119  {
2120  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
2121  }
2122  catch (...)
2123  {
2124  // transparent exceptions
2125  // leave container in valid state
2126  m_capacity = 0;
2127  m_head.ptr = m_tail.ptr = m_data = nullptr;
2128  m_head.parity = m_tail.parity = false;
2129  throw std::bad_alloc();
2130  }
2131 
2132  m_head.ptr = m_tail.ptr = m_data;
2133  m_head.parity = m_tail.parity = false;
2134 
2135  // fill class
2136  try
2137  {
2138  // fill container by copy constructing from the iterators
2139  for (auto itr = first; itr != last; ++itr)
2140  {
2141  emplace_back(*itr);
2142  }
2143  }
2144  catch (...)
2145  {
2146  // if this fails, delete whats been made
2147  clear();
2148  throw;
2149  }
2150  }
2151 
2152  /**
2153  * @brief Assign container content by fill
2154  * @details Assigns new contents to the container, replacing its current contents,
2155  * and modifying its size and capacity accordingly. The new contents are n elements, each
2156  * initialized to a copy of val.\n
2157  * <b> Complexity:</b> Linear in initial and final sizes (destructions, constructions).\n
2158  * <b> Iterator Validity:</b> All iterators, pointers, and references are invalidated.\n
2159  * <b> Data Races:</b> The container and all elements are modified. All copied
2160  * elements are accessed.\n
2161  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
2162  * container is in a valid state. If allocator_traits::construct is not
2163  * supported with the appropriate arguments for the element constructions, or
2164  * if the range specified by [first,last) is not valid, it causes undefined
2165  * behavior. Throws std::length_error if first == last.\n
2166  * @param[in] n new container size
2167  * @param[in] val value to be copied into each element of the container.
2168  */
2169  void assign(size_type n, const value_type& val)
2170  {
2171  // check that there is a valid range
2172  if (n == 0)
2173  {
2174  throw std::length_error("Cannot assign capacity of 0");
2175  }
2176 
2177  // delete and deallocate current contents
2178  this->~circular_queue();
2179 
2180  // set new capacity
2181  m_capacity = n;
2182 
2183  // allocate raw memory near this class.
2184  try
2185  {
2186  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity > n ? m_capacity : n, this);
2187  }
2188  catch (...)
2189  {
2190  // transparent exceptions
2191  // leave container in valid state
2192  m_capacity = 0;
2193  m_head.ptr = m_tail.ptr = m_data = nullptr;
2194  m_head.parity = m_tail.parity = false;
2195  throw std::bad_alloc();
2196  }
2197 
2198  m_head.ptr = m_tail.ptr = m_data;
2199  m_head.parity = m_tail.parity = false;
2200 
2201  // fill class
2202  try
2203  {
2204  // fill container by copy constructing val
2205  for (size_type i = 0; i < n; ++i)
2206  {
2207  emplace_back(val);
2208  }
2209  }
2210  catch (...)
2211  {
2212  // if this fails, cleanup what's been done and then re-throw
2213  // if this fails, delete whats been made
2214  clear();
2215  throw;
2216  }
2217  }
2218 
2219  /**
2220  * @brief Assign container contents from initializer list
2221  * @details Assigns new contents to the container, replacing its current contents, and
2222  * modifying its size and capacity accordingly. The new contents are copies of the
2223  * values passed as initializer list, in the same order.\n
2224  * <b> Complexity:</b> Linear in initial and final sizes (destructions, constructions).\n
2225  * <b> Iterator Validity:</b> All iterators, pointers and references related to this container are invalidated.\n
2226  * <b> Data Races:</b> All copied elements are accessed. The container is modified.
2227  * All contained elements are modified.\n
2228  * <b> Exception Safety:</b> Basic guarantee: if an exception is thrown, the
2229  * container is in a valid state. If allocator_traits::construct is not supported
2230  * with the appropriate arguments for the element constructions it causes
2231  * undefined behavior. If the initializer list is empty, std::length_error is
2232  * thrown.\n
2233  * @param[in] il An initializer_list object. The compiler will automatically construct such
2234  * objects from initializer list declarators. Member type value_type is the type of
2235  * the elements in the container, defined in circular_queue as an alias of its first
2236  * template parameter (T).
2237  * @sa operator=
2238  */
2239  void assign(std::initializer_list<value_type> il)
2240  {
2241  // check that there is a valid range
2242  if (il.size() == 0)
2243  {
2244  throw std::length_error("Cannot assign capacity of 0");
2245  }
2246 
2247  // delete and deallocate current contents
2248  this->~circular_queue();
2249 
2250  // set new capacity
2251  m_capacity = il.size();
2252 
2253  // allocate raw memory near this class.
2254  try
2255  {
2256  m_data = std::allocator_traits<Alloc>::allocate(m_alloc, m_capacity, this);
2257  }
2258  catch (...)
2259  {
2260  // transparent exceptions
2261  // leave container in valid state
2262  m_capacity = 0;
2263  m_head.ptr = m_tail.ptr = m_data = nullptr;
2264  m_head.parity = m_tail.parity = false;
2265  throw std::bad_alloc();
2266  }
2267 
2268  m_head.ptr = m_tail.ptr = m_data;
2269  m_head.parity = m_tail.parity = false;
2270 
2271  // fill class
2272  try
2273  {
2274  // fill container by copy constructing val
2275  for (auto itr = il.begin(); itr != il.end(); ++itr)
2276  {
2277  emplace_back(*itr);
2278  }
2279  }
2280  catch (...)
2281  {
2282  // if this fails, cleanup what's been done and then re-throw
2283  // if this fails, delete whats been made
2284  clear();
2285  throw;
2286  }
2287  }
2288 
2289  /**
2290  * @brief Clear content
2291  * @details Removes all elements from the deque (which are destroyed), leaving the container
2292  * with a size of 0.\n
2293  * <b> Complexity:</b> Linear in size (destructions).\n
2294  * <b> Iterator Validity:</b> All iterators, pointers and references related to
2295  * this container are invalidated.\n
2296  * <b> Data Races:</b> The container is modified.
2297  * All contained elements are modified.\n
2298  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
2299  * exceptions.\n
2300  */
2301  void clear() noexcept
2302  {
2303  // destroy contained objects
2304  for (iterator itr = this->begin(); itr != this->end(); ++itr)
2305  {
2306  std::allocator_traits<Alloc>::destroy(m_alloc, const_cast<T*>(&itr));
2307  }
2308  // reset pointers. DON'T deallocate memory.
2309  m_head.ptr = m_tail.ptr = m_data;
2310  m_head.parity = m_tail.parity = false;
2311  }
2312 
2313  /**
2314  * @brief Add element at the end
2315  * @details Adds a new element at the end of the container, after its current last element.
2316  * The content of val is copied (or moved) to the new element. This effectively
2317  * increases the container size by one. If the circular_queue is full, it will cause
2318  * the element at the front of the queue to be overwritten.\n
2319  * <b> Complexity:</b> Constant.\n
2320  * <b> Iterator Validity:</b> Only the end iterator is invalidated, and all iterators,
2321  * pointers and references to elements are guaranteed to keep referring to the
2322  * same elements they were referring to before the call.\n
2323  * <b> Data Races:</b> The container is modified. If full, the first element in the
2324  * queue is modified. Concurrently accessing or modifying other elements is safe.\n
2325  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2326  * (basic guarantee). If the element is copyable or no-throw movable, then there
2327  * are no side effects (strong guarantee). If the container is not full, then there
2328  * are no side effects (strong guarantee). If the container is full, and an
2329  * exception occurs, the first element in the container will be destroyed. If
2330  * allocator_traits::construct is not supported with val as argument, it causes
2331  * undefined behavior.\n
2332  * @param[in] val value to copy/move into the end of the container. Member type value_type is
2333  * the type of the elements in the container, defined in vector as an alias of
2334  * its first template parameter (T).
2335  */
2336  void push_back(const value_type& val)
2337  {
2338  // make sure if the push fails the queue is in a valid state
2339  try
2340  {
2341  if (full())
2342  {
2343  // copy assign the new object. Unlike emplace, no need to pop because we'll just
2344  // hijack the existing object instead.
2345  value_type* pos = m_head.ptr;
2346  m_head = increment(m_head, 1);
2347  *pos = val; // this can throw
2348  }
2349  else
2350  {
2351  // copy construct the new object. This could throw.
2352  std::allocator_traits<Alloc>::construct(m_alloc, m_tail.ptr, val); // this can throw
2353  }
2354  }
2355  catch (...)
2356  {
2357  // transparent exceptions
2358  throw std::bad_alloc();
2359  }
2360 
2361  // it allocated OK, update state
2362  m_tail = increment(m_tail, 1);
2363  }
2364 
2365  /// @overload
2366  void push_back(value_type&& val)
2367  {
2368  // make sure if the push fails the queue is in a valid state
2369  try
2370  {
2371  if (full())
2372  {
2373  // copy assign the new object. Unlike emplace, no need to pop because we'll just
2374  // hijack the existing object instead.
2375  value_type* pos = m_head.ptr;
2376  m_head = increment(m_head, 1);
2377  *pos = std::move(val); // this can throw
2378  }
2379  else
2380  {
2381  // copy construct the new object. This could throw.
2382  std::allocator_traits<Alloc>::construct(m_alloc, m_tail.ptr, std::move(val)); // this can throw
2383  }
2384  }
2385  catch (...)
2386  {
2387  // transparent exceptions
2388  throw std::bad_alloc();
2389  }
2390 
2391  // it allocated OK, update state
2392  m_tail = increment(m_tail, 1);
2393  }
2394 
2395  /**
2396  * @brief Add element at beginning
2397  * @details Adds a new element at the beginning of the container, right before its current first element.
2398  * The content of val is copied (or moved) to the new element. This effectively
2399  * increases the container size by one. If the circular_queue is full, it will cause
2400  * the element at the end of the queue to be overwritten.\n
2401  * <b> Complexity:</b> Constant.\n
2402  * <b> Iterator Validity:</b> Only the begin iterator is invalidated, and all iterators,
2403  * pointers and references to elements are guaranteed to keep referring to the
2404  * same elements they were referring to before the call.\n
2405  * <b> Data Races:</b> The container is modified. If full, the last element in the
2406  * queue is modified. Concurrently accessing or modifying other elements is safe.\n
2407  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2408  * (basic guarantee). If the element is copyable or no-throw movable, then there
2409  * are no side effects (strong guarantee). If allocator_traits::construct is
2410  * not supported with val as argument, it causes undefined behavior.\n
2411  * @param[in] val value to copy/move into the end of the container. Member type value_type is
2412  * the type of the elements in the container, defined in vector as an alias of
2413  * its first template parameter (T).
2414  */
2415  void push_front(const value_type& val)
2416  {
2417  // make sure if the push fails the queue is in a valid state
2418  try
2419  {
2420  if (full())
2421  {
2422  // copy assign the new object. Unlike emplace, no need to pop because we'll just
2423  // hijack the existing object instead.
2424  m_head = decrement(m_head, 1);
2425  *m_head.ptr = val;
2426  m_tail = decrement(m_tail, 1);
2427  }
2428  else
2429  {
2430  // copy construct the new object. This could throw.
2431  m_head = decrement(m_head, 1);
2432  std::allocator_traits<Alloc>::construct(m_alloc, m_head.ptr, val);
2433  }
2434  }
2435  catch (...)
2436  {
2437  // return head to it's previous position
2438  m_head = increment(m_head, 1);
2439 
2440  // transparent exceptions
2441  throw std::bad_alloc();
2442  }
2443  }
2444 
2445  /// @overload
2446  void push_front(value_type&& val)
2447  {
2448  // make sure if the push fails the queue is in a valid state
2449  try
2450  {
2451  if (full())
2452  {
2453  // copy assign the new object. Unlike emplace, no need to pop because we'll just
2454  // hijack the existing object instead.
2455  m_head = decrement(m_head, 1);
2456  *m_head.ptr = std::move(val);
2457  m_tail = decrement(m_tail, 1);
2458  }
2459  else
2460  {
2461  // copy construct the new object. This could throw.
2462  m_head = decrement(m_head, 1);
2463  std::allocator_traits<Alloc>::construct(m_alloc, m_head.ptr, std::move(val));
2464  }
2465  }
2466  catch (...)
2467  {
2468  // return head to it's previous position
2469  m_head = increment(m_head, 1);
2470 
2471  // transparent exceptions
2472  throw std::bad_alloc();
2473  }
2474  }
2475 
2476  /**
2477  * @brief Delete last element
2478  * @details Removes the last element in the circular_queue container, effectively reducing
2479  * its size by one. This destroys the removed element. Popping an empty queue
2480  * results in undefined behavior.\n
2481  * <b> Complexity:</b> Constant.\n
2482  * <b> Iterator Validity:</b> The iterators, pointers and references referring to
2483  * the removed element are invalidated. Iterators, pointers and references
2484  * referring to other elements that have not been removed are guaranteed to
2485  * keep referring to the same elements they were referring to before the call.\n
2486  * <b> Data Races:</b> The container is modified. The last element is modified.
2487  * Concurrently accessing or modifying other elements is safe (although see
2488  * iterator validity above).\n
2489  * <b> Exception Safety:</b> If the container is not empty, the function never
2490  * throws exceptions (no-throw guarantee). Otherwise, it causes undefined behavior.
2491  */
2492  inline void pop_back() noexcept
2493  {
2494  m_tail = decrement(m_tail, 1);
2495  std::allocator_traits<Alloc>::destroy(m_alloc, m_tail.ptr);
2496  }
2497 
2498  /**
2499  * @brief Delete first element
2500  * @details Removes the first element in the circular_queue container, effectively reducing
2501  * its size by one. This destroys the removed element. Popping an empty queue
2502  * results in undefined behavior.\n
2503  * <b> Complexity:</b> Constant.\n
2504  * <b> Iterator Validity:</b> The iterators, pointers and references referring to
2505  * the removed element are invalidated. Iterators, pointers and references
2506  * referring to other elements that have not been removed are guaranteed to
2507  * keep referring to the same elements they were referring to before the call.\n
2508  * <b> Data Races:</b> The container is modified. The first element is modified.
2509  * Concurrently accessing or modifying other elements is safe (although see
2510  * iterator validity above).\n
2511  * <b> Exception Safety:</b> If the container is not empty, the function never
2512  * throws exceptions (no-throw guarantee). Otherwise, it causes undefined behavior.
2513  */
2514  inline void pop_front() noexcept
2515  {
2516  std::allocator_traits<Alloc>::destroy(m_alloc, m_head.ptr); // if your destructor throws than you are an asshole (and not writing valid c++) and don't you dare blame my container.
2517  m_head = increment(m_head, 1);
2518  }
2519 
2520  /**
2521  * @brief Insert (copy) single element
2522  * @details The container is extended by inserting an element before the element at the
2523  * specified position. This effectively increases the container size by 1. If the
2524  * container is full, the element at begin() is overwritten. Makes at most 1 copy
2525  * of val.\n
2526  * Double-ended queues are designed to be efficient performing insertions (and removals)
2527  * from either the end or the beginning of the sequence. Insertions on other positions
2528  * are usually less efficient than in list or forward_list containers.\n
2529  * <b> Complexity:</b> Linear on the number of elements inserted (copy/move
2530  * construction) plus an additional linear in the number of elements between
2531  * position and the end of the container.\n
2532  * <b> Iterator Validity:</b> All iterators, pointers and references from position
2533  * to the end of the queue are invalidated.\n
2534  * <b> Data Races:</b> The container is modified. It is not safe to concurrently
2535  * access elements.\n
2536  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2537  * (basic guarantee). If allocator_traits::construct is not supported with the
2538  * appropriate arguments for the element constructions, or if an invalid position
2539  * or range is specified, it causes undefined behavior.\n
2540  * @param[in] position Position in the container where the new elements are inserted. Iterator
2541  * is a member type, defined as a random access iterator type that points to elements.
2542  * @param[in] val Value to be copied (or moved) to the inserted elements. Member type value_type
2543  * is the type of the elements in the container, defined in deque as an alias of
2544  * its first template parameter (T).
2545  * @sa push_back()
2546  * @sa push_front()
2547  * @returns An iterator that points to the newly inserted element.
2548  */
2549  iterator insert(const_iterator position, const value_type& val)
2550  {
2551  assert(position.m_buffer == this);
2552 
2553  // increase size of container by 1
2554  push_back(val);
2555 
2556  // swap the new element down to the position we're supposed to insert it at
2557  return swapDownTo(position, 1);
2558  }
2559 
2560  /**
2561  * @brief Insert (move) single element
2562  * @details The container is extended by inserting an element before the element at the
2563  * specified position. This effectively increases the container size by 1. If the
2564  * container is full, the element at begin() is overwritten. Makes no copies of val,
2565  * and val must be <i>move-assignable</i>.\n
2566  * Double-ended queues are designed to be efficient performing insertions (and removals)
2567  * from either the end or the beginning of the sequence. Insertions on other positions
2568  * are usually less efficient than in list or forward_list containers.\n
2569  * <b> Complexity:</b> Linear on the number of elements inserted (copy/move
2570  * construction) plus an additional linear in the number of elements between
2571  * position and the end of the container.\n
2572  * <b> Iterator Validity:</b> All iterators, pointers and references from position
2573  * to the end of the queue are invalidated.\n
2574  * <b> Data Races:</b> The container is modified. It is not safe to concurrently
2575  * access elements.\n
2576  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2577  * (basic guarantee). If allocator_traits::construct is not supported with the
2578  * appropriate arguments for the element constructions, or if an invalid position
2579  * or range is specified, it causes undefined behavior.\n
2580  * @param[in] position Position in the container where the new elements are inserted. Iterator
2581  * is a member type, defined as a random access iterator type that points to elements.
2582  * @param[in] val Value to be copied (or moved) to the inserted elements. Member type value_type
2583  * is the type of the elements in the container, defined in deque as an alias of
2584  * its first template parameter (T).
2585  * @sa push_back()
2586  * @sa push_front()
2587  * @returns An iterator that points to the newly inserted element.
2588  */
2589  iterator insert(const_iterator position, value_type&& val)
2590  {
2591  assert(position.m_buffer == this);
2592 
2593  // increase size of container by 1
2594  push_back(std::move(val));
2595 
2596  // swap the new element down to the position we're supposed to insert it at
2597  return swapDownTo(position, 1);
2598  }
2599 
2600  /**
2601  * @brief Insert (fill) elements
2602  * @details The container is extended by inserting new elements before the element at the
2603  * specified position. This effectively increases the container size by the amount
2604  * of elements inserted. If this size is greater than the current capacity,
2605  * the elements at the beginning of the queue will be over-written. This operation
2606  * will cause at most n copies of <i>val</i>.\n
2607  * Double-ended queues are designed to be efficient performing insertions (and removals)
2608  * from either the end or the beginning of the sequence. Insertions on other
2609  * positions are usually less efficient than in list or forward_list containers.\n
2610  * <b> Complexity:</b> O(m*n) where m is the current size and m is the number of
2611  * elements inserted.\n
2612  * <b> Iterator Validity:</b> All iterators, pointers and references are invalidated.\n
2613  * <b> Data Races:</b> The container is modified. It is not safe to concurrently
2614  * access elements.\n
2615  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2616  * (basic guarantee). If allocator_traits::construct is not supported with the
2617  * appropriate arguments for the element constructions, or if an invalid position
2618  * or range is specified, it causes undefined behavior.\n
2619  * @param[in] position the fill will be inserted before the element at this position.
2620  * @param[in] n Number of elements to insert. Each element is initialized to a copy of val.
2621  * @param[in] val Value to be copied to the inserted elements. Member type value_type is the
2622  * type of the elements in the container, defined in circular_queue as an alias of
2623  * its first template parameter (T).
2624  * @sa push_back()
2625  * @sa push_front()
2626  * @returns An iterator that points to the first of the newly inserted elements.
2627  */
2628  iterator insert(const_iterator position, size_type n, const value_type& val)
2629  {
2630  assert(position.m_buffer == this);
2631 
2632  // increase size of container by n
2633  for (size_type i = 0; i < (n < capacity() ? n : capacity()); ++i)
2634  {
2635  push_back(val); // this can change begin()
2636  }
2637 
2638  // if we filled more than the capacity, no need to swap
2639  if (n >= capacity()) return begin();
2640 
2641  // swap the new elements down to the position we're supposed to insert it at
2642  return swapDownTo(position, n);
2643  }
2644 
2645  /**
2646  * @brief Insert (range) elements
2647  * @details The container is extended by inserting new elements before the element at the
2648  * specified position. This effectively increases the container size by the amount
2649  * of elements inserted. If this size is greater than the current capacity,
2650  * the elements at the beginning of the queue will be over-written. This operation
2651  * will cause at most capacity() copies. The range of copied values is [first, last).\n
2652  * Double-ended queues are designed to be efficient performing insertions (and removals)
2653  * from either the end or the beginning of the sequence. Insertions on other
2654  * positions are usually less efficient than in list or forward_list containers.\n
2655  * <b> Complexity:</b> Linear on the number of elements inserted (copy/move
2656  * construction) plus an additional linear in the number of elements between
2657  * position and the end of the container.\n
2658  * <b> Iterator Validity:</b> All iterators, pointers and references are invalidated.\n
2659  * <b> Data Races:</b> The container is modified. It is not safe to concurrently
2660  * access elements.\n
2661  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2662  * (basic guarantee). If allocator_traits::construct is not supported with the
2663  * appropriate arguments for the element constructions, or if an invalid position
2664  * or range is specified, it causes undefined behavior.\n
2665  * @param[in] position the fill will be inserted before the element at this position.
2666  * @param[in] first iterator to beginning of range to insert. InputIterator can be an iterator
2667  * to any type of container, as long as it is at least a forward iterator.
2668  * @param[in] last iterator to one-past-end of range to insert. InputIterator can be an iterator
2669  * to any type of container, as long as it is at least a forward iterator.
2670  * type of the elements in the container, defined in circular_queue as an alias of
2671  * its first template parameter (T).
2672  * @sa push_back()
2673  * @sa push_front()
2674  * @returns An iterator that points to the first of the newly inserted elements.
2675  */
2676  template<class InputIterator>
2677  iterator insert(const_iterator position, InputIterator first, InputIterator last)
2678  {
2679  static_assert(std::is_base_of<std::forward_iterator_tag, typename std::iterator_traits<InputIterator>::iterator_category>::value,
2680  "Insert (range) requires InputIterator to be at least a forward iterator.");
2681 
2682  static_assert(std::is_convertible<typename std::iterator_traits<InputIterator>::value_type, value_type>::value,
2683  "InputIterator::value_type is not implicitly convertible to circular_queue::value_type.");
2684 
2685  assert(position.m_buffer == this);
2686 
2687  size_type n = last - first;
2688 
2689  InputIterator start = first;
2690  if (n > capacity())
2691  {
2692  start = last - capacity();
2693  }
2694 
2695  // increase size of container by n
2696  for (InputIterator i = std::move(start); i < last; ++i)
2697  {
2698  push_back(*i); // this can change begin()
2699  }
2700 
2701  // if we filled more than the capacity, no need to swap
2702  if (n >= capacity()) return begin();
2703 
2704  // swap the new elements down to the position we're supposed to insert it at
2705  return swapDownTo(position, n);
2706  }
2707 
2708  /**
2709  * @brief Insert elements (initializer_list)
2710  * @details The container is extended by inserting new elements before the element at the
2711  * specified position. This effectively increases the container size by the amount
2712  * of elements inserted. If this size is greater than the current capacity,
2713  * the elements at the beginning of the queue will be over-written. This operation
2714  * will cause at most capacity() copies.\n
2715  * Double-ended queues are designed to be efficient performing insertions (and removals)
2716  * from either the end or the beginning of the sequence. Insertions on other
2717  * positions are usually less efficient than in list or forward_list containers.\n
2718  * <b> Complexity:</b> Linear on the number of elements inserted (copy/move
2719  * construction) plus an additional linear in the number of elements between
2720  * position and the end of the container.\n
2721  * <b> Iterator Validity:</b> All iterators, pointers and references are invalidated.\n
2722  * <b> Data Races:</b> The container is modified. It is not safe to concurrently
2723  * access elements.\n
2724  * <b> Exception Safety:</b> The container is guaranteed to end in a valid state
2725  * (basic guarantee). If allocator_traits::construct is not supported with the
2726  * appropriate arguments for the element constructions, or if an invalid position
2727  * or range is specified, it causes undefined behavior.\n
2728  * @param[in] position the fill will be inserted before the element at this position.
2729  * @param[in] il initializer_list object, filled with values to insert into the container.
2730  * @sa push_back()
2731  * @sa push_front()
2732  * @returns An iterator that points to the first of the newly inserted elements.
2733  */
2734  iterator insert(const_iterator position, std::initializer_list<value_type> il)
2735  {
2736  return insert(position, il.begin(), il.end());
2737  }
2738 
2739  /**
2740  * @brief Erase element
2741  * @details Removes from deque container a single element (<i>position</i>).
2742  * This effectively reduces the container size by the number of elements removed,
2743  * which are destroyed.\n
2744  * Double-ended queues are designed to be efficient removing (and inserting) elements
2745  * at either the end or the beginning of the sequence. Removals on other positions
2746  * are usually less efficient than in list or forward_list containers.
2747  * <b> Complexity:</b> Linear in the distance from <i>position</i> to end().\n
2748  * <b> Iterator Validity:</b> All iterators, pointers, and references to elements
2749  * between <i>position</i> and end() are invalidated.\n
2750  * <b> Data Races:</b> If the erasure happens at the end of the sequence, only the
2751  * erased elements are modified. Otherwise it is not safe to access or modify
2752  * elements.\n
2753  * <b> Exception Safety:</b> If the removed elements include the the last element
2754  * in the container, no exceptions are thrown (no-throw guarantee). Otherwise,
2755  * the container is guaranteed to end in a valid state (basic guarantee): Copying
2756  * or moving elements while relocating them may throw. Invalid ranges produce
2757  * undefined behavior.
2758  * @param[in] position Iterator pointing to a single element to be removed from the container.
2759  * @returns An iterator pointing to the new location of the element that followed the last
2760  * element erased by the function call. This is the container end if the operation
2761  * erased the last element in the sequence.
2762  */
2763  iterator erase(const_iterator position)
2764  {
2765  assert(position.m_buffer == this);
2766 
2767  // swap the elements to delete to the back of the queue
2768  swapUpToEnd(position, 1);
2769  pop_back();
2770 
2771  return iterator(this, position.m_pointer);
2772  }
2773 
2774  /**
2775  * @brief Erase elements
2776  * @details Removes from the deque container the range of elements ([<i>first</i>,<i>last</i>)).
2777  * This effectively reduces the container size by the number of elements removed,
2778  * which are destroyed.\n
2779  * Double-ended queues are designed to be efficient removing (and inserting) elements
2780  * at either the end or the beginning of the sequence. Removals on other positions
2781  * are usually less efficient than in list or forward_list containers.
2782  * <b> Complexity:</b> Linear in the distance from <i>position</i> to end() times
2783  * the number of elements erased.\n
2784  * <b> Iterator Validity:</b> All iterators, pointers, and references to elements
2785  * between <i>position</i> and end() are invalidated.\n
2786  * <b> Data Races:</b> If the erasure happens at the end of the sequence, only the
2787  * erased elements are modified. Otherwise it is not safe to access or modify
2788  * elements.\n
2789  * <b> Exception Safety:</b> If the removed elements include the the last element
2790  * in the container, no exceptions are thrown (no-throw guarantee). Otherwise,
2791  * the container is guaranteed to end in a valid state (basic guarantee): Copying
2792  * or moving elements while relocating them may throw. Invalid ranges produce
2793  * undefined behavior.
2794  * @param[in] first iterator to beginning of range to erase from the container
2795  * @param[in] last iterator to one-past-last element of range to erase from the container
2796  * @returns An iterator pointing to the new location of the element that followed the last
2797  * element erased by the function call. This is the container end if the operation
2798  * erased the last element in the sequence.
2799  */
2800  iterator erase(const_iterator first, const_iterator last)
2801  {
2802  assert(first.m_buffer == this);
2803  assert(last.m_buffer == this);
2804  assert(last > first);
2805 
2806  difference_type n = last - first;
2807 
2808  swapUpToEnd(first, n);
2809 
2810  for (difference_type i = 0; i < n; ++i)
2811  {
2812  pop_back();
2813  }
2814 
2815  return iterator(this, first.m_pointer);
2816  }
2817 
2818  /**
2819  * @brief Swap content
2820  * @details Exchanges the content of the container by the content of <i>other</i>, which is
2821  * another circular_queue object containing elements of the same type. Sizes may differ.
2822  * After the call to this member function, the elements in this container are those
2823  * which were in <i>other</i> before the call, and the elements of <i>other</i> are
2824  * those which were in <i>this</i>. All iterators, references and pointers remain
2825  * valid for the swapped objects. Notice that a non-member function exists with the
2826  * same name, swap, overloading that algorithm with an optimization that behaves
2827  * like this member function.\n
2828  * <b> Complexity:</b> Constant.\n
2829  * <b> Iterator Validity:</b> All iterators, pointers and references referring to
2830  * elements in both containers remain valid, and are now referring to the same elements
2831  * they referred to before the call, but in the other container, where they now iterate.\n
2832  * <b> Data Races:</b> Both the container and <i>other</i> are modified. No contained
2833  * elements are accessed by the call.\n
2834  * <b> Exception Safety:</b> If the allocators in both containers compare equal, or
2835  * if their allocator traits indicate that the allocators shall propagate, the
2836  * function never throws exceptions (no-throw guarantee). Otherwise, it causes
2837  * undefined behavior.\n
2838  * @param[in] other container to swap with <i>this</i>.
2839  */
2840  void swap(circular_queue& other) noexcept
2841  {
2842  if (std::allocator_traits<decltype(other.m_alloc)>::propagate_on_container_swap::value)
2843  {
2844  allocator_type temp = this->m_alloc;
2845  this->m_alloc = other.m_alloc;
2846  other.m_alloc = temp;
2847  }
2848 
2849  auto tempData = this->m_data;
2850  this->m_data = other.m_data;
2851  other.m_data = tempData;
2852 
2853  auto tempCapacity = this->m_capacity;
2854  this->m_capacity = other.m_capacity;
2855  other.m_capacity = tempCapacity;
2856 
2857  auto tempHead = this->m_head;
2858  this->m_head = other.m_head;
2859  other.m_head = tempHead;
2860 
2861  auto tempTail = this->m_tail;
2862  this->m_tail = other.m_tail;
2863  other.m_tail = tempTail;
2864  }
2865 
2866  /**
2867  * @brief Construct and insert element
2868  * @details The container is extended by inserting a new element at position. This new element
2869  * is constructed in place using args as the arguments for its construction. This
2870  * effectively increases the container size by one. Double-ended queues are designed
2871  * to be efficient performing insertions (and removals) from either the end or the
2872  * beginning of the sequence. Insertions on other positions are usually less efficient
2873  * than in list or forward_list containers. See emplace_front and emplace_back for
2874  * member functions that extend the container directly at the beginning or at the end.
2875  * The element is constructed in-place by calling allocator_traits::construct with
2876  * args forwarded.\n
2877  * <b> Complexity:</b> Linear in the number of elements between <i>position</i> and end().\n
2878  * <b> Iterator Validity:</b> All iterators, references, and pointers from
2879  * <i>position</i> to end() are invalidated.\n
2880  * <b> Data Races:</b> The container is modified. It is NOT safe to concurrently
2881  * access or modify elements.\n
2882  * <b> Exception Safety:</b> If position is end, there are no changes in the
2883  * container in case of exception (strong guarantee). Otherwise, the container
2884  * is guaranteed to end in a valid state (basic guarantee).\n
2885  * @param[in] position Position in the container where the new element is inserted. Member type
2886  * const_iterator is a random access iterator type that points to a constant element.
2887  * @param[in] args Arguments forwarded to construct the new element.
2888  * @sa emplace_front()
2889  * @sa emplace_back()
2890  */
2891  template<class... Args>
2892  iterator emplace(const_iterator position, Args&&... args)
2893  {
2894  assert(position.m_buffer == this);
2895 
2896  // increase size of container by 1
2897  emplace_back(std::forward<Args>(args)...);
2898 
2899  // swap the new element down to the position we're supposed to insert it at
2900  return swapDownTo(position, 1);
2901  }
2902 
2903  /**
2904  * @brief Construct and insert element at beginning
2905  * @details Inserts a new element at the beginning of the container, right before its
2906  * current first element. This new element is constructed in place using args as
2907  * the arguments for its construction.This effectively increases the container size by one.
2908  * The element is constructed in-place by calling allocator_traits::construct with
2909  * args forwarded. A similar member function exists, push_front, which either
2910  * copies or moves an existing object into the container.\n
2911  * <b> Complexity:</b> Constant.\n
2912  * <b> Iterator Validity:</b> The begin() iterator is invalidated. If the container was
2913  * full before the call, the end iterator is also invalidated. All other
2914  * iterators, pointers, and references remain valid.\n
2915  * <b> Data Races:</b> The container is modified. If the container was full, the
2916  * last element is destroyed. No other existing elements are accessed.\n
2917  * <b> Exception Safety:</b> If the container is not full, there are no side effects
2918  * (strong guarantee). Otherwise, if the function throws an exception, no
2919  * resources are leaked (basic guarantee), however the head of the container will be destroyed
2920  * even if emplace_back throws and no new object is added to the container.\n
2921  * @param[in] args arguments to the constructor of the contained object.
2922  */
2923  template<class... Args>
2924  void emplace_front(Args&&... args)
2925  {
2926  // make sure if the construction fails the queue is in a valid state
2927  try
2928  {
2929  // cleanup what the tail points to before over-writing it if we are full
2930  if (full())
2931  {
2932  pop_back();
2933  }
2934 
2935  m_head = decrement(m_head, 1);
2936 
2937  // construct the new object. This could throw.
2938  std::allocator_traits<Alloc>::construct(m_alloc, m_head.ptr, std::forward<Args>(args)...);
2939  }
2940  catch (...)
2941  {
2942  // undo head decrement
2943  m_head = increment(m_head, 1);
2944 
2945  // transparent exceptions
2946  throw std::bad_alloc();
2947  }
2948  }
2949 
2950  /**
2951  * @brief Construct and insert element at the end
2952  * @details Inserts a new element at the end of the circular_queue, right after its current
2953  * last element. This new element is constructed in place using args as the
2954  * arguments for its construction. This effectively increases the container capacity by
2955  * one. The element is constructed in-place by calling allocator_traits::construct
2956  * with args forwarded. A similar member function exists, push_back, which either
2957  * copies or moves an existing object into the container.\n
2958  * <b> Complexity:</b> Constant, if the contained object can be constructed in
2959  * constant time.\n
2960  * <b> Iterator Validity:</b> The end iterator is invalidated. If the container was
2961  * full before the call, the begin iterator is also invalidated. All other
2962  * iterators, pointers, and references remain valid.\n
2963  * <b> Data Races:</b> The container is modified. If the container was full, the
2964  * beginning element is destroyed. No other existing elements are accessed.\n
2965  * <b> Exception Safety:</b> If the container is not full, there are no side effects
2966  * (strong guarantee). Otherwise, if the function throws an exception, no
2967  * resources are leaked (basic guarantee), however the head of the container will be destroyed
2968  * even if emplace_back throws and no new object is added to the container.\n
2969  * @param[in] args arguments to the constructor of the contained object.
2970  */
2971  template<class... Args>
2972  void emplace_back(Args&&... args)
2973  {
2974  // make sure if the construction fails the queue is in a valid state
2975  try
2976  {
2977  // cleanup what the tail points to before over-writing it if we are full
2978  if (full())
2979  {
2980  pop_front();
2981  }
2982 
2983  // construct the new object. This could throw.
2984  std::allocator_traits<Alloc>::construct(m_alloc, m_tail.ptr, std::forward<Args>(args)...);
2985 
2986  // it allocated OK, update state
2987  m_tail = increment(m_tail, 1);
2988  }
2989  catch (...)
2990  {
2991  // transparent exceptions
2992  throw std::bad_alloc();
2993  }
2994  }
2995 
2996  /** @} */ // end of modifiers
2997 
2998  //////////////////////////////////////////////////////////////////////////
2999  // #ACCESSORS
3000  //////////////////////////////////////////////////////////////////////////
3001 
3002  /**
3003  * @{
3004  * @name Accessors
3005  * @brief Access member objects of the container
3006  */
3007 
3008  /**
3009  * @brief Get allocator
3010  * @details Returns a copy of the allocator object associated with the container.\n
3011  * <b> Complexity:</b> Constant.\n
3012  * <b> Iterator Validity:</b> No changes.\n
3013  * <b> Data Races:</b> The container is accessed. No contained elements are
3014  * accessed: concurrently accessing or modifying them is safe.\n
3015  * <b> Exception Safety:</b> No-throw guarantee: this member function never throws
3016  * exceptions. Copying any instantiation of the default allocator is also
3017  * guaranteed to never throw.\n
3018  * @returns the allocator.
3019  */
3020  allocator_type get_allocator() const noexcept
3021  {
3022  return m_alloc;
3023  }
3024 
3025  /**
3026  * @brief Copies range to destination buffer using provided copy function.
3027  * @details This function overloads memcpy to handle the internal complexities of copying a
3028  * circular_queue, which may or may not be wrapped. The resulting array at destination
3029  * will be unwrapped in either case, meaning logical and physical index[0] will always
3030  * be the same. Since this function isn't allocator or iterator aware on the destination
3031  * it's use should be avoided for EVERYTHING except compatibility with C code. In the
3032  * author's opinion, the ONLY use case for this function is CUDA memory.\n
3033  * *THIS MAY NOT WORK* if <i>value_type</i> does not exhibit bitwise copy semantics.
3034  * @param[in] first iterator to the first index to be copied.
3035  * @param[in] last iterator to the last index to be copied.
3036  * @param[out] destination output buffer where the data will be copied to.
3037  * @param[in] copy functor used to perform the memory copy. Options may include memcpy, memmove,
3038  * or bound versions of cudaMemcpy, cudaMemcpyAsync. Must have a signature of
3039  * copyFunctor(void* destination, void* source, size_t sizeInBytesToCopy)
3040  * @returns forwards the return value of <i>copyFunctor</i>.
3041  */
3042  template<class copyFunctor>
3043  auto copy(const_iterator first, const_iterator last, value_type* destination, copyFunctor cf) const -> decltype(cf((void*) destination, (void*) first.m_pointer.ptr, ((last.m_pointer.ptr - first.m_pointer.ptr) * sizeof(value_type))))
3044  {
3045 
3046  if (first.m_pointer.parity == last.m_pointer.parity)
3047  {
3048  // straight copy when the iterators have the same parity
3049  return cf((void*) destination, (void*) first.m_pointer.ptr, ((last.m_pointer.ptr - first.m_pointer.ptr) * sizeof(value_type)));
3050  }
3051  else
3052  {
3053  // if the buffer is wrapped, we need to mem copy in two parts
3054  size_t firstChunkSize = m_data + m_capacity - first.m_pointer.ptr; // units of value_type, NOT bytes
3055 
3056  cf((void*) destination, (void*) first.m_pointer.ptr, firstChunkSize * sizeof(value_type));
3057  return cf(destination + firstChunkSize, (void*) m_data, (last.m_pointer.ptr - m_data) * sizeof(value_type));
3058  }
3059  }
3060 
3061  /** @} */ // end of accessors
3062 
3063 protected:
3064  //////////////////////////////////////////////////////////////////////////
3065  // PROTECTED MEMBER FUNCTIONS
3066  //////////////////////////////////////////////////////////////////////////
3067 
3068  /**
3069  * @brief increments a pointer
3070  * @details Takes care of wrapping the pointer and keeping parity consistent.
3071  * @param[in] p pointer to increment. This function modifies the value of p.
3072  * @param[in] n number of elements to increment the pointer
3073  * @param[in] parity parity bit associated with the pointer. This function modifies the value
3074  * of parity.
3075  */
3076  inline queue_pointer increment(queue_pointer p, difference_type n) const noexcept
3077  {
3078  p.ptr += n;
3079 
3080  // wrap tail if it hits end of the buffer
3081  if (p.ptr >= this->m_data + this->m_capacity)
3082  {
3083  p.ptr = m_data + (p.ptr - (m_data + m_capacity));
3084  // flip the parity
3085  p.parity = !p.parity;
3086  return p;
3087  }
3088  else if (p.ptr < m_data)
3089  {
3090  // annoyingly, 'n' can be negative, so this check is required.
3091  p.ptr = m_data + m_capacity - (m_data - p.ptr);
3092  // flip parity
3093  p.parity = !p.parity;
3094  return p;
3095  }
3096 
3097  return p;
3098  }
3099 
3100  /// @overload
3101  inline const_queue_pointer increment(const_queue_pointer p, difference_type n) const noexcept
3102  {
3103  p.ptr += n;
3104 
3105  // wrap tail if it hits end of the buffer
3106  if (p.ptr >= m_data + m_capacity)
3107  {
3108  p.ptr = m_data + (p.ptr - (m_data + m_capacity));
3109  // flip the parity
3110  p.parity = !p.parity;
3111  return p;
3112  }
3113  else if (p.ptr < m_data)
3114  {
3115  // annoyingly, 'n' can be negative, so this check is required.
3116  p.ptr = m_data + m_capacity - (m_data - p.ptr);
3117  // flip parity
3118  p.parity = !p.parity;
3119  return p;
3120  }
3121 
3122  return p;
3123  }
3124 
3125  /**
3126  * @brief decrements a pointer
3127  * @details Takes care of wrapping the pointer and keeping parity consistent.
3128  * @param[in] p pointer to decrement. This function modifies the value of p.
3129  * @param[in] n number of elements to increment the pointer
3130  * @param[in] parity parity bit associated with the pointer. This function modifies the value
3131  * of parity.
3132  */
3133  inline queue_pointer decrement(queue_pointer p, difference_type n) const noexcept
3134  {
3135  p.ptr -= n;
3136 
3137  // wrap the tail if we hit the beginning of the buffer
3138  if (p.ptr < m_data)
3139  {
3140  p.ptr = m_data + m_capacity - (m_data - p.ptr);
3141  // flip parity
3142  p.parity = !p.parity;
3143  return p;
3144  }
3145  if (p.ptr >= m_data + m_capacity)
3146  {
3147  // annoyingly, 'n' can be negative, so this check is required.
3148  p.ptr = m_data + (p.ptr - (m_data + m_capacity));
3149  // flip the parity
3150  p.parity = !p.parity;
3151  return p;
3152  }
3153 
3154  return p;
3155  }
3156 
3157  /// @overload
3158  inline const_queue_pointer decrement(const_queue_pointer p, difference_type n, bool& parity) const noexcept
3159  {
3160  p.ptr -= n;
3161 
3162  // wrap the tail if we hit the beginning of the buffer
3163  if (p.ptr < m_data)
3164  {
3165  p.ptr = m_data + m_capacity - (m_data - p.ptr);
3166  // flip parity
3167  p.parity = !p.parity;
3168  return p;
3169  }
3170  if (p.ptr >= m_data + m_capacity)
3171  {
3172  // annoyingly, 'n' can be negative, so this check is required.
3173  p.ptr = m_data + (p.ptr - (m_data + m_capacity));
3174  // flip the parity
3175  p.parity = !p.parity;
3176  return p;
3177  }
3178 
3179  return p;
3180  }
3181 
3182  /**
3183  * @brief moves the currently contained data to a new area with size n.
3184  * @details O(n) complexity. Unwraps the buffer as a side effect.
3185  * @param[in] n size of new allocation
3186  */
3187  void reallocate(size_type n)
3188  {
3189  pointer newData;
3190  pointer newDataItr;
3191 
3192  try
3193  {
3194  newData = newDataItr = std::allocator_traits<Alloc>::allocate(m_alloc, n, this);
3195  }
3196  catch (...)
3197  {
3198  throw std::bad_alloc();
3199  }
3200 
3201  // move construct the queue to the new location. We can't just memcpy because we don't want
3202  // the queue to be wrapped with a new maximum size, it won't work.
3203  try
3204  {
3205  for (auto&& front : *this)
3206  {
3207  std::allocator_traits<Alloc>::construct(m_alloc, newDataItr, std::move(front));
3208  pop_front(); // this provides some exception safety by making sure the container state is always valid, even though we're going to overwrite it in a few lines.
3209  newDataItr++;
3210  }
3211  }
3212  catch (...)
3213  {
3214  // increment head past the thing that blew up
3215  m_head = increment(m_head, 1);
3216 
3217  // free the new data area
3218  pointer newDataDestroyer = newData;
3219  while (newDataDestroyer < newDataItr)
3220  {
3221  std::allocator_traits<Alloc>::destroy(m_alloc, newDataDestroyer);
3222  ++newDataDestroyer;
3223  }
3224  m_alloc.deallocate(newData, n);
3225 
3226  // just re-throw whatever happened.
3227  throw;
3228  }
3229 
3230  // deallocate old resources
3231  m_alloc.deallocate(m_data, m_capacity);
3232 
3233  // everything is moved, reset the internal state
3234  m_data = m_head.ptr = m_tail.ptr = newData;
3235  m_head.parity = m_tail.parity = false;
3236  m_capacity = n;
3237 
3238  // advance the tail
3239  difference_type distance = newDataItr - newData;
3240  for (difference_type diff = 0; diff < distance; ++diff)
3241  {
3242  m_tail = increment(m_tail, 1);
3243  }
3244  }
3245 
3246  /**
3247  * @brief Swaps the back of the queue down to position with elements n positions away
3248  * @details No-throw. O(n) complexity.
3249  * @param[in] position position to swap down to from the end
3250  * @param[in] n number of elements
3251  * @returns iterator to position of last element swapped.
3252  */
3253  inline iterator swapDownTo(const_iterator position, size_type n) noexcept
3254  {
3255  // create a non-const position iterator
3256  iterator pos(this, const_cast<value_type*>(position.m_pointer.ptr), position.m_pointer.parity);
3257 
3258  // the end iterator is the max of pos or begin (in case pos was consumed by push_back)
3259  pos = pos > begin() ? pos : begin();
3260 
3261  if (pos == end() - n) return pos;
3262 
3263  // swap val all the way down to its resting position
3264  for (size_type i = 0; i < n; ++i)
3265  {
3266  for (iterator swapItr = --end(); swapItr != pos; --swapItr)
3267  {
3268  // swap
3269  auto temp = std::move(*swapItr);
3270  *swapItr = std::move(*(swapItr - 1));
3271  *(swapItr - 1) = std::move(temp);
3272  }
3273  }
3274 
3275  return pos;
3276  }
3277 
3278  /**
3279  * @brief Moves the given position to the end of the queue by successively swapping it.
3280  * @details No-throw. O(n) complexity.
3281  * @param[in] position position to swap up to the end from
3282  * @param[in] n number of elements
3283  * @returns iterator to position of first element swapped.
3284  */
3285  inline iterator swapUpToEnd(const_iterator position, size_type n) noexcept
3286  {
3287  // create a non-const position iterator
3288  iterator pos(this, const_cast<pointer>(position.m_pointer.ptr), position.m_pointer.parity);
3289 
3290  // the end iterator is the max of pos or begin (in case pos was consumed by push_back)
3291  pos = pos > begin() ? pos : begin();
3292 
3293  if (pos == end() - n) return pos;
3294 
3295  // swap val all the way down to its resting position
3296  for (size_type i = 0; i < n; ++i)
3297  {
3298  for (iterator swapItr = pos; swapItr != end() - 1; ++swapItr)
3299  {
3300  // swap
3301  auto temp = std::move(*swapItr);
3302  *swapItr = std::move(*(swapItr + 1));
3303  *(swapItr + 1) = std::move(temp);
3304  }
3305  }
3306 
3307  return pos;
3308  }
3309 
3310 protected:
3311  Alloc m_alloc; ///< Allocator class. NOT c-style malloc.
3312  pointer m_data; ///< Pointer to the internal data array.
3313  size_type m_capacity; ///< capacity of the buffer array.
3314  queue_pointer m_head; ///< Points to the logical beginning of the buffer. No memory ownership!
3315  queue_pointer m_tail; ///< Points to the logical end of the buffer. No memory ownership!
3316 };
3317 
3318 #endif // circular_queue_h__
circular_queue::shrink_to_fit
void shrink_to_fit()
Shrink container to fit.
Definition: circular_queue.h:1948
circular_queue::const_iterator::operator<=
bool operator<=(const const_iterator &rhs) const
less-than-or-equal operator
Definition: circular_queue.h:555
circular_queue::const_iterator::m_buffer
const circular_queue * m_buffer
pointer to the buffer object that this iterates on.
Definition: circular_queue.h:596
circular_queue::const_iterator::operator->
pointer operator->() const
Dereference operator.
Definition: circular_queue.h:271
circular_queue::iterator::operator+=
iterator & operator+=(difference_type n) noexcept
Advance iterator.
Definition: circular_queue.h:827
circular_queue::decrement
queue_pointer decrement(queue_pointer p, difference_type n) const noexcept
decrements a pointer
Definition: circular_queue.h:3133
circular_queue::operator[]
const_reference operator[](size_type n) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1520
circular_queue::assign
void assign(std::initializer_list< value_type > il)
Assign container contents from initializer list.
Definition: circular_queue.h:2239
circular_queue::erase
iterator erase(const_iterator first, const_iterator last)
Erase elements.
Definition: circular_queue.h:2800
circular_queue::const_iterator::operator>=
bool operator>=(const const_iterator &rhs) const
greater-than-or-equal operator
Definition: circular_queue.h:589
circular_queue::max_size
size_type max_size() const noexcept
Return maximum capacity.
Definition: circular_queue.h:1807
circular_queue::iterator::operator==
bool operator==(const iterator &rhs) const noexcept
equality operator
Definition: circular_queue.h:760
circular_queue::operator[]
reference operator[](size_type n)
Access element.
Definition: circular_queue.h:1513
circular_queue::const_iterator::operator&
pointer operator&() const
Dereference operator.
Definition: circular_queue.h:256
circular_queue::const_iterator::operator>
bool operator>(const const_iterator &rhs) const
greater-than operator
Definition: circular_queue.h:572
circular_queue::circular_queue
circular_queue(std::initializer_list< value_type > il, const allocator_type &alloc=allocator_type())
construct from initializer list
Definition: circular_queue.h:1235
circular_queue::operator=
circular_queue & operator=(const circular_queue &other)
Assign content.
Definition: circular_queue.h:1392
circular_queue::crbegin
const_reverse_iterator crbegin() const noexcept
Returns constant iterator to beginning.
Definition: circular_queue.h:1707
circular_queue::iterator::operator-=
iterator & operator-=(difference_type n) noexcept
Retrocede iterator.
Definition: circular_queue.h:904
circular_queue::reallocate
void reallocate(size_type n)
moves the currently contained data to a new area with size n.
Definition: circular_queue.h:3187
circular_queue::const_iterator::operator-
difference_type operator-(const const_iterator &other) const
subtraction operator
Definition: circular_queue.h:497
circular_queue::insert
iterator insert(const_iterator position, value_type &&val)
Insert (move) single element.
Definition: circular_queue.h:2589
circular_queue::m_tail
queue_pointer m_tail
Points to the logical end of the buffer. No memory ownership!
Definition: circular_queue.h:3315
circular_queue::iterator::operator>=
bool operator>=(const iterator &rhs) const
greater-than-or-equal operator
Definition: circular_queue.h:1039
circular_queue::empty
bool empty() const noexcept
Test whether container is empty.
Definition: circular_queue.h:1822
circular_queue::iterator::operator const_iterator
operator const_iterator() const
Allow implicit conversion from iterator to const_iterator as required by STL.
Definition: circular_queue.h:1046
circular_queue::crend
const_reverse_iterator crend() const noexcept
Returns constant iterator to end.
Definition: circular_queue.h:1731
circular_queue::front
const_reference front() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:2032
circular_queue::const_iterator::~const_iterator
~const_iterator() noexcept=default
destructor. Complexity: Constant. Exception Safety: No-throw guarantee: This function never throws...
circular_queue::size
size_type size() const noexcept
Return size.
Definition: circular_queue.h:1760
circular_queue::copy
auto copy(const_iterator first, const_iterator last, value_type *destination, copyFunctor cf) const -> decltype(cf((void *) destination,(void *) first.m_pointer.ptr,((last.m_pointer.ptr - first.m_pointer.ptr) *sizeof(value_type))))
Copies range to destination buffer using provided copy function.
Definition: circular_queue.h:3043
circular_queue::const_iterator::operator!=
bool operator!=(const const_iterator &rhs) const
inequality operator Complexity: Constant. Iterator Validity: No changes. Data Races: The contain...
Definition: circular_queue.h:327
circular_queue::iterator::operator>
bool operator>(const iterator &rhs) const
greater-than operator
Definition: circular_queue.h:1022
circular_queue::pop_front
void pop_front() noexcept
Delete first element.
Definition: circular_queue.h:2514
circular_queue::push_front
void push_front(value_type &&val)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:2446
circular_queue::increment
queue_pointer increment(queue_pointer p, difference_type n) const noexcept
increments a pointer
Definition: circular_queue.h:3076
circular_queue::cend
const_iterator cend() const noexcept
Returns constant iterator to end.
Definition: circular_queue.h:1683
circular_queue::front
reference front() noexcept
Access first element.
Definition: circular_queue.h:2026
circular_queue::const_iterator::operator++
const_iterator operator++(int)
Increment iterator position (postfix)
Definition: circular_queue.h:357
circular_queue::end
const_iterator end() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1583
circular_queue::const_queue_pointer
constant pointer with parity
Definition: circular_queue.h:140
circular_queue::iterator::operator&
pointer operator&() const
Dereference operator.
Definition: circular_queue.h:706
circular_queue::begin
iterator begin() noexcept
Returns iterator to beginning.
Definition: circular_queue.h:1552
circular_queue::iterator::operator->
pointer operator->() const
Dereference operator.
Definition: circular_queue.h:721
circular_queue::circular_queue
circular_queue(const circular_queue &other)
Copy Constructor.
Definition: circular_queue.h:1288
circular_queue::iterator::operator<
bool operator<(const iterator &rhs) const noexcept
less-than operator
Definition: circular_queue.h:974
circular_queue::iterator::operator--
iterator operator--(int)
Decrease iterator position (postfix)
Definition: circular_queue.h:884
circular_queue::insert
iterator insert(const_iterator position, InputIterator first, InputIterator last)
Insert (range) elements.
Definition: circular_queue.h:2677
circular_queue::insert
iterator insert(const_iterator position, const value_type &val)
Insert (copy) single element.
Definition: circular_queue.h:2549
circular_queue::clear
void clear() noexcept
Clear content.
Definition: circular_queue.h:2301
circular_queue::const_iterator::operator[]
reference operator[](difference_type n) const
Dereference iterator with offset.
Definition: circular_queue.h:291
circular_queue
Fixed capacity, STL-style, templated circular buffer.
Definition: circular_queue.h:105
circular_queue::circular_queue
circular_queue(size_type capacity, const allocator_type &alloc=allocator_type())
Constructor.
Definition: circular_queue.h:1079
circular_queue::iterator::operator++
iterator & operator++() noexcept
Increment iterator position (prefix)
Definition: circular_queue.h:793
circular_queue::const_iterator::operator+
const_iterator operator+(difference_type n) const noexcept
Addition operator.
Definition: circular_queue.h:397
circular_queue::decrement
const_queue_pointer decrement(const_queue_pointer p, difference_type n, bool &parity) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:3158
circular_queue::iterator::~iterator
~iterator() noexcept=default
destructor. Complexity: Constant. Exception Safety: No-throw guarantee: This function never throws...
circular_queue::at
const_reference at(size_type n) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1999
circular_queue::const_iterator::operator*
reference operator*() const
Dereference operator.
Definition: circular_queue.h:241
circular_queue::queue_pointer
pointer with parity
Definition: circular_queue.h:130
circular_queue::emplace
iterator emplace(const_iterator position, Args &&... args)
Construct and insert element.
Definition: circular_queue.h:2892
circular_queue::get_allocator
allocator_type get_allocator() const noexcept
Get allocator.
Definition: circular_queue.h:3020
circular_queue::back
reference back()
Access last element.
Definition: circular_queue.h:2054
circular_queue::rend
const_reverse_iterator rend() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1637
circular_queue::rbegin
reverse_iterator rbegin() noexcept
Returns reverse iterator to beginning.
Definition: circular_queue.h:1605
circular_queue::increment
const_queue_pointer increment(const_queue_pointer p, difference_type n) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:3101
circular_queue::swapUpToEnd
iterator swapUpToEnd(const_iterator position, size_type n) noexcept
Moves the given position to the end of the queue by successively swapping it.
Definition: circular_queue.h:3285
circular_queue::swap
void swap(circular_queue &other) noexcept
Swap content.
Definition: circular_queue.h:2840
circular_queue::iterator::operator-
difference_type operator-(const iterator &other) const
subtraction operator
Definition: circular_queue.h:947
circular_queue::circular_queue
circular_queue(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type(), typename std::enable_if<!std::is_integral< InputIterator >::value >::type *=0)
Range Constructor.
Definition: circular_queue.h:1178
circular_queue::const_iterator::operator--
const_iterator operator--(int)
Decrease iterator position (postfix)
Definition: circular_queue.h:434
circular_queue::emplace_front
void emplace_front(Args &&... args)
Construct and insert element at beginning.
Definition: circular_queue.h:2924
circular_queue::iterator::operator-
iterator operator-(difference_type n) const
subtraction operator
Definition: circular_queue.h:925
circular_queue::const_iterator::operator<
bool operator<(const const_iterator &rhs) const noexcept
less-than operator
Definition: circular_queue.h:524
circular_queue::insert
iterator insert(const_iterator position, size_type n, const value_type &val)
Insert (fill) elements.
Definition: circular_queue.h:2628
circular_queue::operator=
circular_queue & operator=(circular_queue &&other) noexcept
Assign content.
Definition: circular_queue.h:1441
circular_queue::assign
void assign(InputIterator first, InputIterator last)
Assign container content range.
Definition: circular_queue.h:2099
circular_queue::const_iterator::operator==
bool operator==(const const_iterator &rhs) const noexcept
equality operator
Definition: circular_queue.h:310
circular_queue::iterator::iterator
iterator(const circular_queue *const buffer, pointer start, bool parity) noexcept
Constructor.
Definition: circular_queue.h:640
circular_queue::pop_back
void pop_back() noexcept
Delete last element.
Definition: circular_queue.h:2492
circular_queue::insert
iterator insert(const_iterator position, std::initializer_list< value_type > il)
Insert elements (initializer_list)
Definition: circular_queue.h:2734
circular_queue::iterator::operator+
iterator operator+(difference_type n) const noexcept
Addition operator.
Definition: circular_queue.h:848
circular_queue::swapDownTo
iterator swapDownTo(const_iterator position, size_type n) noexcept
Swaps the back of the queue down to position with elements n positions away.
Definition: circular_queue.h:3253
circular_queue::m_capacity
size_type m_capacity
capacity of the buffer array.
Definition: circular_queue.h:3313
circular_queue::const_iterator::operator++
const_iterator & operator++() noexcept
Increment iterator position (prefix)
Definition: circular_queue.h:342
circular_queue::iterator::operator*
reference operator*() const
Dereference operator.
Definition: circular_queue.h:691
circular_queue::iterator::operator<=
bool operator<=(const iterator &rhs) const
less-than-or-equal operator
Definition: circular_queue.h:1005
circular_queue::iterator::operator!=
bool operator!=(const iterator &rhs) const
inequality operator Complexity: Constant. Iterator Validity: No changes. Data Races: The contain...
Definition: circular_queue.h:777
circular_queue::operator=
circular_queue & operator=(std::initializer_list< value_type > il)
Assign content.
Definition: circular_queue.h:1486
circular_queue::const_iterator::m_pointer
queue_pointer m_pointer
Iterator position.
Definition: circular_queue.h:597
circular_queue::m_data
pointer m_data
Pointer to the internal data array.
Definition: circular_queue.h:3312
circular_queue::m_alloc
Alloc m_alloc
Allocator class. NOT c-style malloc.
Definition: circular_queue.h:3311
circular_queue::const_iterator::const_iterator
const_iterator(const circular_queue *buffer, pointer start, bool parity) noexcept
Constructor.
Definition: circular_queue.h:189
circular_queue::iterator::operator++
iterator operator++(int)
Increment iterator position (postfix)
Definition: circular_queue.h:808
circular_queue::iterator::operator[]
reference operator[](difference_type n) const
Dereference iterator with offset.
Definition: circular_queue.h:741
circular_queue::full
bool full() const noexcept
Test whether container is full.
Definition: circular_queue.h:1836
circular_queue::rend
reverse_iterator rend() noexcept
Returns reverse iterator to end.
Definition: circular_queue.h:1631
circular_queue::iterator::m_pointer
queue_pointer m_pointer
Iterator position.
Definition: circular_queue.h:1053
circular_queue::cbegin
const_iterator cbegin() const noexcept
Returns constant iterator to beginning.
Definition: circular_queue.h:1660
circular_queue::const_iterator::operator+=
const_iterator & operator+=(difference_type n) noexcept
Advance iterator.
Definition: circular_queue.h:376
circular_queue::capacity
size_type capacity() const noexcept
Get buffer capacity.
Definition: circular_queue.h:1786
circular_queue::const_iterator::operator--
const_iterator & operator--() noexcept
Decrease iterator position (prefix)
Definition: circular_queue.h:418
circular_queue::const_iterator::operator-=
const_iterator & operator-=(difference_type n) noexcept
Retrocede iterator.
Definition: circular_queue.h:454
circular_queue::iterator::operator--
iterator & operator--() noexcept
Decrease iterator position (prefix)
Definition: circular_queue.h:868
circular_queue::assign
void assign(size_type n, const value_type &val)
Assign container content by fill.
Definition: circular_queue.h:2169
circular_queue::at
reference at(size_type n)
Access element.
Definition: circular_queue.h:1988
circular_queue::begin
const_iterator begin() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1558
circular_queue::push_front
void push_front(const value_type &val)
Add element at beginning.
Definition: circular_queue.h:2415
circular_queue::push_back
void push_back(const value_type &val)
Add element at the end.
Definition: circular_queue.h:2336
circular_queue::const_iterator::operator-
const_iterator operator-(difference_type n) const
subtraction operator
Definition: circular_queue.h:475
circular_queue::emplace_back
void emplace_back(Args &&... args)
Construct and insert element at the end.
Definition: circular_queue.h:2972
circular_queue::rbegin
const_reverse_iterator rbegin() const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:1611
circular_queue::resize
void resize(size_type n, const value_type &val=value_type())
Change size.
Definition: circular_queue.h:1904
circular_queue::circular_queue
circular_queue(size_type capacity, const value_type &val, const allocator_type &alloc=allocator_type())
fill constructor
Definition: circular_queue.h:1120
circular_queue::m_head
queue_pointer m_head
Points to the logical beginning of the buffer. No memory ownership!
Definition: circular_queue.h:3314
circular_queue::erase
iterator erase(const_iterator position)
Erase element.
Definition: circular_queue.h:2763
circular_queue::~circular_queue
virtual ~circular_queue()
destructor
Definition: circular_queue.h:1356
circular_queue::circular_queue
circular_queue(circular_queue &&other) noexcept
move constructor
Definition: circular_queue.h:1321
circular_queue::push_back
void push_back(value_type &&val)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:2366
circular_queue::end
iterator end() noexcept
Returns iterator to end.
Definition: circular_queue.h:1577
circular_queue::reserve
void reserve(size_type n)
Request a change in capacity.
Definition: circular_queue.h:1863
circular_queue::back
const_reference back() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: circular_queue.h:2061