STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
deque.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/deque.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <[email protected]>
7  * Copyright (C) 2008, 2009 Andreas Beckmann <[email protected]>
8  * Copyright (C) 2013 Timo Bingmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_CONTAINERS_DEQUE_HEADER
16 #define STXXL_CONTAINERS_DEQUE_HEADER
17 
18 #include <limits>
19 #include <stxxl/vector>
20 
22 
23 template <class ValueType, class VectorType>
24 class deque;
25 
26 template <class DequeType>
28 
29 template <class DequeType>
31 {
32 public:
33  typedef DequeType deque_type;
34  typedef typename deque_type::vector_type vector_type;
35 
36  typedef typename deque_type::value_type value_type;
37  typedef typename deque_type::pointer pointer;
38  typedef typename deque_type::const_pointer const_pointer;
39  typedef typename deque_type::reference reference;
40  typedef typename deque_type::const_reference const_reference;
41  typedef typename deque_type::size_type size_type;
42  typedef typename deque_type::difference_type difference_type;
45 
46  typedef std::random_access_iterator_tag iterator_category;
47 
49  friend class deque<value_type, vector_type>;
50 
51 protected:
53 
56 
58  : m_deque(deque), m_offset(offset)
59  { }
60 
61 public:
62  deque_iterator() : m_deque(NULL), m_offset(0) { }
63 
64  difference_type operator - (const self_type& a) const
65  {
66  size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
67  m_offset : (m_deque->m_vector.size() + m_offset);
68  size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
69  a.m_offset : (m_deque->m_vector.size() + a.m_offset);
70 
71  return SelfAbsOffset - aAbsOffset;
72  }
73 
74  difference_type operator - (const const_iterator& a) const
75  {
76  size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
77  m_offset : (m_deque->m_vector.size() + m_offset);
78  size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
79  a.m_offset : (m_deque->m_vector.size() + a.m_offset);
80 
81  return SelfAbsOffset - aAbsOffset;
82  }
83 
84  self_type operator - (size_type op) const
85  {
86  return self_type(m_deque, (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size());
87  }
88 
89  self_type operator + (size_type op) const
90  {
91  return self_type(m_deque, (m_offset + op) % m_deque->m_vector.size());
92  }
93 
94  self_type& operator -= (size_type op)
95  {
96  m_offset = (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size();
97  return *this;
98  }
99 
101  {
102  m_offset = (m_offset + op) % m_deque->m_vector.size();
103  return *this;
104  }
105 
106  reference operator * ()
107  {
108  return m_deque->m_vector[m_offset];
109  }
110 
111  pointer operator -> ()
112  {
113  return &(m_deque->m_vector[m_offset]);
114  }
115 
116  const_reference operator * () const
117  {
118  return m_deque->m_vector[m_offset];
119  }
120 
121  const_pointer operator -> () const
122  {
123  return &(m_deque->m_vector[m_offset]);
124  }
125 
126  reference operator [] (size_type op)
127  {
128  return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
129  }
130 
131  const_reference operator [] (size_type op) const
132  {
133  return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
134  }
135 
137  {
138  m_offset = (m_offset + 1) % m_deque->m_vector.size();
139  return *this;
140  }
142  {
143  self_type tmp = *this;
144  m_offset = (m_offset + 1) % m_deque->m_vector.size();
145  return tmp;
146  }
148  {
149  m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
150  return *this;
151  }
153  {
154  self_type tmp = *this;
155  m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
156  return tmp;
157  }
158  bool operator == (const self_type& a) const
159  {
160  assert(m_deque == a.m_deque);
161  return m_offset == a.m_offset;
162  }
163  bool operator != (const self_type& a) const
164  {
165  assert(m_deque == a.m_deque);
166  return m_offset != a.m_offset;
167  }
168 
169  bool operator < (const self_type& a) const
170  {
171  assert(m_deque == a.m_deque);
172  return (a - (*this)) > 0;
173  }
174 
175  bool operator > (const self_type& a) const
176  {
177  return a < (*this);
178  }
179 
180  bool operator <= (const self_type& a) const
181  {
182  return !((*this) > a);
183  }
184 
185  bool operator >= (const self_type& a) const
186  {
187  return !((*this) < a);
188  }
189 
190  bool operator == (const const_iterator& a) const
191  {
192  assert(m_deque == a.m_deque);
193  return m_offset == a.m_offset;
194  }
195  bool operator != (const const_iterator& a) const
196  {
197  assert(m_deque == a.m_deque);
198  return m_offset != a.m_offset;
199  }
200 
201  bool operator < (const const_iterator& a) const
202  {
203  assert(m_deque == a.m_deque);
204  return (a - (*this)) > 0;
205  }
206 
207  bool operator > (const const_iterator& a) const
208  {
209  return a < (*this);
210  }
211 
212  bool operator <= (const const_iterator& a) const
213  {
214  return !((*this) > a);
215  }
216 
217  bool operator >= (const const_iterator& a) const
218  {
219  return !((*this) < a);
220  }
221 };
222 
223 template <class DequeType>
224 class const_deque_iterator
225 {
226 public:
227  typedef DequeType deque_type;
228  typedef typename deque_type::vector_type vector_type;
229 
230  typedef typename deque_type::value_type value_type;
231  typedef typename deque_type::const_pointer pointer;
232  typedef typename deque_type::const_pointer const_pointer;
233  typedef typename deque_type::const_reference reference;
234  typedef typename deque_type::const_reference const_reference;
235  typedef typename deque_type::size_type size_type;
236  typedef typename deque_type::difference_type difference_type;
237 
240 
241  typedef std::random_access_iterator_tag iterator_category;
242 
243  friend class deque_iterator<deque_type>;
244  friend class deque<value_type, vector_type>;
245 
246 protected:
248 
251 
253  : m_deque(deque), m_offset(offset)
254  { }
255 
256 public:
257  const_deque_iterator() : m_deque(NULL), m_offset(0) { }
258 
260  : m_deque(it.m_deque), m_offset(it.m_offset)
261  { }
262 
263  difference_type operator - (const self_type& a) const
264  {
265  size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
266  m_offset : (m_deque->m_vector.size() + m_offset);
267  size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
268  a.m_offset : (m_deque->m_vector.size() + a.m_offset);
269 
270  return SelfAbsOffset - aAbsOffset;
271  }
272 
273  difference_type operator - (const iterator& a) const
274  {
275  size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
276  m_offset : (m_deque->m_vector.size() + m_offset);
277  size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
278  a.m_offset : (m_deque->m_vector.size() + a.m_offset);
279 
280  return SelfAbsOffset - aAbsOffset;
281  }
282 
283  self_type operator - (size_type op) const
284  {
285  return self_type(m_deque, (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size());
286  }
287 
288  self_type operator + (size_type op) const
289  {
290  return self_type(m_deque, (m_offset + op) % m_deque->m_vector.size());
291  }
292 
293  self_type& operator -= (size_type op)
294  {
295  m_offset = (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size();
296  return *this;
297  }
298 
300  {
301  m_offset = (m_offset + op) % m_deque->m_vector.size();
302  return *this;
303  }
304 
305  const_reference operator * () const
306  {
307  return m_deque->m_vector[m_offset];
308  }
309 
310  const_pointer operator -> () const
311  {
312  return &(m_deque->m_vector[m_offset]);
313  }
314 
315  const_reference operator [] (size_type op) const
316  {
317  return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
318  }
319 
321  {
322  m_offset = (m_offset + 1) % m_deque->m_vector.size();
323  return *this;
324  }
326  {
327  self_type tmp = *this;
328  m_offset = (m_offset + 1) % m_deque->m_vector.size();
329  return tmp;
330  }
332  {
333  m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
334  return *this;
335  }
337  {
338  self_type tmp = *this;
339  m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
340  return tmp;
341  }
342  bool operator == (const self_type& a) const
343  {
344  assert(m_deque == a.m_deque);
345  return m_offset == a.m_offset;
346  }
347  bool operator != (const self_type& a) const
348  {
349  assert(m_deque == a.m_deque);
350  return m_offset != a.m_offset;
351  }
352 
353  bool operator < (const self_type& a) const
354  {
355  assert(m_deque == a.m_deque);
356  return (a - (*this)) > 0;
357  }
358 
359  bool operator > (const self_type& a) const
360  {
361  return a < (*this);
362  }
363 
364  bool operator <= (const self_type& a) const
365  {
366  return !((*this) > a);
367  }
368 
369  bool operator >= (const self_type& a) const
370  {
371  return !((*this) < a);
372  }
373 
374  bool operator == (const iterator& a) const
375  {
376  assert(m_deque == a.m_deque);
377  return m_offset == a.m_offset;
378  }
379  bool operator != (const iterator& a) const
380  {
381  assert(m_deque == a.m_deque);
382  return m_offset != a.m_offset;
383  }
384 
385  bool operator < (const iterator& a) const
386  {
387  assert(m_deque == a.m_deque);
388  return (a - (*this)) > 0;
389  }
390 
391  bool operator > (const iterator& a) const
392  {
393  return a < (*this);
394  }
395 
396  bool operator <= (const iterator& a) const
397  {
398  return !((*this) > a);
399  }
400 
401  bool operator >= (const iterator& a) const
402  {
403  return !((*this) < a);
404  }
405 };
406 
407 //! \addtogroup stlcont
408 //! \{
409 
410 //! A deque container. \n
411 //! <b> Introduction </b> to deque container: see \ref tutorial_deque tutorial. \n
412 //! <b> Design and Internals </b> of deque container: see \ref design_deque
413 //!
414 //! It is an adaptor of the \c VectorType.
415 //! The implementation wraps the elements around
416 //! the end of the \c VectorType circularly.
417 //! \tparam ValueType type of the contained objects (POD with no references to internal memory)
418 //! \tparam VectorType the type of the underlying vector container,
419 //! the default is \c stxxl::vector<ValueType>
420 template <class ValueType, class VectorType = stxxl::vector<ValueType> >
421 class deque : private noncopyable
422 {
424 
425 public:
426  typedef typename VectorType::size_type size_type;
427  typedef typename VectorType::difference_type difference_type;
428  typedef VectorType vector_type;
429  typedef ValueType value_type;
430  typedef ValueType* pointer;
431  typedef const value_type* const_pointer;
432  typedef ValueType& reference;
433  typedef const ValueType& const_reference;
436  typedef std::reverse_iterator<iterator> reverse_iterator;
437  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
438 
439  friend class deque_iterator<self_type>;
441 
442 private:
444  size_type m_begin, m_end, m_size;
445 
447  {
448  const size_type old_size = m_vector.size();
449  m_vector.resize(2 * old_size);
450  if (m_begin > m_end)
451  { // copy data to the new end of the vector
452  const size_type new_begin = old_size + m_begin;
453  std::copy(m_vector.begin() + m_begin,
454  m_vector.begin() + old_size,
455  m_vector.begin() + new_begin);
456  m_begin = new_begin;
457  }
458  }
459 
460 public:
461  //! \name Constructors/Destructors
462  //! \{
463 
465  : m_vector((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(value_type)),
466  m_begin(0), m_end(0), m_size(0)
467  { }
468 
470  : m_vector(STXXL_MAX<size_type>(STXXL_DEFAULT_BLOCK_SIZE(ValueType) / sizeof(value_type), 2 * n)),
471  m_begin(0), m_end(n), m_size(n)
472  { }
473 
474  ~deque() // empty so far
475  { }
476 
477  //! \}
478 
479  //! \name Iterators
480  //! \{
481 
483  {
484  return iterator(this, m_begin);
485  }
487  {
488  return iterator(this, m_end);
489  }
491  {
492  return const_iterator(this, m_begin);
493  }
495  {
496  return begin();
497  }
499  {
500  return const_iterator(this, m_end);
501  }
503  {
504  return end();
505  }
506 
508  {
509  return reverse_iterator(end());
510  }
512  {
513  return const_reverse_iterator(end());
514  }
516  {
517  return const_reverse_iterator(end());
518  }
520  {
521  return reverse_iterator(begin());
522  }
524  {
525  return const_reverse_iterator(begin());
526  }
528  {
529  return const_reverse_iterator(begin());
530  }
531 
532  //! \}
533 
534  //! \name Capacity
535  //! \{
536 
537  size_type size() const
538  {
539  return m_size;
540  }
541 
543  {
544  return std::numeric_limits<size_type>::max() / 2 - 1;
545  }
546 
547  bool empty() const
548  {
549  return m_size == 0;
550  }
551 
552  //! \}
553 
554  //! \name Operators
555  //! \{
556 
557  reference operator [] (size_type n)
558  {
559  assert(n < size());
560  return m_vector[(m_begin + n) % m_vector.size()];
561  }
562 
563  const_reference operator [] (size_type n) const
564  {
565  assert(n < size());
566  return m_vector[(m_begin + n) % m_vector.size()];
567  }
568 
570  {
571  assert(!empty());
572  return m_vector[m_begin];
573  }
574 
576  {
577  assert(!empty());
578  return m_vector[m_begin];
579  }
580 
582  {
583  assert(!empty());
584  return m_vector[(m_end + m_vector.size() - 1) % m_vector.size()];
585  }
586 
588  {
589  assert(!empty());
590  return m_vector[(m_end + m_vector.size() - 1) % m_vector.size()];
591  }
592 
593  //! \}
594 
595  //! \name Modifiers
596  //! \{
597 
598  void push_front(const value_type& el)
599  {
600  if ((m_begin + m_vector.size() - 1) % m_vector.size() == m_end)
601  {
602  // an overflow will occur: resize the array
603  double_array();
604  }
605 
606  m_begin = (m_begin + m_vector.size() - 1) % m_vector.size();
607  m_vector[m_begin] = el;
608  ++m_size;
609  }
610 
611  void push_back(const value_type& el)
612  {
613  if ((m_end + 1) % m_vector.size() == m_begin)
614  {
615  // an overflow will occur: resize the array
616  double_array();
617  }
618  m_vector[m_end] = el;
619  m_end = (m_end + 1) % m_vector.size();
620  ++m_size;
621  }
622 
623  void pop_front()
624  {
625  assert(!empty());
626  m_begin = (m_begin + 1) % m_vector.size();
627  --m_size;
628  }
629 
630  void pop_back()
631  {
632  assert(!empty());
633  m_end = (m_end + m_vector.size() - 1) % m_vector.size();
634  --m_size;
635  }
636 
637  //! \}
638 
639  //! \name Modifiers
640  //! \{
641 
642  void swap(deque& obj)
643  {
644  std::swap(m_vector, obj.m_vector);
645  std::swap(m_begin, obj.m_begin);
646  std::swap(m_end, obj.m_end);
647  std::swap(m_size, obj.m_size);
648  }
649 
650  void clear()
651  {
652  m_vector.clear();
653  m_vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(value_type));
654  m_begin = 0;
655  m_end = 0;
656  m_size = 0;
657  }
658 
659  //! \}
660 
661  //! \name Capacity
662  //! \{
663 
665  {
666  if (n < size())
667  {
668  do
669  {
670  pop_back();
671  } while (n < size());
672  }
673  else
674  {
675  if (n + 1 > m_vector.size())
676  { // need to resize
677  const size_type old_size = m_vector.size();
678  m_vector.resize(2 * n);
679  if (m_begin > m_end)
680  { // copy data to the new end of the vector
681  const size_type new_begin = m_vector.size() - old_size + m_begin;
682  std::copy(m_vector.begin() + m_begin,
683  m_vector.begin() + old_size,
684  m_vector.begin() + new_begin);
685  m_begin = new_begin;
686  }
687  }
688  m_end = (m_end + n - size()) % m_vector.size();
689  m_size = n;
690  }
691  }
692 
693  //! \}
694 };
695 
696 template <class ValueType, class VectorType>
698 {
699  return std::equal(a.begin(), a.end(), b.begin());
700 }
701 
702 template <class ValueType, class VectorType>
703 bool operator < (const deque<ValueType, VectorType>& a, const deque<ValueType, VectorType>& b)
704 {
705  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
706 }
707 
708 //! \}
709 
711 
712 namespace std {
713 
714 template <typename ValueType, typename VectorType>
717 {
718  a.swap(b);
719 }
720 
721 } // namespace std
722 
723 #endif // !STXXL_CONTAINERS_DEQUE_HEADER
vector_type m_vector
Definition: deque.h:443
deque_type::reference reference
Definition: deque.h:39
deque_type::const_reference const_reference
Definition: deque.h:40
#define STXXL_DEFAULT_BLOCK_SIZE(type)
deque_iterator(deque_type *deque, size_type offset)
Definition: deque.h:57
const_deque_iterator< deque_type > const_iterator
Definition: deque.h:44
VectorType::difference_type difference_type
Definition: deque.h:427
const value_type * const_pointer
Definition: deque.h:431
deque_type * m_deque
Definition: deque.h:54
deque_type::size_type size_type
Definition: deque.h:235
const_deque_iterator(const deque_iterator< deque_type > &it)
Definition: deque.h:259
std::reverse_iterator< iterator > reverse_iterator
Definition: deque.h:436
const_reference front() const
Definition: deque.h:575
const_reference back() const
Definition: deque.h:587
iterator begin()
Definition: deque.h:482
A deque container. Introduction to deque container: see STXXL Deque tutorial. Design and Interna...
Definition: deque.h:24
size_type m_offset
Definition: deque.h:55
const_deque_iterator< self_type > const_iterator
Definition: deque.h:435
size_type size() const
Definition: deque.h:537
ValueType & reference
Definition: deque.h:432
reverse_iterator rbegin()
Definition: deque.h:507
deque_iterator< deque_type > iterator
Definition: deque.h:43
std::random_access_iterator_tag iterator_category
Definition: deque.h:46
deque< ValueType, VectorType > self_type
Definition: deque.h:423
deque(size_type n)
Definition: deque.h:469
deque_type::difference_type difference_type
Definition: deque.h:42
void swap(deque &obj)
Definition: deque.h:642
void clear()
Definition: deque.h:650
const_iterator end() const
Definition: deque.h:498
deque_type::const_pointer const_pointer
Definition: deque.h:38
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
std::random_access_iterator_tag iterator_category
Definition: deque.h:241
reference back()
Definition: deque.h:581
VectorType vector_type
Definition: deque.h:428
const_deque_iterator< deque_type > const_iterator
Definition: deque.h:239
deque_type::vector_type vector_type
Definition: deque.h:228
uint_pair & operator+=(const uint_pair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.h:183
void pop_back()
Definition: deque.h:630
deque_type::difference_type difference_type
Definition: deque.h:236
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.h:198
bool operator<=(const uint_pair &b) const
less-or-equal comparison operator
Definition: uint_types.h:210
bool operator>(const uint_pair &b) const
greater comparison operator
Definition: uint_types.h:216
const_reverse_iterator rbegin() const
Definition: deque.h:511
Container::value_type pop_back(Container &c)
Definition: utils.h:295
size_type max_size() const
Definition: deque.h:542
DequeType deque_type
Definition: deque.h:33
const_iterator begin() const
Definition: deque.h:490
ValueType * pointer
Definition: deque.h:430
bool operator>=(const uint_pair &b) const
greater-or-equal comparison operator
Definition: uint_types.h:222
const Type & STXXL_MAX(const Type &a, const Type &b)
Definition: utils.h:153
bool operator<(const uint_pair &b) const
less-than comparison operator
Definition: uint_types.h:204
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
ValueType value_type
Definition: deque.h:429
uint_pair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.h:173
deque_iterator< self_type > iterator
Definition: deque.h:434
const_deque_iterator(const deque_type *deque, size_type offset)
Definition: deque.h:252
deque_type::value_type value_type
Definition: deque.h:36
deque_iterator< deque_type > iterator
Definition: deque.h:238
VectorType::size_type size_type
Definition: deque.h:426
deque_type::vector_type vector_type
Definition: deque.h:34
void double_array()
Definition: deque.h:446
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.h:241
const_reverse_iterator rend() const
Definition: deque.h:523
deque_type::const_pointer const_pointer
Definition: deque.h:232
deque_iterator< deque_type > self_type
Definition: deque.h:52
deque_type::const_reference const_reference
Definition: deque.h:234
void pop_front()
Definition: deque.h:623
const_iterator cend() const
Definition: deque.h:502
const_deque_iterator< deque_type > self_type
Definition: deque.h:247
reference front()
Definition: deque.h:569
const_reverse_iterator crbegin() const
Definition: deque.h:515
void push_back(const value_type &el)
Definition: deque.h:611
void resize(size_type n)
Definition: deque.h:664
const ValueType & const_reference
Definition: deque.h:433
size_type m_size
Definition: deque.h:444
const_iterator cbegin() const
Definition: deque.h:494
deque_type::const_reference reference
Definition: deque.h:233
bool empty() const
Definition: deque.h:547
reverse_iterator rend()
Definition: deque.h:519
deque_type::const_pointer pointer
Definition: deque.h:231
deque_type::value_type value_type
Definition: deque.h:230
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: deque.h:437
deque_type::pointer pointer
Definition: deque.h:37
deque_type::size_type size_type
Definition: deque.h:41
void push_front(const value_type &el)
Definition: deque.h:598
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
const deque_type * m_deque
Definition: deque.h:249
iterator end()
Definition: deque.h:486
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
const_reverse_iterator crend() const
Definition: deque.h:527