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
00321 template<typename _Tp, typename _Seq>
00322 inline void
00323 swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
00324 { __x.swap(__y); }
00325
00326 template<typename _Tp, typename _Seq>
00327 inline void
00328 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
00329 { __x.swap(__y); }
00330 #endif
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
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367 template<typename _Tp, typename _Sequence = vector<_Tp>,
00368 typename _Compare = less<typename _Sequence::value_type> >
00369 class priority_queue
00370 {
00371
00372 typedef typename _Sequence::value_type _Sequence_value_type;
00373 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00374 __glibcxx_class_requires(_Sequence, _SequenceConcept)
00375 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00376 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00377 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
00378 _BinaryFunctionConcept)
00379
00380 public:
00381 typedef typename _Sequence::value_type value_type;
00382 typedef typename _Sequence::reference reference;
00383 typedef typename _Sequence::const_reference const_reference;
00384 typedef typename _Sequence::size_type size_type;
00385 typedef _Sequence container_type;
00386
00387 protected:
00388
00389 _Sequence c;
00390 _Compare comp;
00391
00392 public:
00393
00394
00395
00396 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00397 explicit
00398 priority_queue(const _Compare& __x = _Compare(),
00399 const _Sequence& __s = _Sequence())
00400 : c(__s), comp(__x)
00401 { std::make_heap(c.begin(), c.end(), comp); }
00402 #else
00403 explicit
00404 priority_queue(const _Compare& __x,
00405 const _Sequence& __s)
00406 : c(__s), comp(__x)
00407 { std::make_heap(c.begin(), c.end(), comp); }
00408
00409 explicit
00410 priority_queue(const _Compare& __x = _Compare(),
00411 _Sequence&& __s = _Sequence())
00412 : c(std::move(__s)), comp(__x)
00413 { std::make_heap(c.begin(), c.end(), comp); }
00414 #endif
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00432 template<typename _InputIterator>
00433 priority_queue(_InputIterator __first, _InputIterator __last,
00434 const _Compare& __x = _Compare(),
00435 const _Sequence& __s = _Sequence())
00436 : c(__s), comp(__x)
00437 {
00438 __glibcxx_requires_valid_range(__first, __last);
00439 c.insert(c.end(), __first, __last);
00440 std::make_heap(c.begin(), c.end(), comp);
00441 }
00442 #else
00443 template<typename _InputIterator>
00444 priority_queue(_InputIterator __first, _InputIterator __last,
00445 const _Compare& __x,
00446 const _Sequence& __s)
00447 : c(__s), comp(__x)
00448 {
00449 __glibcxx_requires_valid_range(__first, __last);
00450 c.insert(c.end(), __first, __last);
00451 std::make_heap(c.begin(), c.end(), comp);
00452 }
00453
00454 template<typename _InputIterator>
00455 priority_queue(_InputIterator __first, _InputIterator __last,
00456 const _Compare& __x = _Compare(),
00457 _Sequence&& __s = _Sequence())
00458 : c(std::move(__s)), comp(__x)
00459 {
00460 __glibcxx_requires_valid_range(__first, __last);
00461 c.insert(c.end(), __first, __last);
00462 std::make_heap(c.begin(), c.end(), comp);
00463 }
00464
00465 priority_queue(priority_queue&& __pq)
00466 : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
00467
00468 priority_queue&
00469 operator=(priority_queue&& __pq)
00470 {
00471 c = std::move(__pq.c);
00472 comp = std::move(__pq.comp);
00473 return *this;
00474 }
00475 #endif
00476
00477
00478
00479
00480 bool
00481 empty() const
00482 { return c.empty(); }
00483
00484
00485 size_type
00486 size() const
00487 { return c.size(); }
00488
00489
00490
00491
00492
00493 const_reference
00494 top() const
00495 {
00496 __glibcxx_requires_nonempty();
00497 return c.front();
00498 }
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508 void
00509 push(const value_type& __x)
00510 {
00511 c.push_back(__x);
00512 std::push_heap(c.begin(), c.end(), comp);
00513 }
00514
00515 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00516 void
00517 push(value_type&& __x)
00518 {
00519 c.push_back(std::move(__x));
00520 std::push_heap(c.begin(), c.end(), comp);
00521 }
00522
00523 template<typename... _Args>
00524 void
00525 emplace(_Args&&... __args)
00526 {
00527 c.emplace_back(std::forward<_Args>(__args)...);
00528 std::push_heap(c.begin(), c.end(), comp);
00529 }
00530 #endif
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543 void
00544 pop()
00545 {
00546 __glibcxx_requires_nonempty();
00547 std::pop_heap(c.begin(), c.end(), comp);
00548 c.pop_back();
00549 }
00550
00551 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00552 void
00553 swap(priority_queue&& __pq)
00554 {
00555 using std::swap;
00556 c.swap(__pq.c);
00557 swap(comp, __pq.comp);
00558 }
00559 #endif
00560 };
00561
00562
00563
00564 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00565 template<typename _Tp, typename _Sequence, typename _Compare>
00566 inline void
00567 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00568 priority_queue<_Tp, _Sequence, _Compare>& __y)
00569 { __x.swap(__y); }
00570
00571 template<typename _Tp, typename _Sequence, typename _Compare>
00572 inline void
00573 swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
00574 priority_queue<_Tp, _Sequence, _Compare>& __y)
00575 { __x.swap(__y); }
00576
00577 template<typename _Tp, typename _Sequence, typename _Compare>
00578 inline void
00579 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00580 priority_queue<_Tp, _Sequence, _Compare>&& __y)
00581 { __x.swap(__y); }
00582 #endif
00583
00584 _GLIBCXX_END_NAMESPACE
00585
00586 #endif