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 #ifndef _STL_QUEUE_H
00058 #define _STL_QUEUE_H 1
00059
00060 #include <bits/concept_check.h>
00061 #include <debug/debug.h>
00062
00063 _GLIBCXX_BEGIN_NAMESPACE(std)
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088 template<typename _Tp, typename _Sequence = deque<_Tp> >
00089 class queue
00090 {
00091
00092 typedef typename _Sequence::value_type _Sequence_value_type;
00093 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00094 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00095 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
00096 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00097
00098 template<typename _Tp1, typename _Seq1>
00099 friend bool
00100 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00101
00102 template<typename _Tp1, typename _Seq1>
00103 friend bool
00104 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00105
00106 public:
00107 typedef typename _Sequence::value_type value_type;
00108 typedef typename _Sequence::reference reference;
00109 typedef typename _Sequence::const_reference const_reference;
00110 typedef typename _Sequence::size_type size_type;
00111 typedef _Sequence container_type;
00112
00113 protected:
00114
00115
00116
00117
00118
00119
00120
00121
00122 _Sequence c;
00123
00124 public:
00125
00126
00127
00128 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00129 explicit
00130 queue(const _Sequence& __c = _Sequence())
00131 : c(__c) { }
00132 #else
00133 explicit
00134 queue(const _Sequence& __c)
00135 : c(__c) { }
00136
00137 explicit
00138 queue(_Sequence&& __c = _Sequence())
00139 : c(std::move(__c)) { }
00140
00141 queue(queue&& __q)
00142 : c(std::move(__q.c)) { }
00143
00144 queue&
00145 operator=(queue&& __q)
00146 {
00147 c = std::move(__q.c);
00148 return *this;
00149 }
00150 #endif
00151
00152
00153
00154
00155 bool
00156 empty() const
00157 { return c.empty(); }
00158
00159
00160 size_type
00161 size() const
00162 { return c.size(); }
00163
00164
00165
00166
00167
00168 reference
00169 front()
00170 {
00171 __glibcxx_requires_nonempty();
00172 return c.front();
00173 }
00174
00175
00176
00177
00178
00179 const_reference
00180 front() const
00181 {
00182 __glibcxx_requires_nonempty();
00183 return c.front();
00184 }
00185
00186
00187
00188
00189
00190 reference
00191 back()
00192 {
00193 __glibcxx_requires_nonempty();
00194 return c.back();
00195 }
00196
00197
00198
00199
00200
00201 const_reference
00202 back() const
00203 {
00204 __glibcxx_requires_nonempty();
00205 return c.back();
00206 }
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217 void
00218 push(const value_type& __x)
00219 { c.push_back(__x); }
00220
00221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00222 void
00223 push(value_type&& __x)
00224 { c.push_back(std::move(__x)); }
00225
00226 template<typename... _Args>
00227 void
00228 emplace(_Args&&... __args)
00229 { c.emplace_back(std::forward<_Args>(__args)...); }
00230 #endif
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243 void
00244 pop()
00245 {
00246 __glibcxx_requires_nonempty();
00247 c.pop_front();
00248 }
00249
00250 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00251 void
00252 swap(queue& __q)
00253 { c.swap(__q.c); }
00254 #endif
00255 };
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268 template<typename _Tp, typename _Seq>
00269 inline bool
00270 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00271 { return __x.c == __y.c; }
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286 template<typename _Tp, typename _Seq>
00287 inline bool
00288 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00289 { return __x.c < __y.c; }
00290
00291
00292 template<typename _Tp, typename _Seq>
00293 inline bool
00294 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00295 { return !(__x == __y); }
00296
00297
00298 template<typename _Tp, typename _Seq>
00299 inline bool
00300 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00301 { return __y < __x; }
00302
00303
00304 template<typename _Tp, typename _Seq>
00305 inline bool
00306 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00307 { return !(__y < __x); }
00308
00309
00310 template<typename _Tp, typename _Seq>
00311 inline bool
00312 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00313 { return !(__x < __y); }
00314
00315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00316 template<typename _Tp, typename _Seq>
00317 inline void
00318 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
00319 { __x.swap(__y); }
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
00455 priority_queue(priority_queue&& __pq)
00456 : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
00457
00458 priority_queue&
00459 operator=(priority_queue&& __pq)
00460 {
00461 c = std::move(__pq.c);
00462 comp = std::move(__pq.comp);
00463 return *this;
00464 }
00465 #endif
00466
00467
00468
00469
00470 bool
00471 empty() const
00472 { return c.empty(); }
00473
00474
00475 size_type
00476 size() const
00477 { return c.size(); }
00478
00479
00480
00481
00482
00483 const_reference
00484 top() const
00485 {
00486 __glibcxx_requires_nonempty();
00487 return c.front();
00488 }
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498 void
00499 push(const value_type& __x)
00500 {
00501 c.push_back(__x);
00502 std::push_heap(c.begin(), c.end(), comp);
00503 }
00504
00505 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00506 void
00507 push(value_type&& __x)
00508 {
00509 c.push_back(std::move(__x));
00510 std::push_heap(c.begin(), c.end(), comp);
00511 }
00512
00513 template<typename... _Args>
00514 void
00515 emplace(_Args&&... __args)
00516 {
00517 c.emplace_back(std::forward<_Args>(__args)...);
00518 std::push_heap(c.begin(), c.end(), comp);
00519 }
00520 #endif
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533 void
00534 pop()
00535 {
00536 __glibcxx_requires_nonempty();
00537 std::pop_heap(c.begin(), c.end(), comp);
00538 c.pop_back();
00539 }
00540
00541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00542 void
00543 swap(priority_queue& __pq)
00544 {
00545 using std::swap;
00546 c.swap(__pq.c);
00547 swap(comp, __pq.comp);
00548 }
00549 #endif
00550 };
00551
00552
00553
00554 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00555 template<typename _Tp, typename _Sequence, typename _Compare>
00556 inline void
00557 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00558 priority_queue<_Tp, _Sequence, _Compare>& __y)
00559 { __x.swap(__y); }
00560 #endif
00561
00562 _GLIBCXX_END_NAMESPACE
00563
00564 #endif