libstdc++-v3/include/bits/stl_queue.h

   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 _GLIBCXX_BEGIN_NAMESPACE(std)
  65
  66   /**
  67    *  @brief  A standard container giving FIFO behavior.
  68    *
  69    *  @ingroup sequences
  70    *
  71    *  Meets many of the requirements of a
  72    *  <a href="tables.html#65">container</a>,
  73    *  but does not define anything to do with iterators.  Very few of the
  74    *  other standard container interfaces are defined.
  75    *
  76    *  This is not a true container, but an @e adaptor.  It holds another
  77    *  container, and provides a wrapper interface to that container.  The
  78    *  wrapper is what enforces strict first-in-first-out %queue behavior.
  79    *
  80    *  The second template parameter defines the type of the underlying
  81    *  sequence/container.  It defaults to std::deque, but it can be any type
  82    *  that supports @c front, @c back, @c push_back, and @c pop_front,
  83    *  such as std::list or an appropriate user-defined type.
  84    *
  85    *  Members not found in @a normal containers are @c container_type,
  86    *  which is a typedef for the second Sequence parameter, and @c push and
  87    *  @c pop, which are standard %queue/FIFO operations.
  88   */
  89   template<typename _Tp, typename _Sequence = deque<_Tp> >
  90     class queue
  91     {
  92       // concept requirements
  93       typedef typename _Sequence::value_type _Sequence_value_type;
  94       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
  95       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
  96       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
  97       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
  98
  99       template<typename _Tp1, typename _Seq1>
 100         friend bool
 101         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 102
 103       template<typename _Tp1, typename _Seq1>
 104         friend bool
 105         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 106
 107     public:
 108       typedef typename _Sequence::value_type                value_type;
 109       typedef typename _Sequence::reference                 reference;
 110       typedef typename _Sequence::const_reference           const_reference;
 111       typedef typename _Sequence::size_type                 size_type;
 112       typedef          _Sequence                            container_type;
 113
 114     protected:
 115       /**
 116        *  'c' is the underlying container.  Maintainers wondering why
 117        *  this isn't uglified as per style guidelines should note that
 118        *  this name is specified in the standard, [23.2.3.1].  (Why?
 119        *  Presumably for the same reason that it's protected instead
 120        *  of private: to allow derivation.  But none of the other
 121        *  containers allow for derivation.  Odd.)
 122        */
 123       _Sequence c;
 124
 125     public:
 126       /**
 127        *  @brief  Default constructor creates no elements.
 128        */
 129 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 130       explicit
 131       queue(const _Sequence& __c = _Sequence())
 132       : c(__c) { }
 133 #else
 134       explicit
 135       queue(const _Sequence& __c)
 136       : c(__c) { }
 137
 138       explicit
 139       queue(_Sequence&& __c = _Sequence())
 140       : c(std::move(__c)) { }
 141 #endif
 142
 143       /**
 144        *  Returns true if the %queue is empty.
 145        */
 146       bool
 147       empty() const
 148       { return c.empty(); }
 149
 150       /**  Returns the number of elements in the %queue.  */
 151       size_type
 152       size() const
 153       { return c.size(); }
 154
 155       /**
 156        *  Returns a read/write reference to the data at the first
 157        *  element of the %queue.
 158        */
 159       reference
 160       front()
 161       {
 162         __glibcxx_requires_nonempty();
 163         return c.front();
 164       }
 165
 166       /**
 167        *  Returns a read-only (constant) reference to the data at the first
 168        *  element of the %queue.
 169        */
 170       const_reference
 171       front() const
 172       {
 173         __glibcxx_requires_nonempty();
 174         return c.front();
 175       }
 176
 177       /**
 178        *  Returns a read/write reference to the data at the last
 179        *  element of the %queue.
 180        */
 181       reference
 182       back()
 183       {
 184         __glibcxx_requires_nonempty();
 185         return c.back();
 186       }
 187
 188       /**
 189        *  Returns a read-only (constant) reference to the data at the last
 190        *  element of the %queue.
 191        */
 192       const_reference
 193       back() const
 194       {
 195         __glibcxx_requires_nonempty();
 196         return c.back();
 197       }
 198
 199       /**
 200        *  @brief  Add data to the end of the %queue.
 201        *  @param  x  Data to be added.
 202        *
 203        *  This is a typical %queue operation.  The function creates an
 204        *  element at the end of the %queue and assigns the given data
 205        *  to it.  The time complexity of the operation depends on the
 206        *  underlying sequence.
 207        */
 208       void
 209       push(const value_type& __x)
 210       { c.push_back(__x); }
 211
 212 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 213       void
 214       push(value_type&& __x)
 215       { c.push_back(std::move(__x)); }
 216
 217       template<typename... _Args>
 218         void
 219         emplace(_Args&&... __args)
 220         { c.emplace_back(std::forward<_Args>(__args)...); }
 221 #endif
 222
 223       /**
 224        *  @brief  Removes first element.
 225        *
 226        *  This is a typical %queue operation.  It shrinks the %queue by one.
 227        *  The time complexity of the operation depends on the underlying
 228        *  sequence.
 229        *
 230        *  Note that no data is returned, and if the first element's
 231        *  data is needed, it should be retrieved before pop() is
 232        *  called.
 233        */
 234       void
 235       pop()
 236       {
 237         __glibcxx_requires_nonempty();
 238         c.pop_front();
 239       }
 240
 241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 242       void
 243       swap(queue& __q)
 244       {
 245         using std::swap;
 246         swap(c, __q.c);
 247       }
 248 #endif
 249     };
 250
 251   /**
 252    *  @brief  Queue equality comparison.
 253    *  @param  x  A %queue.
 254    *  @param  y  A %queue of the same type as @a x.
 255    *  @return  True iff the size and elements of the queues are equal.
 256    *
 257    *  This is an equivalence relation.  Complexity and semantics depend on the
 258    *  underlying sequence type, but the expected rules are:  this relation is
 259    *  linear in the size of the sequences, and queues are considered equivalent
 260    *  if their sequences compare equal.
 261   */
 262   template<typename _Tp, typename _Seq>
 263     inline bool
 264     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 265     { return __x.c == __y.c; }
 266
 267   /**
 268    *  @brief  Queue ordering relation.
 269    *  @param  x  A %queue.
 270    *  @param  y  A %queue of the same type as @a x.
 271    *  @return  True iff @a x is lexicographically less than @a y.
 272    *
 273    *  This is an total ordering relation.  Complexity and semantics
 274    *  depend on the underlying sequence type, but the expected rules
 275    *  are: this relation is linear in the size of the sequences, the
 276    *  elements must be comparable with @c <, and
 277    *  std::lexicographical_compare() is usually used to make the
 278    *  determination.
 279   */
 280   template<typename _Tp, typename _Seq>
 281     inline bool
 282     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 283     { return __x.c < __y.c; }
 284
 285   /// Based on operator==
 286   template<typename _Tp, typename _Seq>
 287     inline bool
 288     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 289     { return !(__x == __y); }
 290
 291   /// Based on operator<
 292   template<typename _Tp, typename _Seq>
 293     inline bool
 294     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 295     { return __y < __x; }
 296
 297   /// Based on operator<
 298   template<typename _Tp, typename _Seq>
 299     inline bool
 300     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 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 !(__x < __y); }
 308
 309 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 310   template<typename _Tp, typename _Seq>
 311     inline void
 312     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
 313     { __x.swap(__y); }
 314
 315   template<typename _Tp, typename _Seq, typename _Alloc>
 316     struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
 317     : public uses_allocator<_Seq, _Alloc>::type { };
 318 #endif
 319
 320   /**
 321    *  @brief  A standard container automatically sorting its contents.
 322    *
 323    *  @ingroup sequences
 324    *
 325    *  This is not a true container, but an @e adaptor.  It holds
 326    *  another container, and provides a wrapper interface to that
 327    *  container.  The wrapper is what enforces priority-based sorting
 328    *  and %queue behavior.  Very few of the standard container/sequence
 329    *  interface requirements are met (e.g., iterators).
 330    *
 331    *  The second template parameter defines the type of the underlying
 332    *  sequence/container.  It defaults to std::vector, but it can be
 333    *  any type that supports @c front(), @c push_back, @c pop_back,
 334    *  and random-access iterators, such as std::deque or an
 335    *  appropriate user-defined type.
 336    *
 337    *  The third template parameter supplies the means of making
 338    *  priority comparisons.  It defaults to @c less<value_type> but
 339    *  can be anything defining a strict weak ordering.
 340    *
 341    *  Members not found in @a normal containers are @c container_type,
 342    *  which is a typedef for the second Sequence parameter, and @c
 343    *  push, @c pop, and @c top, which are standard %queue operations.
 344    *
 345    *  @note No equality/comparison operators are provided for
 346    *  %priority_queue.
 347    *
 348    *  @note Sorting of the elements takes place as they are added to,
 349    *  and removed from, the %priority_queue using the
 350    *  %priority_queue's member functions.  If you access the elements
 351    *  by other means, and change their data such that the sorting
 352    *  order would be different, the %priority_queue will not re-sort
 353    *  the elements for you.  (How could it know to do so?)
 354   */
 355   template<typename _Tp, typename _Sequence = vector<_Tp>,
 356            typename _Compare  = less<typename _Sequence::value_type> >
 357     class priority_queue
 358     {
 359       // concept requirements
 360       typedef typename _Sequence::value_type _Sequence_value_type;
 361       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 362       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 363       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 364       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 365       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 366                                 _BinaryFunctionConcept)
 367
 368     public:
 369       typedef typename _Sequence::value_type                value_type;
 370       typedef typename _Sequence::reference                 reference;
 371       typedef typename _Sequence::const_reference           const_reference;
 372       typedef typename _Sequence::size_type                 size_type;
 373       typedef          _Sequence                            container_type;
 374
 375     protected:
 376       //  See queue::c for notes on these names.
 377       _Sequence  c;
 378       _Compare   comp;
 379
 380     public:
 381       /**
 382        *  @brief  Default constructor creates no elements.
 383        */
 384 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 385       explicit
 386       priority_queue(const _Compare& __x = _Compare(),
 387                      const _Sequence& __s = _Sequence())
 388       : c(__s), comp(__x)
 389       { std::make_heap(c.begin(), c.end(), comp); }
 390 #else
 391       explicit
 392       priority_queue(const _Compare& __x,
 393                      const _Sequence& __s)
 394       : c(__s), comp(__x)
 395       { std::make_heap(c.begin(), c.end(), comp); }
 396
 397       explicit
 398       priority_queue(const _Compare& __x = _Compare(),
 399                      _Sequence&& __s = _Sequence())
 400       : c(std::move(__s)), comp(__x)
 401       { std::make_heap(c.begin(), c.end(), comp); }
 402 #endif
 403
 404       /**
 405        *  @brief  Builds a %queue from a range.
 406        *  @param  first  An input iterator.
 407        *  @param  last  An input iterator.
 408        *  @param  x  A comparison functor describing a strict weak ordering.
 409        *  @param  s  An initial sequence with which to start.
 410        *
 411        *  Begins by copying @a s, inserting a copy of the elements
 412        *  from @a [first,last) into the copy of @a s, then ordering
 413        *  the copy according to @a x.
 414        *
 415        *  For more information on function objects, see the
 416        *  documentation on @link functors functor base
 417        *  classes@endlink.
 418        */
 419 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 420       template<typename _InputIterator>
 421         priority_queue(_InputIterator __first, _InputIterator __last,
 422                        const _Compare& __x = _Compare(),
 423                        const _Sequence& __s = _Sequence())
 424         : c(__s), comp(__x)
 425         {
 426           __glibcxx_requires_valid_range(__first, __last);
 427           c.insert(c.end(), __first, __last);
 428           std::make_heap(c.begin(), c.end(), comp);
 429         }
 430 #else
 431       template<typename _InputIterator>
 432         priority_queue(_InputIterator __first, _InputIterator __last,
 433                        const _Compare& __x,
 434                        const _Sequence& __s)
 435         : c(__s), comp(__x)
 436         {
 437           __glibcxx_requires_valid_range(__first, __last);
 438           c.insert(c.end(), __first, __last);
 439           std::make_heap(c.begin(), c.end(), comp);
 440         }
 441
 442       template<typename _InputIterator>
 443         priority_queue(_InputIterator __first, _InputIterator __last,
 444                        const _Compare& __x = _Compare(),
 445                        _Sequence&& __s = _Sequence())
 446         : c(std::move(__s)), comp(__x)
 447         {
 448           __glibcxx_requires_valid_range(__first, __last);
 449           c.insert(c.end(), __first, __last);
 450           std::make_heap(c.begin(), c.end(), comp);
 451         }
 452 #endif
 453
 454       /**
 455        *  Returns true if the %queue is empty.
 456        */
 457       bool
 458       empty() const
 459       { return c.empty(); }
 460
 461       /**  Returns the number of elements in the %queue.  */
 462       size_type
 463       size() const
 464       { return c.size(); }
 465
 466       /**
 467        *  Returns a read-only (constant) reference to the data at the first
 468        *  element of the %queue.
 469        */
 470       const_reference
 471       top() const
 472       {
 473         __glibcxx_requires_nonempty();
 474         return c.front();
 475       }
 476
 477       /**
 478        *  @brief  Add data to the %queue.
 479        *  @param  x  Data to be added.
 480        *
 481        *  This is a typical %queue operation.
 482        *  The time complexity of the operation depends on the underlying
 483        *  sequence.
 484        */
 485       void
 486       push(const value_type& __x)
 487       {
 488         c.push_back(__x);
 489         std::push_heap(c.begin(), c.end(), comp);
 490       }
 491
 492 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 493       void
 494       push(value_type&& __x)
 495       {
 496         c.push_back(std::move(__x));
 497         std::push_heap(c.begin(), c.end(), comp);
 498       }
 499
 500       template<typename... _Args>
 501         void
 502         emplace(_Args&&... __args)
 503         {
 504           c.emplace_back(std::forward<_Args>(__args)...);
 505           std::push_heap(c.begin(), c.end(), comp);
 506         }
 507 #endif
 508
 509       /**
 510        *  @brief  Removes first element.
 511        *
 512        *  This is a typical %queue operation.  It shrinks the %queue
 513        *  by one.  The time complexity of the operation depends on the
 514        *  underlying sequence.
 515        *
 516        *  Note that no data is returned, and if the first element's
 517        *  data is needed, it should be retrieved before pop() is
 518        *  called.
 519        */
 520       void
 521       pop()
 522       {
 523         __glibcxx_requires_nonempty();
 524         std::pop_heap(c.begin(), c.end(), comp);
 525         c.pop_back();
 526       }
 527
 528 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 529       void
 530       swap(priority_queue& __pq)
 531       {
 532         using std::swap;
 533         swap(c, __pq.c);
 534         swap(comp, __pq.comp);
 535       }
 536 #endif
 537     };
 538
 539   // No equality/comparison operators are provided for priority_queue.
 540
 541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 542   template<typename _Tp, typename _Sequence, typename _Compare>
 543     inline void
 544     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
 545          priority_queue<_Tp, _Sequence, _Compare>& __y)
 546     { __x.swap(__y); }
 547
 548   template<typename _Tp, typename _Sequence, typename _Compare,
 549            typename _Alloc>
 550     struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
 551     : public uses_allocator<_Sequence, _Alloc>::type { };
 552 #endif
 553
 554 _GLIBCXX_END_NAMESPACE
 555
 556 #endif /* _STL_QUEUE_H */