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