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 _VECTOR_H
00063 #define _VECTOR_H 1
00064
00065 #include <bits/stl_iterator_base_funcs.h>
00066 #include <bits/functexcept.h>
00067 #include <bits/concept_check.h>
00068
00069 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
00070
00071
00072
00073
00074
00075
00076 template<typename _Tp, typename _Alloc>
00077 struct _Vector_base
00078 {
00079 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00080
00081 struct _Vector_impl
00082 : public _Tp_alloc_type
00083 {
00084 _Tp* _M_start;
00085 _Tp* _M_finish;
00086 _Tp* _M_end_of_storage;
00087 _Vector_impl(_Tp_alloc_type const& __a)
00088 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00089 { }
00090 };
00091
00092 public:
00093 typedef _Alloc allocator_type;
00094
00095 _Tp_alloc_type&
00096 _M_get_Tp_allocator()
00097 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00098
00099 const _Tp_alloc_type&
00100 _M_get_Tp_allocator() const
00101 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00102
00103 allocator_type
00104 get_allocator() const
00105 { return allocator_type(_M_get_Tp_allocator()); }
00106
00107 _Vector_base(const allocator_type& __a)
00108 : _M_impl(__a)
00109 { }
00110
00111 _Vector_base(size_t __n, const allocator_type& __a)
00112 : _M_impl(__a)
00113 {
00114 this->_M_impl._M_start = this->_M_allocate(__n);
00115 this->_M_impl._M_finish = this->_M_impl._M_start;
00116 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00117 }
00118
00119 ~_Vector_base()
00120 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
00121 - this->_M_impl._M_start); }
00122
00123 public:
00124 _Vector_impl _M_impl;
00125
00126 _Tp*
00127 _M_allocate(size_t __n)
00128 { return _M_impl.allocate(__n); }
00129
00130 void
00131 _M_deallocate(_Tp* __p, size_t __n)
00132 {
00133 if (__p)
00134 _M_impl.deallocate(__p, __n);
00135 }
00136 };
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00159 class vector : protected _Vector_base<_Tp, _Alloc>
00160 {
00161
00162 typedef typename _Alloc::value_type _Alloc_value_type;
00163 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00164 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00165
00166 typedef _Vector_base<_Tp, _Alloc> _Base;
00167 typedef vector<_Tp, _Alloc> vector_type;
00168 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
00169
00170 public:
00171 typedef _Tp value_type;
00172 typedef typename _Tp_alloc_type::pointer pointer;
00173 typedef typename _Tp_alloc_type::const_pointer const_pointer;
00174 typedef typename _Tp_alloc_type::reference reference;
00175 typedef typename _Tp_alloc_type::const_reference const_reference;
00176 typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
00177 typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
00178 const_iterator;
00179 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00180 typedef std::reverse_iterator<iterator> reverse_iterator;
00181 typedef size_t size_type;
00182 typedef ptrdiff_t difference_type;
00183 typedef _Alloc allocator_type;
00184
00185 protected:
00186 using _Base::_M_allocate;
00187 using _Base::_M_deallocate;
00188 using _Base::_M_impl;
00189 using _Base::_M_get_Tp_allocator;
00190
00191 public:
00192
00193
00194
00195
00196
00197 explicit
00198 vector(const allocator_type& __a = allocator_type())
00199 : _Base(__a)
00200 { }
00201
00202
00203
00204
00205
00206
00207
00208
00209 explicit
00210 vector(size_type __n, const value_type& __value = value_type(),
00211 const allocator_type& __a = allocator_type())
00212 : _Base(__n, __a)
00213 {
00214 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
00215 _M_get_Tp_allocator());
00216 this->_M_impl._M_finish = this->_M_impl._M_start + __n;
00217 }
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228 vector(const vector& __x)
00229 : _Base(__x.size(), __x._M_get_Tp_allocator())
00230 { this->_M_impl._M_finish =
00231 std::__uninitialized_copy_a(__x.begin(), __x.end(),
00232 this->_M_impl._M_start,
00233 _M_get_Tp_allocator());
00234 }
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251 template<typename _InputIterator>
00252 vector(_InputIterator __first, _InputIterator __last,
00253 const allocator_type& __a = allocator_type())
00254 : _Base(__a)
00255 {
00256
00257 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00258 _M_initialize_dispatch(__first, __last, _Integral());
00259 }
00260
00261
00262
00263
00264
00265
00266
00267 ~vector()
00268 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00269 _M_get_Tp_allocator()); }
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279 vector&
00280 operator=(const vector& __x);
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292 void
00293 assign(size_type __n, const value_type& __val)
00294 { _M_fill_assign(__n, __val); }
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308 template<typename _InputIterator>
00309 void
00310 assign(_InputIterator __first, _InputIterator __last)
00311 {
00312
00313 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00314 _M_assign_dispatch(__first, __last, _Integral());
00315 }
00316
00317
00318 using _Base::get_allocator;
00319
00320
00321
00322
00323
00324
00325
00326 iterator
00327 begin()
00328 { return iterator(this->_M_impl._M_start); }
00329
00330
00331
00332
00333
00334
00335 const_iterator
00336 begin() const
00337 { return const_iterator(this->_M_impl._M_start); }
00338
00339
00340
00341
00342
00343
00344 iterator
00345 end()
00346 { return iterator(this->_M_impl._M_finish); }
00347
00348
00349
00350
00351
00352
00353 const_iterator
00354 end() const
00355 { return const_iterator(this->_M_impl._M_finish); }
00356
00357
00358
00359
00360
00361
00362 reverse_iterator
00363 rbegin()
00364 { return reverse_iterator(end()); }
00365
00366
00367
00368
00369
00370
00371 const_reverse_iterator
00372 rbegin() const
00373 { return const_reverse_iterator(end()); }
00374
00375
00376
00377
00378
00379
00380 reverse_iterator
00381 rend()
00382 { return reverse_iterator(begin()); }
00383
00384
00385
00386
00387
00388
00389 const_reverse_iterator
00390 rend() const
00391 { return const_reverse_iterator(begin()); }
00392
00393
00394
00395 size_type
00396 size() const
00397 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
00398
00399
00400 size_type
00401 max_size() const
00402 { return _M_get_Tp_allocator().max_size(); }
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415 void
00416 resize(size_type __new_size, value_type __x = value_type())
00417 {
00418 if (__new_size < size())
00419 _M_erase_at_end(this->_M_impl._M_start + __new_size);
00420 else
00421 insert(end(), __new_size - size(), __x);
00422 }
00423
00424
00425
00426
00427
00428 size_type
00429 capacity() const
00430 { return size_type(this->_M_impl._M_end_of_storage
00431 - this->_M_impl._M_start); }
00432
00433
00434
00435
00436
00437 bool
00438 empty() const
00439 { return begin() == end(); }
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458 void
00459 reserve(size_type __n);
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473 reference
00474 operator[](size_type __n)
00475 { return *(this->_M_impl._M_start + __n); }
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488 const_reference
00489 operator[](size_type __n) const
00490 { return *(this->_M_impl._M_start + __n); }
00491
00492 protected:
00493
00494 void
00495 _M_range_check(size_type __n) const
00496 {
00497 if (__n >= this->size())
00498 __throw_out_of_range(__N("vector::_M_range_check"));
00499 }
00500
00501 public:
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513 reference
00514 at(size_type __n)
00515 {
00516 _M_range_check(__n);
00517 return (*this)[__n];
00518 }
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531 const_reference
00532 at(size_type __n) const
00533 {
00534 _M_range_check(__n);
00535 return (*this)[__n];
00536 }
00537
00538
00539
00540
00541
00542 reference
00543 front()
00544 { return *begin(); }
00545
00546
00547
00548
00549
00550 const_reference
00551 front() const
00552 { return *begin(); }
00553
00554
00555
00556
00557
00558 reference
00559 back()
00560 { return *(end() - 1); }
00561
00562
00563
00564
00565
00566 const_reference
00567 back() const
00568 { return *(end() - 1); }
00569
00570
00571
00572
00573
00574
00575
00576
00577 pointer
00578 data()
00579 { return pointer(this->_M_impl._M_start); }
00580
00581 const_pointer
00582 data() const
00583 { return const_pointer(this->_M_impl._M_start); }
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596 void
00597 push_back(const value_type& __x)
00598 {
00599 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00600 {
00601 this->_M_impl.construct(this->_M_impl._M_finish, __x);
00602 ++this->_M_impl._M_finish;
00603 }
00604 else
00605 _M_insert_aux(end(), __x);
00606 }
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617 void
00618 pop_back()
00619 {
00620 --this->_M_impl._M_finish;
00621 this->_M_impl.destroy(this->_M_impl._M_finish);
00622 }
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635 iterator
00636 insert(iterator __position, const value_type& __x);
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651 void
00652 insert(iterator __position, size_type __n, const value_type& __x)
00653 { _M_fill_insert(__position, __n, __x); }
00654
00655
00656
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668
00669 template<typename _InputIterator>
00670 void
00671 insert(iterator __position, _InputIterator __first,
00672 _InputIterator __last)
00673 {
00674
00675 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00676 _M_insert_dispatch(__position, __first, __last, _Integral());
00677 }
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694 iterator
00695 erase(iterator __position);
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715 iterator
00716 erase(iterator __first, iterator __last);
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727 void
00728 swap(vector& __x)
00729 {
00730 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00731 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00732 std::swap(this->_M_impl._M_end_of_storage,
00733 __x._M_impl._M_end_of_storage);
00734
00735
00736
00737 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
00738 __x._M_get_Tp_allocator());
00739 }
00740
00741
00742
00743
00744
00745
00746
00747 void
00748 clear()
00749 { _M_erase_at_end(this->_M_impl._M_start); }
00750
00751 protected:
00752
00753
00754
00755
00756
00757
00758 template<typename _ForwardIterator>
00759 pointer
00760 _M_allocate_and_copy(size_type __n,
00761 _ForwardIterator __first, _ForwardIterator __last)
00762 {
00763 pointer __result = this->_M_allocate(__n);
00764 try
00765 {
00766 std::__uninitialized_copy_a(__first, __last, __result,
00767 _M_get_Tp_allocator());
00768 return __result;
00769 }
00770 catch(...)
00771 {
00772 _M_deallocate(__result, __n);
00773 __throw_exception_again;
00774 }
00775 }
00776
00777
00778
00779
00780
00781 template<typename _Integer>
00782 void
00783 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
00784 {
00785 this->_M_impl._M_start = _M_allocate(__n);
00786 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00787 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
00788 _M_get_Tp_allocator());
00789 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
00790 }
00791
00792
00793 template<typename _InputIterator>
00794 void
00795 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00796 __false_type)
00797 {
00798 typedef typename std::iterator_traits<_InputIterator>::
00799 iterator_category _IterCategory;
00800 _M_range_initialize(__first, __last, _IterCategory());
00801 }
00802
00803
00804 template<typename _InputIterator>
00805 void
00806 _M_range_initialize(_InputIterator __first,
00807 _InputIterator __last, std::input_iterator_tag)
00808 {
00809 for (; __first != __last; ++__first)
00810 push_back(*__first);
00811 }
00812
00813
00814 template<typename _ForwardIterator>
00815 void
00816 _M_range_initialize(_ForwardIterator __first,
00817 _ForwardIterator __last, std::forward_iterator_tag)
00818 {
00819 const size_type __n = std::distance(__first, __last);
00820 this->_M_impl._M_start = this->_M_allocate(__n);
00821 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00822 this->_M_impl._M_finish =
00823 std::__uninitialized_copy_a(__first, __last,
00824 this->_M_impl._M_start,
00825 _M_get_Tp_allocator());
00826 }
00827
00828
00829
00830
00831
00832
00833 template<typename _Integer>
00834 void
00835 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00836 {
00837 _M_fill_assign(static_cast<size_type>(__n),
00838 static_cast<value_type>(__val));
00839 }
00840
00841
00842 template<typename _InputIterator>
00843 void
00844 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00845 __false_type)
00846 {
00847 typedef typename std::iterator_traits<_InputIterator>::
00848 iterator_category _IterCategory;
00849 _M_assign_aux(__first, __last, _IterCategory());
00850 }
00851
00852
00853 template<typename _InputIterator>
00854 void
00855 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00856 std::input_iterator_tag);
00857
00858
00859 template<typename _ForwardIterator>
00860 void
00861 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00862 std::forward_iterator_tag);
00863
00864
00865
00866 void
00867 _M_fill_assign(size_type __n, const value_type& __val);
00868
00869
00870
00871
00872
00873 template<typename _Integer>
00874 void
00875 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
00876 __true_type)
00877 {
00878 _M_fill_insert(__pos, static_cast<size_type>(__n),
00879 static_cast<value_type>(__val));
00880 }
00881
00882
00883 template<typename _InputIterator>
00884 void
00885 _M_insert_dispatch(iterator __pos, _InputIterator __first,
00886 _InputIterator __last, __false_type)
00887 {
00888 typedef typename std::iterator_traits<_InputIterator>::
00889 iterator_category _IterCategory;
00890 _M_range_insert(__pos, __first, __last, _IterCategory());
00891 }
00892
00893
00894 template<typename _InputIterator>
00895 void
00896 _M_range_insert(iterator __pos, _InputIterator __first,
00897 _InputIterator __last, std::input_iterator_tag);
00898
00899
00900 template<typename _ForwardIterator>
00901 void
00902 _M_range_insert(iterator __pos, _ForwardIterator __first,
00903 _ForwardIterator __last, std::forward_iterator_tag);
00904
00905
00906
00907 void
00908 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
00909
00910
00911 void
00912 _M_insert_aux(iterator __position, const value_type& __x);
00913
00914
00915
00916
00917
00918 void
00919 _M_erase_at_end(pointer __pos)
00920 {
00921 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
00922 this->_M_impl._M_finish = __pos;
00923 }
00924 };
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937 template<typename _Tp, typename _Alloc>
00938 inline bool
00939 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00940 { return (__x.size() == __y.size()
00941 && std::equal(__x.begin(), __x.end(), __y.begin())); }
00942
00943
00944
00945
00946
00947
00948
00949
00950
00951
00952
00953
00954 template<typename _Tp, typename _Alloc>
00955 inline bool
00956 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00957 { return std::lexicographical_compare(__x.begin(), __x.end(),
00958 __y.begin(), __y.end()); }
00959
00960
00961 template<typename _Tp, typename _Alloc>
00962 inline bool
00963 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00964 { return !(__x == __y); }
00965
00966
00967 template<typename _Tp, typename _Alloc>
00968 inline bool
00969 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00970 { return __y < __x; }
00971
00972
00973 template<typename _Tp, typename _Alloc>
00974 inline bool
00975 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00976 { return !(__y < __x); }
00977
00978
00979 template<typename _Tp, typename _Alloc>
00980 inline bool
00981 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
00982 { return !(__x < __y); }
00983
00984
00985 template<typename _Tp, typename _Alloc>
00986 inline void
00987 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
00988 { __x.swap(__y); }
00989
00990 _GLIBCXX_END_NESTED_NAMESPACE
00991
00992 #endif