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

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