00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #ifndef _STL_QUEUE_H
00063 #define _STL_QUEUE_H 1
00064
00065 #include <bits/concept_check.h>
00066 #include <debug/debug.h>
00067
00068 _GLIBCXX_BEGIN_NAMESPACE(std)
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094 template<typename _Tp, typename _Sequence = deque<_Tp> >
00095 class queue
00096 {
00097
00098 typedef typename _Sequence::value_type _Sequence_value_type;
00099 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00100 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00101 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
00102 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00103
00104 template<typename _Tp1, typename _Seq1>
00105 friend bool
00106 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00107
00108 template<typename _Tp1, typename _Seq1>
00109 friend bool
00110 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00111
00112 public:
00113 typedef typename _Sequence::value_type value_type;
00114 typedef typename _Sequence::reference reference;
00115 typedef typename _Sequence::const_reference const_reference;
00116 typedef typename _Sequence::size_type size_type;
00117 typedef _Sequence container_type;
00118
00119 protected:
00120
00121
00122
00123
00124
00125
00126
00127
00128 _Sequence c;
00129
00130 public:
00131
00132
00133
00134 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00135 explicit
00136 queue(const _Sequence& __c = _Sequence())
00137 : c(__c) { }
00138 #else
00139 explicit
00140 queue(const _Sequence& __c)
00141 : c(__c) { }
00142
00143 explicit
00144 queue(_Sequence&& __c = _Sequence())
00145 : c(std::move(__c)) { }
00146
00147 queue(queue&& __q)
00148 : c(std::move(__q.c)) { }
00149
00150 queue&
00151 operator=(queue&& __q)
00152 {
00153 c = std::move(__q.c);
00154 return *this;
00155 }
00156 #endif
00157
00158
00159
00160
00161 bool
00162 empty() const
00163 { return c.empty(); }
00164
00165
00166 size_type
00167 size() const
00168 { return c.size(); }
00169
00170
00171
00172
00173
00174 reference
00175 front()
00176 {
00177 __glibcxx_requires_nonempty();
00178 return c.front();
00179 }
00180
00181
00182
00183
00184
00185 const_reference
00186 front() const
00187 {
00188 __glibcxx_requires_nonempty();
00189 return c.front();
00190 }
00191
00192
00193
00194
00195
00196 reference
00197 back()
00198 {
00199 __glibcxx_requires_nonempty();
00200 return c.back();
00201 }
00202
00203
00204
00205
00206
00207 const_reference
00208 back() const
00209 {
00210 __glibcxx_requires_nonempty();
00211 return c.back();
00212 }
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00224 void
00225 push(const value_type& __x)
00226 { c.push_back(__x); }
00227 #else
00228
00229 template<typename... _Args>
00230 void
00231 push(_Args&&... __args)
00232 { c.push_back(std::forward<_Args>(__args)...); }
00233 #endif
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246 void
00247 pop()
00248 {
00249 __glibcxx_requires_nonempty();
00250 c.pop_front();
00251 }
00252
00253 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00254 void
00255 swap(queue&& __q)
00256 { c.swap(__q.c); }
00257 #endif
00258 };
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271 template<typename _Tp, typename _Seq>
00272 inline bool
00273 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00274 { return __x.c == __y.c; }
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289 template<typename _Tp, typename _Seq>
00290 inline bool
00291 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00292 { return __x.c < __y.c; }
00293
00294
00295 template<typename _Tp, typename _Seq>
00296 inline bool
00297 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00298 { return !(__x == __y); }
00299
00300
00301 template<typename _Tp, typename _Seq>
00302 inline bool
00303 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00304 { return __y < __x; }
00305
00306
00307 template<typename _Tp, typename _Seq>
00308 inline bool
00309 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00310 { return !(__y < __x); }
00311
00312
00313 template<typename _Tp, typename _Seq>
00314 inline bool
00315 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00316 { return !(__x < __y); }
00317
00318 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00319 template<typename _Tp, typename _Seq>
00320 inline void
00321 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
00322 { __x.swap(__y); }
00323
00324 template<typename _Tp, typename _Seq>
00325 inline void
00326 swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
00327 { __x.swap(__y); }
00328
00329 template<typename _Tp, typename _Seq>
00330 inline void
00331 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
00332 { __x.swap(__y); }
00333 #endif
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371 template<typename _Tp, typename _Sequence = vector<_Tp>,
00372 typename _Compare = less<typename _Sequence::value_type> >
00373 class priority_queue
00374 {
00375
00376 typedef typename _Sequence::value_type _Sequence_value_type;
00377 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00378 __glibcxx_class_requires(_Sequence, _SequenceConcept)
00379 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00380 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00381 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
00382 _BinaryFunctionConcept)
00383
00384 public:
00385 typedef typename _Sequence::value_type value_type;
00386 typedef typename _Sequence::reference reference;
00387 typedef typename _Sequence::const_reference const_reference;
00388 typedef typename _Sequence::size_type size_type;
00389 typedef _Sequence container_type;
00390
00391 protected:
00392
00393 _Sequence c;
00394 _Compare comp;
00395
00396 public:
00397
00398
00399
00400 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00401 explicit
00402 priority_queue(const _Compare& __x = _Compare(),
00403 const _Sequence& __s = _Sequence())
00404 : c(__s), comp(__x)
00405 { std::make_heap(c.begin(), c.end(), comp); }
00406 #else
00407 explicit
00408 priority_queue(const _Compare& __x,
00409 const _Sequence& __s)
00410 : c(__s), comp(__x)
00411 { std::make_heap(c.begin(), c.end(), comp); }
00412
00413 explicit
00414 priority_queue(const _Compare& __x = _Compare(),
00415 _Sequence&& __s = _Sequence())
00416 : c(std::move(__s)), comp(__x)
00417 { std::make_heap(c.begin(), c.end(), comp); }
00418 #endif
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00436 template<typename _InputIterator>
00437 priority_queue(_InputIterator __first, _InputIterator __last,
00438 const _Compare& __x = _Compare(),
00439 const _Sequence& __s = _Sequence())
00440 : c(__s), comp(__x)
00441 {
00442 __glibcxx_requires_valid_range(__first, __last);
00443 c.insert(c.end(), __first, __last);
00444 std::make_heap(c.begin(), c.end(), comp);
00445 }
00446 #else
00447 template<typename _InputIterator>
00448 priority_queue(_InputIterator __first, _InputIterator __last,
00449 const _Compare& __x,
00450 const _Sequence& __s)
00451 : c(__s), comp(__x)
00452 {
00453 __glibcxx_requires_valid_range(__first, __last);
00454 c.insert(c.end(), __first, __last);
00455 std::make_heap(c.begin(), c.end(), comp);
00456 }
00457
00458 template<typename _InputIterator>
00459 priority_queue(_InputIterator __first, _InputIterator __last,
00460 const _Compare& __x = _Compare(),
00461 _Sequence&& __s = _Sequence())
00462 : c(std::move(__s)), comp(__x)
00463 {
00464 __glibcxx_requires_valid_range(__first, __last);
00465 c.insert(c.end(), __first, __last);
00466 std::make_heap(c.begin(), c.end(), comp);
00467 }
00468
00469 priority_queue(priority_queue&& __pq)
00470 : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
00471
00472 priority_queue&
00473 operator=(priority_queue&& __pq)
00474 {
00475 c = std::move(__pq.c);
00476 comp = std::move(__pq.comp);
00477 return *this;
00478 }
00479 #endif
00480
00481
00482
00483
00484 bool
00485 empty() const
00486 { return c.empty(); }
00487
00488
00489 size_type
00490 size() const
00491 { return c.size(); }
00492
00493
00494
00495
00496
00497 const_reference
00498 top() const
00499 {
00500 __glibcxx_requires_nonempty();
00501 return c.front();
00502 }
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00513 void
00514 push(const value_type& __x)
00515 {
00516 c.push_back(__x);
00517 std::push_heap(c.begin(), c.end(), comp);
00518 }
00519 #else
00520
00521 template<typename... _Args>
00522 void
00523 push(_Args&&... __args)
00524 {
00525 c.push_back(std::forward<_Args>(__args)...);
00526 std::push_heap(c.begin(), c.end(), comp);
00527 }
00528 #endif
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541 void
00542 pop()
00543 {
00544 __glibcxx_requires_nonempty();
00545 std::pop_heap(c.begin(), c.end(), comp);
00546 c.pop_back();
00547 }
00548
00549 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00550 void
00551 swap(priority_queue&& __pq)
00552 {
00553 using std::swap;
00554 c.swap(__pq.c);
00555 swap(comp, __pq.comp);
00556 }
00557 #endif
00558 };
00559
00560
00561
00562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00563 template<typename _Tp, typename _Sequence, typename _Compare>
00564 inline void
00565 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00566 priority_queue<_Tp, _Sequence, _Compare>& __y)
00567 { __x.swap(__y); }
00568
00569 template<typename _Tp, typename _Sequence, typename _Compare>
00570 inline void
00571 swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
00572 priority_queue<_Tp, _Sequence, _Compare>& __y)
00573 { __x.swap(__y); }
00574
00575 template<typename _Tp, typename _Sequence, typename _Compare>
00576 inline void
00577 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00578 priority_queue<_Tp, _Sequence, _Compare>&& __y)
00579 { __x.swap(__y); }
00580 #endif
00581
00582 _GLIBCXX_END_NAMESPACE
00583
00584 #endif