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