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