OSDN Git Service

5f71aa5cd007c57af599ae0cee45b56d2276a007
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_vector.h
1 // Vector implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation.  Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose.  It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation.  Silicon Graphics makes no
48  * representations about the suitability of this  software for any
49  * purpose.  It is provided "as is" without express or implied warranty.
50  */
51
52 /** @file bits/stl_vector.h
53  *  This is an internal header file, included by other library headers.
54  *  Do not attempt to use it directly. @headername{vector}
55  */
56
57 #ifndef _STL_VECTOR_H
58 #define _STL_VECTOR_H 1
59
60 #include <bits/stl_iterator_base_funcs.h>
61 #include <bits/functexcept.h>
62 #include <bits/concept_check.h>
63 #include <initializer_list>
64
65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
69   /// See bits/stl_deque.h's _Deque_base for an explanation.
70   template<typename _Tp, typename _Alloc>
71     struct _Vector_base
72     {
73       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
74
75       struct _Vector_impl 
76       : public _Tp_alloc_type
77       {
78         typename _Tp_alloc_type::pointer _M_start;
79         typename _Tp_alloc_type::pointer _M_finish;
80         typename _Tp_alloc_type::pointer _M_end_of_storage;
81
82         _Vector_impl()
83         : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
84         { }
85
86         _Vector_impl(_Tp_alloc_type const& __a)
87         : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
88         { }
89       };
90       
91     public:
92       typedef _Alloc allocator_type;
93
94       _Tp_alloc_type&
95       _M_get_Tp_allocator()
96       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
97
98       const _Tp_alloc_type&
99       _M_get_Tp_allocator() const
100       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
101
102       allocator_type
103       get_allocator() const
104       { return allocator_type(_M_get_Tp_allocator()); }
105
106       _Vector_base()
107       : _M_impl() { }
108
109       _Vector_base(const allocator_type& __a)
110       : _M_impl(__a) { }
111
112       _Vector_base(size_t __n)
113       : _M_impl()
114       {
115         this->_M_impl._M_start = this->_M_allocate(__n);
116         this->_M_impl._M_finish = this->_M_impl._M_start;
117         this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
118       }
119
120       _Vector_base(size_t __n, const allocator_type& __a)
121       : _M_impl(__a)
122       {
123         this->_M_impl._M_start = this->_M_allocate(__n);
124         this->_M_impl._M_finish = this->_M_impl._M_start;
125         this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
126       }
127
128 #ifdef __GXX_EXPERIMENTAL_CXX0X__
129       _Vector_base(_Vector_base&& __x)
130       : _M_impl(__x._M_get_Tp_allocator())
131       {
132         this->_M_impl._M_start = __x._M_impl._M_start;
133         this->_M_impl._M_finish = __x._M_impl._M_finish;
134         this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
135         __x._M_impl._M_start = 0;
136         __x._M_impl._M_finish = 0;
137         __x._M_impl._M_end_of_storage = 0;
138       }
139 #endif
140
141       ~_Vector_base()
142       { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
143                       - this->_M_impl._M_start); }
144
145     public:
146       _Vector_impl _M_impl;
147
148       typename _Tp_alloc_type::pointer
149       _M_allocate(size_t __n)
150       { return __n != 0 ? _M_impl.allocate(__n) : 0; }
151
152       void
153       _M_deallocate(typename _Tp_alloc_type::pointer __p, size_t __n)
154       {
155         if (__p)
156           _M_impl.deallocate(__p, __n);
157       }
158     };
159
160
161   /**
162    *  @brief A standard container which offers fixed time access to
163    *  individual elements in any order.
164    *
165    *  @ingroup sequences
166    *
167    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
168    *  <a href="tables.html#66">reversible container</a>, and a
169    *  <a href="tables.html#67">sequence</a>, including the
170    *  <a href="tables.html#68">optional sequence requirements</a> with the
171    *  %exception of @c push_front and @c pop_front.
172    *
173    *  In some terminology a %vector can be described as a dynamic
174    *  C-style array, it offers fast and efficient access to individual
175    *  elements in any order and saves the user from worrying about
176    *  memory and size allocation.  Subscripting ( @c [] ) access is
177    *  also provided as with C-style arrays.
178   */
179   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
180     class vector : protected _Vector_base<_Tp, _Alloc>
181     {
182       // Concept requirements.
183       typedef typename _Alloc::value_type                _Alloc_value_type;
184       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
185       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
186       
187       typedef _Vector_base<_Tp, _Alloc>                  _Base;
188       typedef typename _Base::_Tp_alloc_type             _Tp_alloc_type;
189
190     public:
191       typedef _Tp                                        value_type;
192       typedef typename _Tp_alloc_type::pointer           pointer;
193       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
194       typedef typename _Tp_alloc_type::reference         reference;
195       typedef typename _Tp_alloc_type::const_reference   const_reference;
196       typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
197       typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
198       const_iterator;
199       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
200       typedef std::reverse_iterator<iterator>            reverse_iterator;
201       typedef size_t                                     size_type;
202       typedef ptrdiff_t                                  difference_type;
203       typedef _Alloc                                     allocator_type;
204
205     protected:
206       using _Base::_M_allocate;
207       using _Base::_M_deallocate;
208       using _Base::_M_impl;
209       using _Base::_M_get_Tp_allocator;
210
211     public:
212       // [23.2.4.1] construct/copy/destroy
213       // (assign() and get_allocator() are also listed in this section)
214       /**
215        *  @brief  Default constructor creates no elements.
216        */
217       vector()
218       : _Base() { }
219
220       /**
221        *  @brief  Creates a %vector with no elements.
222        *  @param  a  An allocator object.
223        */
224       explicit
225       vector(const allocator_type& __a)
226       : _Base(__a) { }
227
228 #ifdef __GXX_EXPERIMENTAL_CXX0X__
229       /**
230        *  @brief  Creates a %vector with default constructed elements.
231        *  @param  n  The number of elements to initially create.
232        *
233        *  This constructor fills the %vector with @a n default
234        *  constructed elements.
235        */
236       explicit
237       vector(size_type __n)
238       : _Base(__n)
239       { _M_default_initialize(__n); }
240
241       /**
242        *  @brief  Creates a %vector with copies of an exemplar element.
243        *  @param  n  The number of elements to initially create.
244        *  @param  value  An element to copy.
245        *  @param  a  An allocator.
246        *
247        *  This constructor fills the %vector with @a n copies of @a value.
248        */
249       vector(size_type __n, const value_type& __value,
250              const allocator_type& __a = allocator_type())
251       : _Base(__n, __a)
252       { _M_fill_initialize(__n, __value); }
253 #else
254       /**
255        *  @brief  Creates a %vector with copies of an exemplar element.
256        *  @param  n  The number of elements to initially create.
257        *  @param  value  An element to copy.
258        *  @param  a  An allocator.
259        *
260        *  This constructor fills the %vector with @a n copies of @a value.
261        */
262       explicit
263       vector(size_type __n, const value_type& __value = value_type(),
264              const allocator_type& __a = allocator_type())
265       : _Base(__n, __a)
266       { _M_fill_initialize(__n, __value); }
267 #endif
268
269       /**
270        *  @brief  %Vector copy constructor.
271        *  @param  x  A %vector of identical element and allocator types.
272        *
273        *  The newly-created %vector uses a copy of the allocation
274        *  object used by @a x.  All the elements of @a x are copied,
275        *  but any extra memory in
276        *  @a x (for fast expansion) will not be copied.
277        */
278       vector(const vector& __x)
279       : _Base(__x.size(), __x._M_get_Tp_allocator())
280       { this->_M_impl._M_finish =
281           std::__uninitialized_copy_a(__x.begin(), __x.end(),
282                                       this->_M_impl._M_start,
283                                       _M_get_Tp_allocator());
284       }
285
286 #ifdef __GXX_EXPERIMENTAL_CXX0X__
287       /**
288        *  @brief  %Vector move constructor.
289        *  @param  x  A %vector of identical element and allocator types.
290        *
291        *  The newly-created %vector contains the exact contents of @a x.
292        *  The contents of @a x are a valid, but unspecified %vector.
293        */
294       vector(vector&& __x)
295       : _Base(std::move(__x)) { }
296
297       /**
298        *  @brief  Builds a %vector from an initializer list.
299        *  @param  l  An initializer_list.
300        *  @param  a  An allocator.
301        *
302        *  Create a %vector consisting of copies of the elements in the
303        *  initializer_list @a l.
304        *
305        *  This will call the element type's copy constructor N times
306        *  (where N is @a l.size()) and do no memory reallocation.
307        */
308       vector(initializer_list<value_type> __l,
309              const allocator_type& __a = allocator_type())
310       : _Base(__a)
311       {
312         _M_range_initialize(__l.begin(), __l.end(),
313                             random_access_iterator_tag());
314       }
315 #endif
316
317       /**
318        *  @brief  Builds a %vector from a range.
319        *  @param  first  An input iterator.
320        *  @param  last  An input iterator.
321        *  @param  a  An allocator.
322        *
323        *  Create a %vector consisting of copies of the elements from
324        *  [first,last).
325        *
326        *  If the iterators are forward, bidirectional, or
327        *  random-access, then this will call the elements' copy
328        *  constructor N times (where N is distance(first,last)) and do
329        *  no memory reallocation.  But if only input iterators are
330        *  used, then this will do at most 2N calls to the copy
331        *  constructor, and logN memory reallocations.
332        */
333       template<typename _InputIterator>
334         vector(_InputIterator __first, _InputIterator __last,
335                const allocator_type& __a = allocator_type())
336         : _Base(__a)
337         {
338           // Check whether it's an integral type.  If so, it's not an iterator.
339           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
340           _M_initialize_dispatch(__first, __last, _Integral());
341         }
342
343       /**
344        *  The dtor only erases the elements, and note that if the
345        *  elements themselves are pointers, the pointed-to memory is
346        *  not touched in any way.  Managing the pointer is the user's
347        *  responsibility.
348        */
349       ~vector()
350       { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
351                       _M_get_Tp_allocator()); }
352
353       /**
354        *  @brief  %Vector assignment operator.
355        *  @param  x  A %vector of identical element and allocator types.
356        *
357        *  All the elements of @a x are copied, but any extra memory in
358        *  @a x (for fast expansion) will not be copied.  Unlike the
359        *  copy constructor, the allocator object is not copied.
360        */
361       vector&
362       operator=(const vector& __x);
363
364 #ifdef __GXX_EXPERIMENTAL_CXX0X__
365       /**
366        *  @brief  %Vector move assignment operator.
367        *  @param  x  A %vector of identical element and allocator types.
368        *
369        *  The contents of @a x are moved into this %vector (without copying).
370        *  @a x is a valid, but unspecified %vector.
371        */
372       vector&
373       operator=(vector&& __x)
374       {
375         // NB: DR 1204.
376         // NB: DR 675.
377         this->clear();
378         this->swap(__x);
379         return *this;
380       }
381
382       /**
383        *  @brief  %Vector list assignment operator.
384        *  @param  l  An initializer_list.
385        *
386        *  This function fills a %vector with copies of the elements in the
387        *  initializer list @a l.
388        *
389        *  Note that the assignment completely changes the %vector and
390        *  that the resulting %vector's size is the same as the number
391        *  of elements assigned.  Old data may be lost.
392        */
393       vector&
394       operator=(initializer_list<value_type> __l)
395       {
396         this->assign(__l.begin(), __l.end());
397         return *this;
398       }
399 #endif
400
401       /**
402        *  @brief  Assigns a given value to a %vector.
403        *  @param  n  Number of elements to be assigned.
404        *  @param  val  Value to be assigned.
405        *
406        *  This function fills a %vector with @a n copies of the given
407        *  value.  Note that the assignment completely changes the
408        *  %vector and that the resulting %vector's size is the same as
409        *  the number of elements assigned.  Old data may be lost.
410        */
411       void
412       assign(size_type __n, const value_type& __val)
413       { _M_fill_assign(__n, __val); }
414
415       /**
416        *  @brief  Assigns a range to a %vector.
417        *  @param  first  An input iterator.
418        *  @param  last   An input iterator.
419        *
420        *  This function fills a %vector with copies of the elements in the
421        *  range [first,last).
422        *
423        *  Note that the assignment completely changes the %vector and
424        *  that the resulting %vector's size is the same as the number
425        *  of elements assigned.  Old data may be lost.
426        */
427       template<typename _InputIterator>
428         void
429         assign(_InputIterator __first, _InputIterator __last)
430         {
431           // Check whether it's an integral type.  If so, it's not an iterator.
432           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
433           _M_assign_dispatch(__first, __last, _Integral());
434         }
435
436 #ifdef __GXX_EXPERIMENTAL_CXX0X__
437       /**
438        *  @brief  Assigns an initializer list to a %vector.
439        *  @param  l  An initializer_list.
440        *
441        *  This function fills a %vector with copies of the elements in the
442        *  initializer list @a l.
443        *
444        *  Note that the assignment completely changes the %vector and
445        *  that the resulting %vector's size is the same as the number
446        *  of elements assigned.  Old data may be lost.
447        */
448       void
449       assign(initializer_list<value_type> __l)
450       { this->assign(__l.begin(), __l.end()); }
451 #endif
452
453       /// Get a copy of the memory allocation object.
454       using _Base::get_allocator;
455
456       // iterators
457       /**
458        *  Returns a read/write iterator that points to the first
459        *  element in the %vector.  Iteration is done in ordinary
460        *  element order.
461        */
462       iterator
463       begin()
464       { return iterator(this->_M_impl._M_start); }
465
466       /**
467        *  Returns a read-only (constant) iterator that points to the
468        *  first element in the %vector.  Iteration is done in ordinary
469        *  element order.
470        */
471       const_iterator
472       begin() const
473       { return const_iterator(this->_M_impl._M_start); }
474
475       /**
476        *  Returns a read/write iterator that points one past the last
477        *  element in the %vector.  Iteration is done in ordinary
478        *  element order.
479        */
480       iterator
481       end()
482       { return iterator(this->_M_impl._M_finish); }
483
484       /**
485        *  Returns a read-only (constant) iterator that points one past
486        *  the last element in the %vector.  Iteration is done in
487        *  ordinary element order.
488        */
489       const_iterator
490       end() const
491       { return const_iterator(this->_M_impl._M_finish); }
492
493       /**
494        *  Returns a read/write reverse iterator that points to the
495        *  last element in the %vector.  Iteration is done in reverse
496        *  element order.
497        */
498       reverse_iterator
499       rbegin()
500       { return reverse_iterator(end()); }
501
502       /**
503        *  Returns a read-only (constant) reverse iterator that points
504        *  to the last element in the %vector.  Iteration is done in
505        *  reverse element order.
506        */
507       const_reverse_iterator
508       rbegin() const
509       { return const_reverse_iterator(end()); }
510
511       /**
512        *  Returns a read/write reverse iterator that points to one
513        *  before the first element in the %vector.  Iteration is done
514        *  in reverse element order.
515        */
516       reverse_iterator
517       rend()
518       { return reverse_iterator(begin()); }
519
520       /**
521        *  Returns a read-only (constant) reverse iterator that points
522        *  to one before the first element in the %vector.  Iteration
523        *  is done in reverse element order.
524        */
525       const_reverse_iterator
526       rend() const
527       { return const_reverse_iterator(begin()); }
528
529 #ifdef __GXX_EXPERIMENTAL_CXX0X__
530       /**
531        *  Returns a read-only (constant) iterator that points to the
532        *  first element in the %vector.  Iteration is done in ordinary
533        *  element order.
534        */
535       const_iterator
536       cbegin() const
537       { return const_iterator(this->_M_impl._M_start); }
538
539       /**
540        *  Returns a read-only (constant) iterator that points one past
541        *  the last element in the %vector.  Iteration is done in
542        *  ordinary element order.
543        */
544       const_iterator
545       cend() const
546       { return const_iterator(this->_M_impl._M_finish); }
547
548       /**
549        *  Returns a read-only (constant) reverse iterator that points
550        *  to the last element in the %vector.  Iteration is done in
551        *  reverse element order.
552        */
553       const_reverse_iterator
554       crbegin() const
555       { return const_reverse_iterator(end()); }
556
557       /**
558        *  Returns a read-only (constant) reverse iterator that points
559        *  to one before the first element in the %vector.  Iteration
560        *  is done in reverse element order.
561        */
562       const_reverse_iterator
563       crend() const
564       { return const_reverse_iterator(begin()); }
565 #endif
566
567       // [23.2.4.2] capacity
568       /**  Returns the number of elements in the %vector.  */
569       size_type
570       size() const
571       { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
572
573       /**  Returns the size() of the largest possible %vector.  */
574       size_type
575       max_size() const
576       { return _M_get_Tp_allocator().max_size(); }
577
578 #ifdef __GXX_EXPERIMENTAL_CXX0X__
579       /**
580        *  @brief  Resizes the %vector to the specified number of elements.
581        *  @param  new_size  Number of elements the %vector should contain.
582        *
583        *  This function will %resize the %vector to the specified
584        *  number of elements.  If the number is smaller than the
585        *  %vector's current size the %vector is truncated, otherwise
586        *  default constructed elements are appended.
587        */
588       void
589       resize(size_type __new_size)
590       {
591         if (__new_size > size())
592           _M_default_append(__new_size - size());
593         else if (__new_size < size())
594           _M_erase_at_end(this->_M_impl._M_start + __new_size);
595       }
596
597       /**
598        *  @brief  Resizes the %vector to the specified number of elements.
599        *  @param  new_size  Number of elements the %vector should contain.
600        *  @param  x  Data with which new elements should be populated.
601        *
602        *  This function will %resize the %vector to the specified
603        *  number of elements.  If the number is smaller than the
604        *  %vector's current size the %vector is truncated, otherwise
605        *  the %vector is extended and new elements are populated with
606        *  given data.
607        */
608       void
609       resize(size_type __new_size, const value_type& __x)
610       {
611         if (__new_size > size())
612           insert(end(), __new_size - size(), __x);
613         else if (__new_size < size())
614           _M_erase_at_end(this->_M_impl._M_start + __new_size);
615       }
616 #else
617       /**
618        *  @brief  Resizes the %vector to the specified number of elements.
619        *  @param  new_size  Number of elements the %vector should contain.
620        *  @param  x  Data with which new elements should be populated.
621        *
622        *  This function will %resize the %vector to the specified
623        *  number of elements.  If the number is smaller than the
624        *  %vector's current size the %vector is truncated, otherwise
625        *  the %vector is extended and new elements are populated with
626        *  given data.
627        */
628       void
629       resize(size_type __new_size, value_type __x = value_type())
630       {
631         if (__new_size > size())
632           insert(end(), __new_size - size(), __x);
633         else if (__new_size < size())
634           _M_erase_at_end(this->_M_impl._M_start + __new_size);
635       }
636 #endif
637
638 #ifdef __GXX_EXPERIMENTAL_CXX0X__
639       /**  A non-binding request to reduce capacity() to size().  */
640       void
641       shrink_to_fit()
642       { std::__shrink_to_fit<vector>::_S_do_it(*this); }
643 #endif
644
645       /**
646        *  Returns the total number of elements that the %vector can
647        *  hold before needing to allocate more memory.
648        */
649       size_type
650       capacity() const
651       { return size_type(this->_M_impl._M_end_of_storage
652                          - this->_M_impl._M_start); }
653
654       /**
655        *  Returns true if the %vector is empty.  (Thus begin() would
656        *  equal end().)
657        */
658       bool
659       empty() const
660       { return begin() == end(); }
661
662       /**
663        *  @brief  Attempt to preallocate enough memory for specified number of
664        *          elements.
665        *  @param  n  Number of elements required.
666        *  @throw  std::length_error  If @a n exceeds @c max_size().
667        *
668        *  This function attempts to reserve enough memory for the
669        *  %vector to hold the specified number of elements.  If the
670        *  number requested is more than max_size(), length_error is
671        *  thrown.
672        *
673        *  The advantage of this function is that if optimal code is a
674        *  necessity and the user can determine the number of elements
675        *  that will be required, the user can reserve the memory in
676        *  %advance, and thus prevent a possible reallocation of memory
677        *  and copying of %vector data.
678        */
679       void
680       reserve(size_type __n);
681
682       // element access
683       /**
684        *  @brief  Subscript access to the data contained in the %vector.
685        *  @param n The index of the element for which data should be
686        *  accessed.
687        *  @return  Read/write reference to data.
688        *
689        *  This operator allows for easy, array-style, data access.
690        *  Note that data access with this operator is unchecked and
691        *  out_of_range lookups are not defined. (For checked lookups
692        *  see at().)
693        */
694       reference
695       operator[](size_type __n)
696       { return *(this->_M_impl._M_start + __n); }
697
698       /**
699        *  @brief  Subscript access to the data contained in the %vector.
700        *  @param n The index of the element for which data should be
701        *  accessed.
702        *  @return  Read-only (constant) reference to data.
703        *
704        *  This operator allows for easy, array-style, data access.
705        *  Note that data access with this operator is unchecked and
706        *  out_of_range lookups are not defined. (For checked lookups
707        *  see at().)
708        */
709       const_reference
710       operator[](size_type __n) const
711       { return *(this->_M_impl._M_start + __n); }
712
713     protected:
714       /// Safety check used only from at().
715       void
716       _M_range_check(size_type __n) const
717       {
718         if (__n >= this->size())
719           __throw_out_of_range(__N("vector::_M_range_check"));
720       }
721
722     public:
723       /**
724        *  @brief  Provides access to the data contained in the %vector.
725        *  @param n The index of the element for which data should be
726        *  accessed.
727        *  @return  Read/write reference to data.
728        *  @throw  std::out_of_range  If @a n is an invalid index.
729        *
730        *  This function provides for safer data access.  The parameter
731        *  is first checked that it is in the range of the vector.  The
732        *  function throws out_of_range if the check fails.
733        */
734       reference
735       at(size_type __n)
736       {
737         _M_range_check(__n);
738         return (*this)[__n]; 
739       }
740
741       /**
742        *  @brief  Provides access to the data contained in the %vector.
743        *  @param n The index of the element for which data should be
744        *  accessed.
745        *  @return  Read-only (constant) reference to data.
746        *  @throw  std::out_of_range  If @a n is an invalid index.
747        *
748        *  This function provides for safer data access.  The parameter
749        *  is first checked that it is in the range of the vector.  The
750        *  function throws out_of_range if the check fails.
751        */
752       const_reference
753       at(size_type __n) const
754       {
755         _M_range_check(__n);
756         return (*this)[__n];
757       }
758
759       /**
760        *  Returns a read/write reference to the data at the first
761        *  element of the %vector.
762        */
763       reference
764       front()
765       { return *begin(); }
766
767       /**
768        *  Returns a read-only (constant) reference to the data at the first
769        *  element of the %vector.
770        */
771       const_reference
772       front() const
773       { return *begin(); }
774
775       /**
776        *  Returns a read/write reference to the data at the last
777        *  element of the %vector.
778        */
779       reference
780       back()
781       { return *(end() - 1); }
782       
783       /**
784        *  Returns a read-only (constant) reference to the data at the
785        *  last element of the %vector.
786        */
787       const_reference
788       back() const
789       { return *(end() - 1); }
790
791       // _GLIBCXX_RESOLVE_LIB_DEFECTS
792       // DR 464. Suggestion for new member functions in standard containers.
793       // data access
794       /**
795        *   Returns a pointer such that [data(), data() + size()) is a valid
796        *   range.  For a non-empty %vector, data() == &front().
797        */
798 #ifdef __GXX_EXPERIMENTAL_CXX0X__
799       _Tp*
800 #else
801       pointer
802 #endif
803       data()
804       { return std::__addressof(front()); }
805
806 #ifdef __GXX_EXPERIMENTAL_CXX0X__
807       const _Tp*
808 #else
809       const_pointer
810 #endif
811       data() const
812       { return std::__addressof(front()); }
813
814       // [23.2.4.3] modifiers
815       /**
816        *  @brief  Add data to the end of the %vector.
817        *  @param  x  Data to be added.
818        *
819        *  This is a typical stack operation.  The function creates an
820        *  element at the end of the %vector and assigns the given data
821        *  to it.  Due to the nature of a %vector this operation can be
822        *  done in constant time if the %vector has preallocated space
823        *  available.
824        */
825       void
826       push_back(const value_type& __x)
827       {
828         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
829           {
830             this->_M_impl.construct(this->_M_impl._M_finish, __x);
831             ++this->_M_impl._M_finish;
832           }
833         else
834           _M_insert_aux(end(), __x);
835       }
836
837 #ifdef __GXX_EXPERIMENTAL_CXX0X__
838       void
839       push_back(value_type&& __x)
840       { emplace_back(std::move(__x)); }
841
842       template<typename... _Args>
843         void
844         emplace_back(_Args&&... __args);
845 #endif
846
847       /**
848        *  @brief  Removes last element.
849        *
850        *  This is a typical stack operation. It shrinks the %vector by one.
851        *
852        *  Note that no data is returned, and if the last element's
853        *  data is needed, it should be retrieved before pop_back() is
854        *  called.
855        */
856       void
857       pop_back()
858       {
859         --this->_M_impl._M_finish;
860         this->_M_impl.destroy(this->_M_impl._M_finish);
861       }
862
863 #ifdef __GXX_EXPERIMENTAL_CXX0X__
864       /**
865        *  @brief  Inserts an object in %vector before specified iterator.
866        *  @param  position  An iterator into the %vector.
867        *  @param  args  Arguments.
868        *  @return  An iterator that points to the inserted data.
869        *
870        *  This function will insert an object of type T constructed
871        *  with T(std::forward<Args>(args)...) before the specified location.
872        *  Note that this kind of operation could be expensive for a %vector
873        *  and if it is frequently used the user should consider using
874        *  std::list.
875        */
876       template<typename... _Args>
877         iterator
878         emplace(iterator __position, _Args&&... __args);
879 #endif
880
881       /**
882        *  @brief  Inserts given value into %vector before specified iterator.
883        *  @param  position  An iterator into the %vector.
884        *  @param  x  Data to be inserted.
885        *  @return  An iterator that points to the inserted data.
886        *
887        *  This function will insert a copy of the given value before
888        *  the specified location.  Note that this kind of operation
889        *  could be expensive for a %vector and if it is frequently
890        *  used the user should consider using std::list.
891        */
892       iterator
893       insert(iterator __position, const value_type& __x);
894
895 #ifdef __GXX_EXPERIMENTAL_CXX0X__
896       /**
897        *  @brief  Inserts given rvalue into %vector before specified iterator.
898        *  @param  position  An iterator into the %vector.
899        *  @param  x  Data to be inserted.
900        *  @return  An iterator that points to the inserted data.
901        *
902        *  This function will insert a copy of the given rvalue before
903        *  the specified location.  Note that this kind of operation
904        *  could be expensive for a %vector and if it is frequently
905        *  used the user should consider using std::list.
906        */
907       iterator
908       insert(iterator __position, value_type&& __x)
909       { return emplace(__position, std::move(__x)); }
910
911       /**
912        *  @brief  Inserts an initializer_list into the %vector.
913        *  @param  position  An iterator into the %vector.
914        *  @param  l  An initializer_list.
915        *
916        *  This function will insert copies of the data in the 
917        *  initializer_list @a l into the %vector before the location
918        *  specified by @a position.
919        *
920        *  Note that this kind of operation could be expensive for a
921        *  %vector and if it is frequently used the user should
922        *  consider using std::list.
923        */
924       void
925       insert(iterator __position, initializer_list<value_type> __l)
926       { this->insert(__position, __l.begin(), __l.end()); }
927 #endif
928
929       /**
930        *  @brief  Inserts a number of copies of given data into the %vector.
931        *  @param  position  An iterator into the %vector.
932        *  @param  n  Number of elements to be inserted.
933        *  @param  x  Data to be inserted.
934        *
935        *  This function will insert a specified number of copies of
936        *  the given data before the location specified by @a position.
937        *
938        *  Note that this kind of operation could be expensive for a
939        *  %vector and if it is frequently used the user should
940        *  consider using std::list.
941        */
942       void
943       insert(iterator __position, size_type __n, const value_type& __x)
944       { _M_fill_insert(__position, __n, __x); }
945
946       /**
947        *  @brief  Inserts a range into the %vector.
948        *  @param  position  An iterator into the %vector.
949        *  @param  first  An input iterator.
950        *  @param  last   An input iterator.
951        *
952        *  This function will insert copies of the data in the range
953        *  [first,last) into the %vector before the location specified
954        *  by @a pos.
955        *
956        *  Note that this kind of operation could be expensive for a
957        *  %vector and if it is frequently used the user should
958        *  consider using std::list.
959        */
960       template<typename _InputIterator>
961         void
962         insert(iterator __position, _InputIterator __first,
963                _InputIterator __last)
964         {
965           // Check whether it's an integral type.  If so, it's not an iterator.
966           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
967           _M_insert_dispatch(__position, __first, __last, _Integral());
968         }
969
970       /**
971        *  @brief  Remove element at given position.
972        *  @param  position  Iterator pointing to element to be erased.
973        *  @return  An iterator pointing to the next element (or end()).
974        *
975        *  This function will erase the element at the given position and thus
976        *  shorten the %vector by one.
977        *
978        *  Note This operation could be expensive and if it is
979        *  frequently used the user should consider using std::list.
980        *  The user is also cautioned that this function only erases
981        *  the element, and that if the element is itself a pointer,
982        *  the pointed-to memory is not touched in any way.  Managing
983        *  the pointer is the user's responsibility.
984        */
985       iterator
986       erase(iterator __position);
987
988       /**
989        *  @brief  Remove a range of elements.
990        *  @param  first  Iterator pointing to the first element to be erased.
991        *  @param  last  Iterator pointing to one past the last element to be
992        *                erased.
993        *  @return  An iterator pointing to the element pointed to by @a last
994        *           prior to erasing (or end()).
995        *
996        *  This function will erase the elements in the range [first,last) and
997        *  shorten the %vector accordingly.
998        *
999        *  Note This operation could be expensive and if it is
1000        *  frequently used the user should consider using std::list.
1001        *  The user is also cautioned that this function only erases
1002        *  the elements, and that if the elements themselves are
1003        *  pointers, the pointed-to memory is not touched in any way.
1004        *  Managing the pointer is the user's responsibility.
1005        */
1006       iterator
1007       erase(iterator __first, iterator __last);
1008
1009       /**
1010        *  @brief  Swaps data with another %vector.
1011        *  @param  x  A %vector of the same element and allocator types.
1012        *
1013        *  This exchanges the elements between two vectors in constant time.
1014        *  (Three pointers, so it should be quite fast.)
1015        *  Note that the global std::swap() function is specialized such that
1016        *  std::swap(v1,v2) will feed to this function.
1017        */
1018       void
1019       swap(vector& __x)
1020       {
1021         std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1022         std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1023         std::swap(this->_M_impl._M_end_of_storage,
1024                   __x._M_impl._M_end_of_storage);
1025
1026         // _GLIBCXX_RESOLVE_LIB_DEFECTS
1027         // 431. Swapping containers with unequal allocators.
1028         std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
1029                                                     __x._M_get_Tp_allocator());
1030       }
1031
1032       /**
1033        *  Erases all the elements.  Note that this function only erases the
1034        *  elements, and that if the elements themselves are pointers, the
1035        *  pointed-to memory is not touched in any way.  Managing the pointer is
1036        *  the user's responsibility.
1037        */
1038       void
1039       clear()
1040       { _M_erase_at_end(this->_M_impl._M_start); }
1041
1042     protected:
1043       /**
1044        *  Memory expansion handler.  Uses the member allocation function to
1045        *  obtain @a n bytes of memory, and then copies [first,last) into it.
1046        */
1047       template<typename _ForwardIterator>
1048         pointer
1049         _M_allocate_and_copy(size_type __n,
1050                              _ForwardIterator __first, _ForwardIterator __last)
1051         {
1052           pointer __result = this->_M_allocate(__n);
1053           __try
1054             {
1055               std::__uninitialized_copy_a(__first, __last, __result,
1056                                           _M_get_Tp_allocator());
1057               return __result;
1058             }
1059           __catch(...)
1060             {
1061               _M_deallocate(__result, __n);
1062               __throw_exception_again;
1063             }
1064         }
1065
1066
1067       // Internal constructor functions follow.
1068
1069       // Called by the range constructor to implement [23.1.1]/9
1070
1071       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1072       // 438. Ambiguity in the "do the right thing" clause
1073       template<typename _Integer>
1074         void
1075         _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1076         {
1077           this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1078           this->_M_impl._M_end_of_storage =
1079             this->_M_impl._M_start + static_cast<size_type>(__n);
1080           _M_fill_initialize(static_cast<size_type>(__n), __value);
1081         }
1082
1083       // Called by the range constructor to implement [23.1.1]/9
1084       template<typename _InputIterator>
1085         void
1086         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1087                                __false_type)
1088         {
1089           typedef typename std::iterator_traits<_InputIterator>::
1090             iterator_category _IterCategory;
1091           _M_range_initialize(__first, __last, _IterCategory());
1092         }
1093
1094       // Called by the second initialize_dispatch above
1095       template<typename _InputIterator>
1096         void
1097         _M_range_initialize(_InputIterator __first,
1098                             _InputIterator __last, std::input_iterator_tag)
1099         {
1100           for (; __first != __last; ++__first)
1101             push_back(*__first);
1102         }
1103
1104       // Called by the second initialize_dispatch above
1105       template<typename _ForwardIterator>
1106         void
1107         _M_range_initialize(_ForwardIterator __first,
1108                             _ForwardIterator __last, std::forward_iterator_tag)
1109         {
1110           const size_type __n = std::distance(__first, __last);
1111           this->_M_impl._M_start = this->_M_allocate(__n);
1112           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1113           this->_M_impl._M_finish =
1114             std::__uninitialized_copy_a(__first, __last,
1115                                         this->_M_impl._M_start,
1116                                         _M_get_Tp_allocator());
1117         }
1118
1119       // Called by the first initialize_dispatch above and by the
1120       // vector(n,value,a) constructor.
1121       void
1122       _M_fill_initialize(size_type __n, const value_type& __value)
1123       {
1124         std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 
1125                                       _M_get_Tp_allocator());
1126         this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1127       }
1128
1129 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1130       // Called by the vector(n) constructor.
1131       void
1132       _M_default_initialize(size_type __n)
1133       {
1134         std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 
1135                                          _M_get_Tp_allocator());
1136         this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1137       }
1138 #endif
1139
1140       // Internal assign functions follow.  The *_aux functions do the actual
1141       // assignment work for the range versions.
1142
1143       // Called by the range assign to implement [23.1.1]/9
1144
1145       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1146       // 438. Ambiguity in the "do the right thing" clause
1147       template<typename _Integer>
1148         void
1149         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1150         { _M_fill_assign(__n, __val); }
1151
1152       // Called by the range assign to implement [23.1.1]/9
1153       template<typename _InputIterator>
1154         void
1155         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1156                            __false_type)
1157         {
1158           typedef typename std::iterator_traits<_InputIterator>::
1159             iterator_category _IterCategory;
1160           _M_assign_aux(__first, __last, _IterCategory());
1161         }
1162
1163       // Called by the second assign_dispatch above
1164       template<typename _InputIterator>
1165         void
1166         _M_assign_aux(_InputIterator __first, _InputIterator __last,
1167                       std::input_iterator_tag);
1168
1169       // Called by the second assign_dispatch above
1170       template<typename _ForwardIterator>
1171         void
1172         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1173                       std::forward_iterator_tag);
1174
1175       // Called by assign(n,t), and the range assign when it turns out
1176       // to be the same thing.
1177       void
1178       _M_fill_assign(size_type __n, const value_type& __val);
1179
1180
1181       // Internal insert functions follow.
1182
1183       // Called by the range insert to implement [23.1.1]/9
1184
1185       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1186       // 438. Ambiguity in the "do the right thing" clause
1187       template<typename _Integer>
1188         void
1189         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1190                            __true_type)
1191         { _M_fill_insert(__pos, __n, __val); }
1192
1193       // Called by the range insert to implement [23.1.1]/9
1194       template<typename _InputIterator>
1195         void
1196         _M_insert_dispatch(iterator __pos, _InputIterator __first,
1197                            _InputIterator __last, __false_type)
1198         {
1199           typedef typename std::iterator_traits<_InputIterator>::
1200             iterator_category _IterCategory;
1201           _M_range_insert(__pos, __first, __last, _IterCategory());
1202         }
1203
1204       // Called by the second insert_dispatch above
1205       template<typename _InputIterator>
1206         void
1207         _M_range_insert(iterator __pos, _InputIterator __first,
1208                         _InputIterator __last, std::input_iterator_tag);
1209
1210       // Called by the second insert_dispatch above
1211       template<typename _ForwardIterator>
1212         void
1213         _M_range_insert(iterator __pos, _ForwardIterator __first,
1214                         _ForwardIterator __last, std::forward_iterator_tag);
1215
1216       // Called by insert(p,n,x), and the range insert when it turns out to be
1217       // the same thing.
1218       void
1219       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1220
1221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1222       // Called by resize(n).
1223       void
1224       _M_default_append(size_type __n);
1225 #endif
1226
1227       // Called by insert(p,x)
1228 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1229       void
1230       _M_insert_aux(iterator __position, const value_type& __x);
1231 #else
1232       template<typename... _Args>
1233         void
1234         _M_insert_aux(iterator __position, _Args&&... __args);
1235 #endif
1236
1237       // Called by the latter.
1238       size_type
1239       _M_check_len(size_type __n, const char* __s) const
1240       {
1241         if (max_size() - size() < __n)
1242           __throw_length_error(__N(__s));
1243
1244         const size_type __len = size() + std::max(size(), __n);
1245         return (__len < size() || __len > max_size()) ? max_size() : __len;
1246       }
1247
1248       // Internal erase functions follow.
1249
1250       // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1251       // _M_assign_aux.
1252       void
1253       _M_erase_at_end(pointer __pos)
1254       {
1255         std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1256         this->_M_impl._M_finish = __pos;
1257       }
1258     };
1259
1260
1261   /**
1262    *  @brief  Vector equality comparison.
1263    *  @param  x  A %vector.
1264    *  @param  y  A %vector of the same type as @a x.
1265    *  @return  True iff the size and elements of the vectors are equal.
1266    *
1267    *  This is an equivalence relation.  It is linear in the size of the
1268    *  vectors.  Vectors are considered equivalent if their sizes are equal,
1269    *  and if corresponding elements compare equal.
1270   */
1271   template<typename _Tp, typename _Alloc>
1272     inline bool
1273     operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1274     { return (__x.size() == __y.size()
1275               && std::equal(__x.begin(), __x.end(), __y.begin())); }
1276
1277   /**
1278    *  @brief  Vector ordering relation.
1279    *  @param  x  A %vector.
1280    *  @param  y  A %vector of the same type as @a x.
1281    *  @return  True iff @a x is lexicographically less than @a y.
1282    *
1283    *  This is a total ordering relation.  It is linear in the size of the
1284    *  vectors.  The elements must be comparable with @c <.
1285    *
1286    *  See std::lexicographical_compare() for how the determination is made.
1287   */
1288   template<typename _Tp, typename _Alloc>
1289     inline bool
1290     operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1291     { return std::lexicographical_compare(__x.begin(), __x.end(),
1292                                           __y.begin(), __y.end()); }
1293
1294   /// Based on operator==
1295   template<typename _Tp, typename _Alloc>
1296     inline bool
1297     operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1298     { return !(__x == __y); }
1299
1300   /// Based on operator<
1301   template<typename _Tp, typename _Alloc>
1302     inline bool
1303     operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1304     { return __y < __x; }
1305
1306   /// Based on operator<
1307   template<typename _Tp, typename _Alloc>
1308     inline bool
1309     operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1310     { return !(__y < __x); }
1311
1312   /// Based on operator<
1313   template<typename _Tp, typename _Alloc>
1314     inline bool
1315     operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1316     { return !(__x < __y); }
1317
1318   /// See std::vector::swap().
1319   template<typename _Tp, typename _Alloc>
1320     inline void
1321     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1322     { __x.swap(__y); }
1323
1324 _GLIBCXX_END_NAMESPACE_CONTAINER
1325 } // namespace std
1326
1327 #endif /* _STL_VECTOR_H */