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