Line data Source code
1 : // Vector implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2014 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 210 : 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 128 : _Vector_impl()
87 128 : : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
88 128 : { }
89 :
90 50 : _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
91 50 : : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
92 50 : { }
93 :
94 : #if __cplusplus >= 201103L
95 32 : _Vector_impl(_Tp_alloc_type&& __a) noexcept
96 32 : : _Tp_alloc_type(std::move(__a)),
97 32 : _M_start(0), _M_finish(0), _M_end_of_storage(0)
98 32 : { }
99 : #endif
100 :
101 36 : void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT
102 : {
103 36 : std::swap(_M_start, __x._M_start);
104 36 : std::swap(_M_finish, __x._M_finish);
105 36 : std::swap(_M_end_of_storage, __x._M_end_of_storage);
106 36 : }
107 : };
108 :
109 : public:
110 : typedef _Alloc allocator_type;
111 :
112 : _Tp_alloc_type&
113 517 : _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
114 517 : { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
115 :
116 : const _Tp_alloc_type&
117 233 : _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
118 233 : { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
119 :
120 : allocator_type
121 2 : get_allocator() const _GLIBCXX_NOEXCEPT
122 2 : { return allocator_type(_M_get_Tp_allocator()); }
123 :
124 128 : _Vector_base()
125 128 : : _M_impl() { }
126 :
127 2 : _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
128 2 : : _M_impl(__a) { }
129 :
130 : _Vector_base(size_t __n)
131 : : _M_impl()
132 : { _M_create_storage(__n); }
133 :
134 48 : _Vector_base(size_t __n, const allocator_type& __a)
135 48 : : _M_impl(__a)
136 48 : { _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 32 : _Vector_base(_Vector_base&& __x) noexcept
143 32 : : _M_impl(std::move(__x._M_get_Tp_allocator()))
144 32 : { 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 210 : ~_Vector_base() _GLIBCXX_NOEXCEPT
160 210 : { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
161 420 : - this->_M_impl._M_start); }
162 :
163 : public:
164 : _Vector_impl _M_impl;
165 :
166 : pointer
167 157 : _M_allocate(size_t __n)
168 : {
169 : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
170 157 : return __n != 0 ? _Tr::allocate(_M_impl, __n) : 0;
171 : }
172 :
173 : void
174 319 : _M_deallocate(pointer __p, size_t __n)
175 : {
176 : typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
177 319 : if (__p)
178 157 : _Tr::deallocate(_M_impl, __p, __n);
179 319 : }
180 :
181 : private:
182 : void
183 48 : _M_create_storage(size_t __n)
184 : {
185 48 : this->_M_impl._M_start = this->_M_allocate(__n);
186 48 : this->_M_impl._M_finish = this->_M_impl._M_start;
187 48 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
188 48 : }
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 128 : vector()
254 : #if __cplusplus >= 201103L
255 : noexcept(is_nothrow_default_constructible<_Alloc>::value)
256 : #endif
257 128 : : _Base() { }
258 :
259 : /**
260 : * @brief Creates a %vector with no elements.
261 : * @param __a An allocator object.
262 : */
263 : explicit
264 2 : vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
265 2 : : _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 : vector(size_type __n, const allocator_type& __a = allocator_type())
278 : : _Base(__n, __a)
279 : { _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 : vector(size_type __n, const value_type& __value,
290 : const allocator_type& __a = allocator_type())
291 : : _Base(__n, __a)
292 : { _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 48 : vector(const vector& __x)
319 : : _Base(__x.size(),
320 48 : _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
321 48 : { this->_M_impl._M_finish =
322 : std::__uninitialized_copy_a(__x.begin(), __x.end(),
323 : this->_M_impl._M_start,
324 48 : _M_get_Tp_allocator());
325 48 : }
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 32 : vector(vector&& __x) noexcept
336 32 : : _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 : vector(initializer_list<value_type> __l,
374 : const allocator_type& __a = allocator_type())
375 : : _Base(__a)
376 : {
377 : _M_range_initialize(__l.begin(), __l.end(),
378 : random_access_iterator_tag());
379 : }
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 : vector(_InputIterator __first, _InputIterator __last,
402 : const allocator_type& __a = allocator_type())
403 : : _Base(__a)
404 : { _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 210 : ~vector() _GLIBCXX_NOEXCEPT
424 210 : { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
425 420 : _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 2 : operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
449 : {
450 : constexpr bool __move_storage =
451 : _Alloc_traits::_S_propagate_on_move_assign()
452 2 : || _Alloc_traits::_S_always_equal();
453 2 : _M_move_assign(std::move(__x),
454 2 : integral_constant<bool, __move_storage>());
455 2 : 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 66 : begin() _GLIBCXX_NOEXCEPT
548 66 : { 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 98 : begin() const _GLIBCXX_NOEXCEPT
557 98 : { 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 87 : end() _GLIBCXX_NOEXCEPT
566 87 : { 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 100 : end() const _GLIBCXX_NOEXCEPT
575 100 : { 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 0 : cbegin() const noexcept
621 0 : { 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 571 : size() const _GLIBCXX_NOEXCEPT
655 571 : { 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 183 : max_size() const _GLIBCXX_NOEXCEPT
660 183 : { 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 0 : resize(size_type __new_size)
674 : {
675 0 : if (__new_size > size())
676 0 : _M_default_append(__new_size - size());
677 0 : else if (__new_size < size())
678 0 : _M_erase_at_end(this->_M_impl._M_start + __new_size);
679 0 : }
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 33 : capacity() const _GLIBCXX_NOEXCEPT
735 : { return size_type(this->_M_impl._M_end_of_storage
736 33 : - 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 9 : empty() const _GLIBCXX_NOEXCEPT
744 9 : { 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 58 : operator[](size_type __n) _GLIBCXX_NOEXCEPT
780 58 : { 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 5 : front() _GLIBCXX_NOEXCEPT
852 5 : { 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 0 : back() _GLIBCXX_NOEXCEPT
868 0 : { 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 23 : push_back(const value_type& __x)
914 : {
915 23 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
916 : {
917 0 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
918 0 : __x);
919 0 : ++this->_M_impl._M_finish;
920 : }
921 : else
922 : #if __cplusplus >= 201103L
923 23 : _M_emplace_back_aux(__x);
924 : #else
925 : _M_insert_aux(end(), __x);
926 : #endif
927 23 : }
928 :
929 : #if __cplusplus >= 201103L
930 : void
931 85 : push_back(value_type&& __x)
932 85 : { 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 14 : pop_back() _GLIBCXX_NOEXCEPT
950 : {
951 14 : --this->_M_impl._M_finish;
952 14 : _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
953 14 : }
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 : insert(const_iterator __position, _InputIterator __first,
1096 : _InputIterator __last)
1097 : {
1098 : difference_type __offset = __position - cbegin();
1099 : _M_insert_dispatch(begin() + __offset,
1100 : __first, __last, __false_type());
1101 : 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 0 : erase(const_iterator __position)
1147 0 : { return _M_erase(begin() + (__position - cbegin())); }
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 0 : erase(const_iterator __first, const_iterator __last)
1174 : {
1175 0 : const auto __beg = begin();
1176 0 : const auto __cbeg = cbegin();
1177 0 : 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 0 : swap(vector& __x)
1195 : #if __cplusplus >= 201103L
1196 : noexcept(_Alloc_traits::_S_nothrow_swap())
1197 : #endif
1198 : {
1199 0 : this->_M_impl._M_swap_data(__x._M_impl);
1200 0 : _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1201 0 : __x._M_get_Tp_allocator());
1202 0 : }
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 0 : clear() _GLIBCXX_NOEXCEPT
1212 0 : { _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 28 : _M_allocate_and_copy(size_type __n,
1222 : _ForwardIterator __first, _ForwardIterator __last)
1223 : {
1224 28 : pointer __result = this->_M_allocate(__n);
1225 : __try
1226 : {
1227 28 : std::__uninitialized_copy_a(__first, __last, __result,
1228 28 : _M_get_Tp_allocator());
1229 28 : return __result;
1230 : }
1231 0 : __catch(...)
1232 : {
1233 0 : _M_deallocate(__result, __n);
1234 0 : __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 : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1259 : __false_type)
1260 : {
1261 : typedef typename std::iterator_traits<_InputIterator>::
1262 : iterator_category _IterCategory;
1263 : _M_range_initialize(__first, __last, _IterCategory());
1264 : }
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 : _M_range_initialize(_ForwardIterator __first,
1284 : _ForwardIterator __last, std::forward_iterator_tag)
1285 : {
1286 : const size_type __n = std::distance(__first, __last);
1287 : this->_M_impl._M_start = this->_M_allocate(__n);
1288 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1289 : this->_M_impl._M_finish =
1290 : std::__uninitialized_copy_a(__first, __last,
1291 : this->_M_impl._M_start,
1292 : _M_get_Tp_allocator());
1293 : }
1294 :
1295 : // Called by the first initialize_dispatch above and by the
1296 : // vector(n,value,a) constructor.
1297 : void
1298 : _M_fill_initialize(size_type __n, const value_type& __value)
1299 : {
1300 : std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1301 : _M_get_Tp_allocator());
1302 : this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1303 : }
1304 :
1305 : #if __cplusplus >= 201103L
1306 : // Called by the vector(n) constructor.
1307 : void
1308 : _M_default_initialize(size_type __n)
1309 : {
1310 : std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1311 : _M_get_Tp_allocator());
1312 : this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1313 : }
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 : _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 : _M_range_insert(__pos, __first, __last, _IterCategory());
1378 : }
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 81 : _M_check_len(size_type __n, const char* __s) const
1423 : {
1424 81 : if (max_size() - size() < __n)
1425 0 : __throw_length_error(__N(__s));
1426 :
1427 81 : const size_type __len = size() + std::max(size(), __n);
1428 81 : return (__len < size() || __len > max_size()) ? max_size() : __len;
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 0 : _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1437 : {
1438 0 : std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1439 0 : this->_M_impl._M_finish = __pos;
1440 0 : }
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 2 : _M_move_assign(vector&& __x, std::true_type) noexcept
1455 : {
1456 2 : vector __tmp(get_allocator());
1457 2 : this->_M_impl._M_swap_data(__tmp._M_impl);
1458 2 : this->_M_impl._M_swap_data(__x._M_impl);
1459 2 : std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1460 2 : }
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 */
|
