1// Vector implementation -*- C++ -*- 2 3// Copyright (C) 2001-2015 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51/** @file bits/stl_vector.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{vector} 54 */ 55 56#ifndef _STL_VECTOR_H 57#define _STL_VECTOR_H 1 58 59#include <bits/stl_iterator_base_funcs.h> 60#include <bits/functexcept.h> 61#include <bits/concept_check.h> 62#if __cplusplus >= 201103L 63#include <initializer_list> 64#endif 65 66namespace 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 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 _Vector_impl() 87 : _Tp_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() 88 { } 89 90 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT 91 : _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() 92 { } 93 94#if __cplusplus >= 201103L 95 _Vector_impl(_Tp_alloc_type&& __a) noexcept 96 : _Tp_alloc_type(std::move(__a)), 97 _M_start(), _M_finish(), _M_end_of_storage() 98 { } 99#endif 100 101 void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT 102 { 103 std::swap(_M_start, __x._M_start); 104 std::swap(_M_finish, __x._M_finish); 105 std::swap(_M_end_of_storage, __x._M_end_of_storage); 106 } 107 }; 108 109 public: 110 typedef _Alloc allocator_type; 111 112 _Tp_alloc_type& 113 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT 114 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 115 116 const _Tp_alloc_type& 117 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT 118 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 119 120 allocator_type 121 get_allocator() const _GLIBCXX_NOEXCEPT 122 { return allocator_type(_M_get_Tp_allocator()); } 123 124 _Vector_base() 125 : _M_impl() { } 126 127 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT 128 : _M_impl(__a) { } 129 130 _Vector_base(size_t __n) 131 : _M_impl() 132 { _M_create_storage(__n); } 133 134 _Vector_base(size_t __n, const allocator_type& __a) 135 : _M_impl(__a) 136 { _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 _Vector_base(_Vector_base&& __x) noexcept 143 : _M_impl(std::move(__x._M_get_Tp_allocator())) 144 { 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 ~_Vector_base() _GLIBCXX_NOEXCEPT 160 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 161 - this->_M_impl._M_start); } 162 163 public: 164 _Vector_impl _M_impl; 165 166 pointer 167 _M_allocate(size_t __n) 168 { 169 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 170 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); 171 } 172 173 void 174 _M_deallocate(pointer __p, size_t __n) 175 { 176 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; 177 if (__p) 178 _Tr::deallocate(_M_impl, __p, __n); 179 } 180 181 private: 182 void 183 _M_create_storage(size_t __n) 184 { 185 this->_M_impl._M_start = this->_M_allocate(__n); 186 this->_M_impl._M_finish = this->_M_impl._M_start; 187 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 188 } 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 vector() 254#if __cplusplus >= 201103L 255 noexcept(is_nothrow_default_constructible<_Alloc>::value) 256#endif 257 : _Base() { } 258 259 /** 260 * @brief Creates a %vector with no elements. 261 * @param __a An allocator object. 262 */ 263 explicit 264 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT 265 : _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 vector(const vector& __x) 319 : _Base(__x.size(), 320 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) 321 { this->_M_impl._M_finish = 322 std::__uninitialized_copy_a(__x.begin(), __x.end(), 323 this->_M_impl._M_start, 324 _M_get_Tp_allocator()); 325 } 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 vector(vector&& __x) noexcept 336 : _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 ~vector() _GLIBCXX_NOEXCEPT 424 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 425 _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 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 449 { 450 constexpr bool __move_storage = 451 _Alloc_traits::_S_propagate_on_move_assign() 452 || _Alloc_traits::_S_always_equal(); 453 _M_move_assign(std::move(__x), 454 integral_constant<bool, __move_storage>()); 455 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 begin() _GLIBCXX_NOEXCEPT 548 { 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 begin() const _GLIBCXX_NOEXCEPT 557 { 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 end() _GLIBCXX_NOEXCEPT 566 { 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 end() const _GLIBCXX_NOEXCEPT 575 { 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 cbegin() const noexcept 621 { 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 size() const _GLIBCXX_NOEXCEPT 655 { 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 max_size() const _GLIBCXX_NOEXCEPT 660 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); } 661 662#if __cplusplus >= 201103L 663 /** 664 * @brief Resizes the %vector to the specified number of elements. 665 * @param __new_size Number of elements the %vector should contain. 666 * 667 * This function will %resize the %vector to the specified 668 * number of elements. If the number is smaller than the 669 * %vector's current size the %vector is truncated, otherwise 670 * default constructed elements are appended. 671 */ 672 void 673 resize(size_type __new_size) 674 { 675 if (__new_size > size()) 676 _M_default_append(__new_size - size()); 677 else if (__new_size < size()) 678 _M_erase_at_end(this->_M_impl._M_start + __new_size); 679 } 680 681 /** 682 * @brief Resizes the %vector to the specified number of elements. 683 * @param __new_size Number of elements the %vector should contain. 684 * @param __x Data with which new elements should be populated. 685 * 686 * This function will %resize the %vector to the specified 687 * number of elements. If the number is smaller than the 688 * %vector's current size the %vector is truncated, otherwise 689 * the %vector is extended and new elements are populated with 690 * given data. 691 */ 692 void 693 resize(size_type __new_size, const value_type& __x) 694 { 695 if (__new_size > size()) 696 insert(end(), __new_size - size(), __x); 697 else if (__new_size < size()) 698 _M_erase_at_end(this->_M_impl._M_start + __new_size); 699 } 700#else 701 /** 702 * @brief Resizes the %vector to the specified number of elements. 703 * @param __new_size Number of elements the %vector should contain. 704 * @param __x Data with which new elements should be populated. 705 * 706 * This function will %resize the %vector to the specified 707 * number of elements. If the number is smaller than the 708 * %vector's current size the %vector is truncated, otherwise 709 * the %vector is extended and new elements are populated with 710 * given data. 711 */ 712 void 713 resize(size_type __new_size, value_type __x = value_type()) 714 { 715 if (__new_size > size()) 716 insert(end(), __new_size - size(), __x); 717 else if (__new_size < size()) 718 _M_erase_at_end(this->_M_impl._M_start + __new_size); 719 } 720#endif 721 722#if __cplusplus >= 201103L 723 /** A non-binding request to reduce capacity() to size(). */ 724 void 725 shrink_to_fit() 726 { _M_shrink_to_fit(); } 727#endif 728 729 /** 730 * Returns the total number of elements that the %vector can 731 * hold before needing to allocate more memory. 732 */ 733 size_type 734 capacity() const _GLIBCXX_NOEXCEPT 735 { return size_type(this->_M_impl._M_end_of_storage 736 - 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 empty() const _GLIBCXX_NOEXCEPT 744 { 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 operator[](size_type __n) _GLIBCXX_NOEXCEPT 780 { return *(this->_M_impl._M_start + __n); } 781 782 /** 783 * @brief Subscript access to the data contained in the %vector. 784 * @param __n The index of the element for which data should be 785 * accessed. 786 * @return Read-only (constant) reference to data. 787 * 788 * This operator allows for easy, array-style, data access. 789 * Note that data access with this operator is unchecked and 790 * out_of_range lookups are not defined. (For checked lookups 791 * see at().) 792 */ 793 const_reference 794 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 795 { return *(this->_M_impl._M_start + __n); } 796 797 protected: 798 /// Safety check used only from at(). 799 void 800 _M_range_check(size_type __n) const 801 { 802 if (__n >= this->size()) 803 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n " 804 "(which is %zu) >= this->size() " 805 "(which is %zu)"), 806 __n, this->size()); 807 } 808 809 public: 810 /** 811 * @brief Provides access to the data contained in the %vector. 812 * @param __n The index of the element for which data should be 813 * accessed. 814 * @return Read/write reference to data. 815 * @throw std::out_of_range If @a __n is an invalid index. 816 * 817 * This function provides for safer data access. The parameter 818 * is first checked that it is in the range of the vector. The 819 * function throws out_of_range if the check fails. 820 */ 821 reference 822 at(size_type __n) 823 { 824 _M_range_check(__n); 825 return (*this)[__n]; 826 } 827 828 /** 829 * @brief Provides access to the data contained in the %vector. 830 * @param __n The index of the element for which data should be 831 * accessed. 832 * @return Read-only (constant) reference to data. 833 * @throw std::out_of_range If @a __n is an invalid index. 834 * 835 * This function provides for safer data access. The parameter 836 * is first checked that it is in the range of the vector. The 837 * function throws out_of_range if the check fails. 838 */ 839 const_reference 840 at(size_type __n) const 841 { 842 _M_range_check(__n); 843 return (*this)[__n]; 844 } 845 846 /** 847 * Returns a read/write reference to the data at the first 848 * element of the %vector. 849 */ 850 reference 851 front() _GLIBCXX_NOEXCEPT 852 { return *begin(); } 853 854 /** 855 * Returns a read-only (constant) reference to the data at the first 856 * element of the %vector. 857 */ 858 const_reference 859 front() const _GLIBCXX_NOEXCEPT 860 { return *begin(); } 861 862 /** 863 * Returns a read/write reference to the data at the last 864 * element of the %vector. 865 */ 866 reference 867 back() _GLIBCXX_NOEXCEPT 868 { 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 push_back(const value_type& __x) 914 { 915 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 916 { 917 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 918 __x); 919 ++this->_M_impl._M_finish; 920 } 921 else 922#if __cplusplus >= 201103L 923 _M_emplace_back_aux(__x); 924#else 925 _M_insert_aux(end(), __x); 926#endif 927 } 928 929#if __cplusplus >= 201103L 930 void 931 push_back(value_type&& __x) 932 { 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 pop_back() _GLIBCXX_NOEXCEPT 950 { 951 --this->_M_impl._M_finish; 952 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); 953 } 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 erase(const_iterator __position) 1147 { 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 erase(const_iterator __first, const_iterator __last) 1174 { 1175 const auto __beg = begin(); 1176 const auto __cbeg = cbegin(); 1177 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg)); 1178 } 1179#else 1180 erase(iterator __first, iterator __last) 1181 { return _M_erase(__first, __last); } 1182#endif 1183 1184 /** 1185 * @brief Swaps data with another %vector. 1186 * @param __x A %vector of the same element and allocator types. 1187 * 1188 * This exchanges the elements between two vectors in constant time. 1189 * (Three pointers, so it should be quite fast.) 1190 * Note that the global std::swap() function is specialized such that 1191 * std::swap(v1,v2) will feed to this function. 1192 */ 1193 void 1194 swap(vector& __x) 1195#if __cplusplus >= 201103L 1196 noexcept(_Alloc_traits::_S_nothrow_swap()) 1197#endif 1198 { 1199 this->_M_impl._M_swap_data(__x._M_impl); 1200 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), 1201 __x._M_get_Tp_allocator()); 1202 } 1203 1204 /** 1205 * Erases all the elements. Note that this function only erases the 1206 * elements, and that if the elements themselves are pointers, the 1207 * pointed-to memory is not touched in any way. Managing the pointer is 1208 * the user's responsibility. 1209 */ 1210 void 1211 clear() _GLIBCXX_NOEXCEPT 1212 { _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 _M_allocate_and_copy(size_type __n, 1222 _ForwardIterator __first, _ForwardIterator __last) 1223 { 1224 pointer __result = this->_M_allocate(__n); 1225 __try 1226 { 1227 std::__uninitialized_copy_a(__first, __last, __result, 1228 _M_get_Tp_allocator()); 1229 return __result; 1230 } 1231 __catch(...) 1232 { 1233 _M_deallocate(__result, __n); 1234 __throw_exception_again; 1235 } 1236 } 1237 1238 1239 // Internal constructor functions follow. 1240 1241 // Called by the range constructor to implement [23.1.1]/9 1242 1243 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1244 // 438. Ambiguity in the "do the right thing" clause 1245 template<typename _Integer> 1246 void 1247 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 1248 { 1249 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n)); 1250 this->_M_impl._M_end_of_storage = 1251 this->_M_impl._M_start + static_cast<size_type>(__n); 1252 _M_fill_initialize(static_cast<size_type>(__n), __value); 1253 } 1254 1255 // Called by the range constructor to implement [23.1.1]/9 1256 template<typename _InputIterator> 1257 void 1258 _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 this->_M_impl._M_finish = 1301 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 1302 _M_get_Tp_allocator()); 1303 } 1304 1305#if __cplusplus >= 201103L 1306 // Called by the vector(n) constructor. 1307 void 1308 _M_default_initialize(size_type __n) 1309 { 1310 this->_M_impl._M_finish = 1311 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 1312 _M_get_Tp_allocator()); 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 _M_check_len(size_type __n, const char* __s) const 1423 { 1424 if (max_size() - size() < __n) 1425 __throw_length_error(__N(__s)); 1426 1427 const size_type __len = size() + std::max(size(), __n); 1428 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 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT 1437 { 1438 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 1439 this->_M_impl._M_finish = __pos; 1440 } 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 _M_move_assign(vector&& __x, std::true_type) noexcept 1455 { 1456 vector __tmp(get_allocator()); 1457 this->_M_impl._M_swap_data(__tmp._M_impl); 1458 this->_M_impl._M_swap_data(__x._M_impl); 1459 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); 1460 } 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 */ 1566