libstdc++
stl_queue.h
Go to the documentation of this file.
1 // Queue implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2014 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996,1997
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_queue.h
52  * This is an internal header file, included by other library headers.
53  * Do not attempt to use it directly. @headername{queue}
54  */
55 
56 #ifndef _STL_QUEUE_H
57 #define _STL_QUEUE_H 1
58 
59 #include <bits/concept_check.h>
60 #include <debug/debug.h>
61 #if __cplusplus >= 201103L
62 # include <bits/uses_allocator.h>
63 #endif
64 
65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 
69  /**
70  * @brief A standard container giving FIFO behavior.
71  *
72  * @ingroup sequences
73  *
74  * @tparam _Tp Type of element.
75  * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
76  *
77  * Meets many of the requirements of a
78  * <a href="tables.html#65">container</a>,
79  * but does not define anything to do with iterators. Very few of the
80  * other standard container interfaces are defined.
81  *
82  * This is not a true container, but an @e adaptor. It holds another
83  * container, and provides a wrapper interface to that container. The
84  * wrapper is what enforces strict first-in-first-out %queue behavior.
85  *
86  * The second template parameter defines the type of the underlying
87  * sequence/container. It defaults to std::deque, but it can be any type
88  * that supports @c front, @c back, @c push_back, and @c pop_front,
89  * such as std::list or an appropriate user-defined type.
90  *
91  * Members not found in @a normal containers are @c container_type,
92  * which is a typedef for the second Sequence parameter, and @c push and
93  * @c pop, which are standard %queue/FIFO operations.
94  */
95  template<typename _Tp, typename _Sequence = deque<_Tp> >
96  class queue
97  {
98  // concept requirements
99  typedef typename _Sequence::value_type _Sequence_value_type;
100  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
101  __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
102  __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
103  __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
104 
105  template<typename _Tp1, typename _Seq1>
106  friend bool
107  operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
108 
109  template<typename _Tp1, typename _Seq1>
110  friend bool
111  operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
112 
113  public:
114  typedef typename _Sequence::value_type value_type;
115  typedef typename _Sequence::reference reference;
116  typedef typename _Sequence::const_reference const_reference;
117  typedef typename _Sequence::size_type size_type;
118  typedef _Sequence container_type;
119 
120  protected:
121  /**
122  * 'c' is the underlying container. Maintainers wondering why
123  * this isn't uglified as per style guidelines should note that
124  * this name is specified in the standard, [23.2.3.1]. (Why?
125  * Presumably for the same reason that it's protected instead
126  * of private: to allow derivation. But none of the other
127  * containers allow for derivation. Odd.)
128  */
129  _Sequence c;
130 
131  public:
132  /**
133  * @brief Default constructor creates no elements.
134  */
135 #if __cplusplus < 201103L
136  explicit
137  queue(const _Sequence& __c = _Sequence())
138  : c(__c) { }
139 #else
140  explicit
141  queue(const _Sequence& __c)
142  : c(__c) { }
143 
144  explicit
145  queue(_Sequence&& __c = _Sequence())
146  : c(std::move(__c)) { }
147 #endif
148 
149  /**
150  * Returns true if the %queue is empty.
151  */
152  bool
153  empty() const
154  { return c.empty(); }
155 
156  /** Returns the number of elements in the %queue. */
157  size_type
158  size() const
159  { return c.size(); }
160 
161  /**
162  * Returns a read/write reference to the data at the first
163  * element of the %queue.
164  */
165  reference
167  {
168  __glibcxx_requires_nonempty();
169  return c.front();
170  }
171 
172  /**
173  * Returns a read-only (constant) reference to the data at the first
174  * element of the %queue.
175  */
176  const_reference
177  front() const
178  {
179  __glibcxx_requires_nonempty();
180  return c.front();
181  }
182 
183  /**
184  * Returns a read/write reference to the data at the last
185  * element of the %queue.
186  */
187  reference
189  {
190  __glibcxx_requires_nonempty();
191  return c.back();
192  }
193 
194  /**
195  * Returns a read-only (constant) reference to the data at the last
196  * element of the %queue.
197  */
198  const_reference
199  back() const
200  {
201  __glibcxx_requires_nonempty();
202  return c.back();
203  }
204 
205  /**
206  * @brief Add data to the end of the %queue.
207  * @param __x Data to be added.
208  *
209  * This is a typical %queue operation. The function creates an
210  * element at the end of the %queue and assigns the given data
211  * to it. The time complexity of the operation depends on the
212  * underlying sequence.
213  */
214  void
215  push(const value_type& __x)
216  { c.push_back(__x); }
217 
218 #if __cplusplus >= 201103L
219  void
220  push(value_type&& __x)
221  { c.push_back(std::move(__x)); }
222 
223  template<typename... _Args>
224  void
225  emplace(_Args&&... __args)
226  { c.emplace_back(std::forward<_Args>(__args)...); }
227 #endif
228 
229  /**
230  * @brief Removes first element.
231  *
232  * This is a typical %queue operation. It shrinks the %queue by one.
233  * The time complexity of the operation depends on the underlying
234  * sequence.
235  *
236  * Note that no data is returned, and if the first element's
237  * data is needed, it should be retrieved before pop() is
238  * called.
239  */
240  void
241  pop()
242  {
243  __glibcxx_requires_nonempty();
244  c.pop_front();
245  }
246 
247 #if __cplusplus >= 201103L
248  void
249  swap(queue& __q)
250  noexcept(noexcept(swap(c, __q.c)))
251  {
252  using std::swap;
253  swap(c, __q.c);
254  }
255 #endif
256  };
257 
258  /**
259  * @brief Queue equality comparison.
260  * @param __x A %queue.
261  * @param __y A %queue of the same type as @a __x.
262  * @return True iff the size and elements of the queues are equal.
263  *
264  * This is an equivalence relation. Complexity and semantics depend on the
265  * underlying sequence type, but the expected rules are: this relation is
266  * linear in the size of the sequences, and queues are considered equivalent
267  * if their sequences compare equal.
268  */
269  template<typename _Tp, typename _Seq>
270  inline bool
271  operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
272  { return __x.c == __y.c; }
273 
274  /**
275  * @brief Queue ordering relation.
276  * @param __x A %queue.
277  * @param __y A %queue of the same type as @a x.
278  * @return True iff @a __x is lexicographically less than @a __y.
279  *
280  * This is an total ordering relation. Complexity and semantics
281  * depend on the underlying sequence type, but the expected rules
282  * are: this relation is linear in the size of the sequences, the
283  * elements must be comparable with @c <, and
284  * std::lexicographical_compare() is usually used to make the
285  * determination.
286  */
287  template<typename _Tp, typename _Seq>
288  inline bool
289  operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
290  { return __x.c < __y.c; }
291 
292  /// Based on operator==
293  template<typename _Tp, typename _Seq>
294  inline bool
295  operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
296  { return !(__x == __y); }
297 
298  /// Based on operator<
299  template<typename _Tp, typename _Seq>
300  inline bool
302  { return __y < __x; }
303 
304  /// Based on operator<
305  template<typename _Tp, typename _Seq>
306  inline bool
307  operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
308  { return !(__y < __x); }
309 
310  /// Based on operator<
311  template<typename _Tp, typename _Seq>
312  inline bool
314  { return !(__x < __y); }
315 
316 #if __cplusplus >= 201103L
317  template<typename _Tp, typename _Seq>
318  inline void
319  swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
320  noexcept(noexcept(__x.swap(__y)))
321  { __x.swap(__y); }
322 
323  template<typename _Tp, typename _Seq, typename _Alloc>
324  struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
325  : public uses_allocator<_Seq, _Alloc>::type { };
326 #endif
327 
328  /**
329  * @brief A standard container automatically sorting its contents.
330  *
331  * @ingroup sequences
332  *
333  * @tparam _Tp Type of element.
334  * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
335  * @tparam _Compare Comparison function object type, defaults to
336  * less<_Sequence::value_type>.
337  *
338  * This is not a true container, but an @e adaptor. It holds
339  * another container, and provides a wrapper interface to that
340  * container. The wrapper is what enforces priority-based sorting
341  * and %queue behavior. Very few of the standard container/sequence
342  * interface requirements are met (e.g., iterators).
343  *
344  * The second template parameter defines the type of the underlying
345  * sequence/container. It defaults to std::vector, but it can be
346  * any type that supports @c front(), @c push_back, @c pop_back,
347  * and random-access iterators, such as std::deque or an
348  * appropriate user-defined type.
349  *
350  * The third template parameter supplies the means of making
351  * priority comparisons. It defaults to @c less<value_type> but
352  * can be anything defining a strict weak ordering.
353  *
354  * Members not found in @a normal containers are @c container_type,
355  * which is a typedef for the second Sequence parameter, and @c
356  * push, @c pop, and @c top, which are standard %queue operations.
357  *
358  * @note No equality/comparison operators are provided for
359  * %priority_queue.
360  *
361  * @note Sorting of the elements takes place as they are added to,
362  * and removed from, the %priority_queue using the
363  * %priority_queue's member functions. If you access the elements
364  * by other means, and change their data such that the sorting
365  * order would be different, the %priority_queue will not re-sort
366  * the elements for you. (How could it know to do so?)
367  */
368  template<typename _Tp, typename _Sequence = vector<_Tp>,
369  typename _Compare = less<typename _Sequence::value_type> >
371  {
372  // concept requirements
373  typedef typename _Sequence::value_type _Sequence_value_type;
374  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
375  __glibcxx_class_requires(_Sequence, _SequenceConcept)
376  __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
377  __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
378  __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
379  _BinaryFunctionConcept)
380 
381  public:
382  typedef typename _Sequence::value_type value_type;
383  typedef typename _Sequence::reference reference;
384  typedef typename _Sequence::const_reference const_reference;
385  typedef typename _Sequence::size_type size_type;
386  typedef _Sequence container_type;
387 
388  protected:
389  // See queue::c for notes on these names.
390  _Sequence c;
391  _Compare comp;
392 
393  public:
394  /**
395  * @brief Default constructor creates no elements.
396  */
397 #if __cplusplus < 201103L
398  explicit
399  priority_queue(const _Compare& __x = _Compare(),
400  const _Sequence& __s = _Sequence())
401  : c(__s), comp(__x)
402  { std::make_heap(c.begin(), c.end(), comp); }
403 #else
404  explicit
405  priority_queue(const _Compare& __x,
406  const _Sequence& __s)
407  : c(__s), comp(__x)
408  { std::make_heap(c.begin(), c.end(), comp); }
409 
410  explicit
411  priority_queue(const _Compare& __x = _Compare(),
412  _Sequence&& __s = _Sequence())
413  : c(std::move(__s)), comp(__x)
414  { std::make_heap(c.begin(), c.end(), comp); }
415 #endif
416 
417  /**
418  * @brief Builds a %queue from a range.
419  * @param __first An input iterator.
420  * @param __last An input iterator.
421  * @param __x A comparison functor describing a strict weak ordering.
422  * @param __s An initial sequence with which to start.
423  *
424  * Begins by copying @a __s, inserting a copy of the elements
425  * from @a [first,last) into the copy of @a __s, then ordering
426  * the copy according to @a __x.
427  *
428  * For more information on function objects, see the
429  * documentation on @link functors functor base
430  * classes@endlink.
431  */
432 #if __cplusplus < 201103L
433  template<typename _InputIterator>
434  priority_queue(_InputIterator __first, _InputIterator __last,
435  const _Compare& __x = _Compare(),
436  const _Sequence& __s = _Sequence())
437  : c(__s), comp(__x)
438  {
439  __glibcxx_requires_valid_range(__first, __last);
440  c.insert(c.end(), __first, __last);
441  std::make_heap(c.begin(), c.end(), comp);
442  }
443 #else
444  template<typename _InputIterator>
445  priority_queue(_InputIterator __first, _InputIterator __last,
446  const _Compare& __x,
447  const _Sequence& __s)
448  : c(__s), comp(__x)
449  {
450  __glibcxx_requires_valid_range(__first, __last);
451  c.insert(c.end(), __first, __last);
452  std::make_heap(c.begin(), c.end(), comp);
453  }
454 
455  template<typename _InputIterator>
456  priority_queue(_InputIterator __first, _InputIterator __last,
457  const _Compare& __x = _Compare(),
458  _Sequence&& __s = _Sequence())
459  : c(std::move(__s)), comp(__x)
460  {
461  __glibcxx_requires_valid_range(__first, __last);
462  c.insert(c.end(), __first, __last);
463  std::make_heap(c.begin(), c.end(), comp);
464  }
465 #endif
466 
467  /**
468  * Returns true if the %queue is empty.
469  */
470  bool
471  empty() const
472  { return c.empty(); }
473 
474  /** Returns the number of elements in the %queue. */
475  size_type
476  size() const
477  { return c.size(); }
478 
479  /**
480  * Returns a read-only (constant) reference to the data at the first
481  * element of the %queue.
482  */
483  const_reference
484  top() const
485  {
486  __glibcxx_requires_nonempty();
487  return c.front();
488  }
489 
490  /**
491  * @brief Add data to the %queue.
492  * @param __x Data to be added.
493  *
494  * This is a typical %queue operation.
495  * The time complexity of the operation depends on the underlying
496  * sequence.
497  */
498  void
499  push(const value_type& __x)
500  {
501  c.push_back(__x);
502  std::push_heap(c.begin(), c.end(), comp);
503  }
504 
505 #if __cplusplus >= 201103L
506  void
507  push(value_type&& __x)
508  {
509  c.push_back(std::move(__x));
510  std::push_heap(c.begin(), c.end(), comp);
511  }
512 
513  template<typename... _Args>
514  void
515  emplace(_Args&&... __args)
516  {
517  c.emplace_back(std::forward<_Args>(__args)...);
518  std::push_heap(c.begin(), c.end(), comp);
519  }
520 #endif
521 
522  /**
523  * @brief Removes first element.
524  *
525  * This is a typical %queue operation. It shrinks the %queue
526  * by one. The time complexity of the operation depends on the
527  * underlying sequence.
528  *
529  * Note that no data is returned, and if the first element's
530  * data is needed, it should be retrieved before pop() is
531  * called.
532  */
533  void
534  pop()
535  {
536  __glibcxx_requires_nonempty();
537  std::pop_heap(c.begin(), c.end(), comp);
538  c.pop_back();
539  }
540 
541 #if __cplusplus >= 201103L
542  void
543  swap(priority_queue& __pq)
544  noexcept(noexcept(swap(c, __pq.c)) && noexcept(swap(comp, __pq.comp)))
545  {
546  using std::swap;
547  swap(c, __pq.c);
548  swap(comp, __pq.comp);
549  }
550 #endif
551  };
552 
553  // No equality/comparison operators are provided for priority_queue.
554 
555 #if __cplusplus >= 201103L
556  template<typename _Tp, typename _Sequence, typename _Compare>
557  inline void
558  swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
559  priority_queue<_Tp, _Sequence, _Compare>& __y)
560  noexcept(noexcept(__x.swap(__y)))
561  { __x.swap(__y); }
562 
563  template<typename _Tp, typename _Sequence, typename _Compare,
564  typename _Alloc>
565  struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
566  : public uses_allocator<_Sequence, _Alloc>::type { };
567 #endif
568 
569 _GLIBCXX_END_NAMESPACE_VERSION
570 } // namespace
571 
572 #endif /* _STL_QUEUE_H */
priority_queue(const _Compare &__x, const _Sequence &__s)
Default constructor creates no elements.
Definition: stl_queue.h:405
void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
Definition: stl_heap.h:184
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
A standard container giving FIFO behavior.
Definition: stl_queue.h:96
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x, const _Sequence &__s)
Builds a queue from a range.
Definition: stl_queue.h:445
void push(const value_type &__x)
Add data to the queue.
Definition: stl_queue.h:499
size_type size() const
Definition: stl_queue.h:158
const_reference top() const
Definition: stl_queue.h:484
const_reference front() const
Definition: stl_queue.h:177
void pop()
Removes first element.
Definition: stl_queue.h:534
const_reference back() const
Definition: stl_queue.h:199
void push(const value_type &__x)
Add data to the end of the queue.
Definition: stl_queue.h:215
bool empty() const
Definition: stl_queue.h:471
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
Definition: stl_heap.h:297
ISO C++ entities toplevel namespace is std.
size_type size() const
Definition: stl_queue.h:476
A standard container automatically sorting its contents.
Definition: stl_queue.h:370
void pop()
Removes first element.
Definition: stl_queue.h:241
_Sequence c
Definition: stl_queue.h:129
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
reference back()
Definition: stl_queue.h:188
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
queue(const _Sequence &__c)
Default constructor creates no elements.
Definition: stl_queue.h:141
reference front()
Definition: stl_queue.h:166
bool empty() const
Definition: stl_queue.h:153
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
Definition: stl_heap.h:376