File Coverage

/usr/include/c++/5/bits/stl_vector.h
Criterion Covered Total %
statement 163 164 99.3
branch 62 118 52.5
condition n/a
subroutine n/a
pod n/a
total 225 282 79.7


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