stl_vector.h revision 97403
1// Vector implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file stl_vector.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_VECTOR_H 62#define __GLIBCPP_INTERNAL_VECTOR_H 63 64#include <bits/stl_iterator_base_funcs.h> 65#include <bits/functexcept.h> 66#include <bits/concept_check.h> 67 68namespace std 69{ 70 71// The vector base class serves two purposes. First, its constructor 72// and destructor allocate (but don't initialize) storage. This makes 73// exception safety easier. Second, the base class encapsulates all of 74// the differences between SGI-style allocators and standard-conforming 75// allocators. 76 77// Base class for ordinary allocators. 78template <class _Tp, class _Allocator, bool _IsStatic> 79class _Vector_alloc_base { 80public: 81 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 82 allocator_type; 83 allocator_type get_allocator() const { return _M_data_allocator; } 84 85 _Vector_alloc_base(const allocator_type& __a) 86 : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 87 {} 88 89protected: 90 allocator_type _M_data_allocator; 91 _Tp* _M_start; 92 _Tp* _M_finish; 93 _Tp* _M_end_of_storage; 94 95 _Tp* _M_allocate(size_t __n) 96 { return _M_data_allocator.allocate(__n); } 97 void _M_deallocate(_Tp* __p, size_t __n) 98 { if (__p) _M_data_allocator.deallocate(__p, __n); } 99}; 100 101// Specialization for allocators that have the property that we don't 102// actually have to store an allocator object. 103template <class _Tp, class _Allocator> 104class _Vector_alloc_base<_Tp, _Allocator, true> { 105public: 106 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 107 allocator_type; 108 allocator_type get_allocator() const { return allocator_type(); } 109 110 _Vector_alloc_base(const allocator_type&) 111 : _M_start(0), _M_finish(0), _M_end_of_storage(0) 112 {} 113 114protected: 115 _Tp* _M_start; 116 _Tp* _M_finish; 117 _Tp* _M_end_of_storage; 118 119 typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type; 120 _Tp* _M_allocate(size_t __n) 121 { return _Alloc_type::allocate(__n); } 122 void _M_deallocate(_Tp* __p, size_t __n) 123 { _Alloc_type::deallocate(__p, __n);} 124}; 125 126template <class _Tp, class _Alloc> 127struct _Vector_base 128 : public _Vector_alloc_base<_Tp, _Alloc, 129 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 130{ 131 typedef _Vector_alloc_base<_Tp, _Alloc, 132 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 133 _Base; 134 typedef typename _Base::allocator_type allocator_type; 135 136 _Vector_base(const allocator_type& __a) : _Base(__a) {} 137 _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) { 138 _M_start = _M_allocate(__n); 139 _M_finish = _M_start; 140 _M_end_of_storage = _M_start + __n; 141 } 142 143 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } 144}; 145 146 147/** 148 * @brief A standard container which offers fixed time access to individual 149 * elements in any order. 150 * 151 * @ingroup Containers 152 * @ingroup Sequences 153 * 154 * Meets the requirements of a <a href="tables.html#65">container</a>, a 155 * <a href="tables.html#66">reversible container</a>, and a 156 * <a href="tables.html#67">sequence</a>, including the 157 * <a href="tables.html#68">optional sequence requirements</a> with the 158 * %exception of @c push_front and @c pop_front. 159 * 160 * In some terminology a vector can be described as a dynamic C-style array, 161 * it offers fast and efficient access to individual elements in any order 162 * and saves the user from worrying about memory and size allocation. 163 * Subscripting ( [] ) access is also provided as with C-style arrays. 164*/ 165template <class _Tp, class _Alloc = allocator<_Tp> > 166class vector : protected _Vector_base<_Tp, _Alloc> 167{ 168 // concept requirements 169 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 170 171private: 172 typedef _Vector_base<_Tp, _Alloc> _Base; 173 typedef vector<_Tp, _Alloc> vector_type; 174public: 175 typedef _Tp value_type; 176 typedef value_type* pointer; 177 typedef const value_type* const_pointer; 178 typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; 179 typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> 180 const_iterator; 181 typedef value_type& reference; 182 typedef const value_type& const_reference; 183 typedef size_t size_type; 184 typedef ptrdiff_t difference_type; 185 186 typedef typename _Base::allocator_type allocator_type; 187 allocator_type get_allocator() const { return _Base::get_allocator(); } 188 189 typedef reverse_iterator<const_iterator> const_reverse_iterator; 190 typedef reverse_iterator<iterator> reverse_iterator; 191 192protected: 193 using _Base::_M_allocate; 194 using _Base::_M_deallocate; 195 using _Base::_M_start; 196 using _Base::_M_finish; 197 using _Base::_M_end_of_storage; 198 199protected: 200 void _M_insert_aux(iterator __position, const _Tp& __x); 201 void _M_insert_aux(iterator __position); 202 203public: 204 /** 205 * Returns a read/write iterator that points to the first element in the 206 * vector. Iteration is done in ordinary element order. 207 */ 208 iterator begin() { return iterator (_M_start); } 209 210 /** 211 * Returns a read-only (constant) iterator that points to the first element 212 * in the vector. Iteration is done in ordinary element order. 213 */ 214 const_iterator begin() const 215 { return const_iterator (_M_start); } 216 217 /** 218 * Returns a read/write iterator that points one past the last element in 219 * the vector. Iteration is done in ordinary element order. 220 */ 221 iterator end() { return iterator (_M_finish); } 222 223 /** 224 * Returns a read-only (constant) iterator that points one past the last 225 * element in the vector. Iteration is done in ordinary element order. 226 */ 227 const_iterator end() const { return const_iterator (_M_finish); } 228 229 /** 230 * Returns a read/write reverse iterator that points to the last element in 231 * the vector. Iteration is done in reverse element order. 232 */ 233 reverse_iterator rbegin() 234 { return reverse_iterator(end()); } 235 236 /** 237 * Returns a read-only (constant) reverse iterator that points to the last 238 * element in the vector. Iteration is done in reverse element order. 239 */ 240 const_reverse_iterator rbegin() const 241 { return const_reverse_iterator(end()); } 242 243 /** 244 * Returns a read/write reverse iterator that points to one before the 245 * first element in the vector. Iteration is done in reverse element 246 * order. 247 */ 248 reverse_iterator rend() 249 { return reverse_iterator(begin()); } 250 251 /** 252 * Returns a read-only (constant) reverse iterator that points to one 253 * before the first element in the vector. Iteration is done in reverse 254 * element order. 255 */ 256 const_reverse_iterator rend() const 257 { return const_reverse_iterator(begin()); } 258 259 /** Returns the number of elements in the vector. */ 260 size_type size() const 261 { return size_type(end() - begin()); } 262 263 /** Returns the size of the largest possible vector. */ 264 size_type max_size() const 265 { return size_type(-1) / sizeof(_Tp); } 266 267 /** 268 * Returns the amount of memory that has been alocated for the current 269 * elements (?). 270 */ 271 size_type capacity() const 272 { return size_type(const_iterator(_M_end_of_storage) - begin()); } 273 274 /** 275 * Returns true if the vector is empty. (Thus begin() would equal end().) 276 */ 277 bool empty() const 278 { return begin() == end(); } 279 280 /** 281 * @brief Subscript access to the data contained in the vector. 282 * @param n The element for which data should be accessed. 283 * @return Read/write reference to data. 284 * 285 * This operator allows for easy, array-style, data access. 286 * Note that data access with this operator is unchecked and out_of_range 287 * lookups are not defined. (For checked lookups see at().) 288 */ 289 reference operator[](size_type __n) { return *(begin() + __n); } 290 291 /** 292 * @brief Subscript access to the data contained in the vector. 293 * @param n The element for which data should be accessed. 294 * @return Read-only (constant) reference to data. 295 * 296 * This operator allows for easy, array-style, data access. 297 * Note that data access with this operator is unchecked and out_of_range 298 * lookups are not defined. (For checked lookups see at().) 299 */ 300 const_reference operator[](size_type __n) const { return *(begin() + __n); } 301 302 void _M_range_check(size_type __n) const { 303 if (__n >= this->size()) 304 __throw_out_of_range("vector"); 305 } 306 307 /** 308 * @brief Provides access to the data contained in the vector. 309 * @param n The element for which data should be accessed. 310 * @return Read/write reference to data. 311 * 312 * This function provides for safer data access. The parameter is first 313 * checked that it is in the range of the vector. The function throws 314 * out_of_range if the check fails. 315 */ 316 reference at(size_type __n) 317 { _M_range_check(__n); return (*this)[__n]; } 318 319 /** 320 * @brief Provides access to the data contained in the vector. 321 * @param n The element for which data should be accessed. 322 * @return Read-only (constant) reference to data. 323 * 324 * This function provides for safer data access. The parameter is first 325 * checked that it is in the range of the vector. The function throws 326 * out_of_range if the check fails. 327 */ 328 const_reference at(size_type __n) const 329 { _M_range_check(__n); return (*this)[__n]; } 330 331 332 explicit vector(const allocator_type& __a = allocator_type()) 333 : _Base(__a) {} 334 335 vector(size_type __n, const _Tp& __value, 336 const allocator_type& __a = allocator_type()) 337 : _Base(__n, __a) 338 { _M_finish = uninitialized_fill_n(_M_start, __n, __value); } 339 340 explicit vector(size_type __n) 341 : _Base(__n, allocator_type()) 342 { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); } 343 344 vector(const vector<_Tp, _Alloc>& __x) 345 : _Base(__x.size(), __x.get_allocator()) 346 { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); } 347 348 // Check whether it's an integral type. If so, it's not an iterator. 349 template <class _InputIterator> 350 vector(_InputIterator __first, _InputIterator __last, 351 const allocator_type& __a = allocator_type()) 352 : _Base(__a) 353 { 354 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 355 _M_initialize_aux(__first, __last, _Integral()); 356 } 357 358 template <class _Integer> 359 void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) 360 { 361 _M_start = _M_allocate(__n); 362 _M_end_of_storage = _M_start + __n; 363 _M_finish = uninitialized_fill_n(_M_start, __n, __value); 364 } 365 366 template<class _InputIterator> 367 void 368 _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type) 369 { 370 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory; 371 _M_range_initialize(__first, __last, _IterCategory()); 372 } 373 374 ~vector() 375 { _Destroy(_M_start, _M_finish); } 376 377 vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x); 378 379 /** 380 * @brief Attempt to preallocate enough memory for specified number of 381 * elements. 382 * @param n Number of elements required 383 * 384 * This function attempts to reserve enough memory for the vector to hold 385 * the specified number of elements. If the number requested is more than 386 * max_size() length_error is thrown. 387 * 388 * The advantage of this function is that if optimal code is a necessity 389 * and the user can determine the number of elements that will be required 390 * the user can reserve the memory and thus prevent a possible 391 * reallocation of memory and copy of vector data. 392 */ 393 void reserve(size_type __n) { 394 if (capacity() < __n) { 395 const size_type __old_size = size(); 396 pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); 397 _Destroy(_M_start, _M_finish); 398 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 399 _M_start = __tmp; 400 _M_finish = __tmp + __old_size; 401 _M_end_of_storage = _M_start + __n; 402 } 403 } 404 405 // assign(), a generalized assignment member function. Two 406 // versions: one that takes a count, and one that takes a range. 407 // The range version is a member template, so we dispatch on whether 408 // or not the type is an integer. 409 410 /** 411 * @brief Assigns a given value or range to a vector. 412 * @param n Number of elements to be assigned. 413 * @param val Value to be assigned. 414 * 415 * This function can be used to assign a range to a vector or fill it 416 * with a specified number of copies of the given value. 417 * Note that the assignment completely changes the vector and that the 418 * resulting vector's size is the same as the number of elements assigned. 419 * Old data may be lost. 420 */ 421 void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } 422 void _M_fill_assign(size_type __n, const _Tp& __val); 423 424 template<class _InputIterator> 425 void 426 assign(_InputIterator __first, _InputIterator __last) 427 { 428 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 429 _M_assign_dispatch(__first, __last, _Integral()); 430 } 431 432 template<class _Integer> 433 void 434 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 435 { _M_fill_assign((size_type) __n, (_Tp) __val); } 436 437 template<class _InputIter> 438 void 439 _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) 440 { 441 typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory; 442 _M_assign_aux(__first, __last, _IterCategory()); 443 } 444 445 template <class _InputIterator> 446 void 447 _M_assign_aux(_InputIterator __first, _InputIterator __last, 448 input_iterator_tag); 449 450 template <class _ForwardIterator> 451 void 452 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 453 forward_iterator_tag); 454 455 /** 456 * Returns a read/write reference to the data at the first element of the 457 * vector. 458 */ 459 reference front() { return *begin(); } 460 461 /** 462 * Returns a read-only (constant) reference to the data at the first 463 * element of the vector. 464 */ 465 const_reference front() const { return *begin(); } 466 467 /** 468 * Returns a read/write reference to the data at the last element of the 469 * vector. 470 */ 471 reference back() { return *(end() - 1); } 472 473 /** 474 * Returns a read-only (constant) reference to the data at the first 475 * element of the vector. 476 */ 477 const_reference back() const { return *(end() - 1); } 478 479 /** 480 * @brief Add data to the end of the vector. 481 * @param x Data to be added. 482 * 483 * This is a typical stack operation. The function creates an element at 484 * the end of the vector and assigns the given data to it. 485 * Due to the nature of a vector this operation can be done in constant 486 * time if the vector has preallocated space available. 487 */ 488 void 489 push_back(const _Tp& __x) 490 { 491 if (_M_finish != _M_end_of_storage) { 492 _Construct(_M_finish, __x); 493 ++_M_finish; 494 } 495 else 496 _M_insert_aux(end(), __x); 497 } 498 499#ifdef _GLIBCPP_DEPRECATED 500 /** 501 * Add an element to the end of the vector. The element is 502 * default-constructed. 503 * 504 * @note You must define _GLIBCPP_DEPRECATED to make this visible; see 505 * c++config.h. 506 */ 507 void 508 push_back() 509 { 510 if (_M_finish != _M_end_of_storage) { 511 _Construct(_M_finish); 512 ++_M_finish; 513 } 514 else 515 _M_insert_aux(end()); 516 } 517#endif 518 519 void 520 swap(vector<_Tp, _Alloc>& __x) 521 { 522 std::swap(_M_start, __x._M_start); 523 std::swap(_M_finish, __x._M_finish); 524 std::swap(_M_end_of_storage, __x._M_end_of_storage); 525 } 526 527 /** 528 * @brief Inserts given value into vector at specified element. 529 * @param position An iterator that points to the element where data 530 * should be inserted. 531 * @param x Data to be inserted. 532 * @return An iterator that points to the inserted data. 533 * 534 * This function will insert the given value into the specified location. 535 * Note that this kind of operation could be expensive for a vector and if 536 * it is frequently used the user should consider using std::list. 537 */ 538 iterator 539 insert(iterator __position, const _Tp& __x) 540 { 541 size_type __n = __position - begin(); 542 if (_M_finish != _M_end_of_storage && __position == end()) { 543 _Construct(_M_finish, __x); 544 ++_M_finish; 545 } 546 else 547 _M_insert_aux(iterator(__position), __x); 548 return begin() + __n; 549 } 550 551 /** 552 * @brief Inserts an empty element into the vector. 553 * @param position An iterator that points to the element where empty 554 * element should be inserted. 555 * @param x Data to be inserted. 556 * @return An iterator that points to the inserted element. 557 * 558 * This function will insert an empty element into the specified location. 559 * Note that this kind of operation could be expensive for a vector and if 560 * it is frequently used the user should consider using std::list. 561 */ 562 iterator 563 insert(iterator __position) 564 { 565 size_type __n = __position - begin(); 566 if (_M_finish != _M_end_of_storage && __position == end()) { 567 _Construct(_M_finish); 568 ++_M_finish; 569 } 570 else 571 _M_insert_aux(iterator(__position)); 572 return begin() + __n; 573 } 574 575 // Check whether it's an integral type. If so, it's not an iterator. 576 template<class _InputIterator> 577 void 578 insert(iterator __pos, _InputIterator __first, _InputIterator __last) 579 { 580 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 581 _M_insert_dispatch(__pos, __first, __last, _Integral()); 582 } 583 584 template <class _Integer> 585 void 586 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type) 587 { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); } 588 589 template<class _InputIterator> 590 void 591 _M_insert_dispatch(iterator __pos, 592 _InputIterator __first, _InputIterator __last, 593 __false_type) 594 { 595 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory; 596 _M_range_insert(__pos, __first, __last, _IterCategory()); 597 } 598 599 /** 600 * @brief Inserts a number of copies of given data into the vector. 601 * @param position An iterator that points to the element where data 602 * should be inserted. 603 * @param n Amount of elements to be inserted. 604 * @param x Data to be inserted. 605 * 606 * This function will insert a specified number of copies of the given data 607 * into the specified location. 608 * 609 * Note that this kind of operation could be expensive for a vector and if 610 * it is frequently used the user should consider using std::list. 611 */ 612 void insert (iterator __pos, size_type __n, const _Tp& __x) 613 { _M_fill_insert(__pos, __n, __x); } 614 615 void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x); 616 617 /** 618 * @brief Removes last element from vector. 619 * 620 * This is a typical stack operation. It allows us to shrink the vector by 621 * one. 622 * 623 * Note that no data is returned and if last element's data is needed it 624 * should be retrieved before pop_back() is called. 625 */ 626 void pop_back() { 627 --_M_finish; 628 _Destroy(_M_finish); 629 } 630 631 /** 632 * @brief Remove element at given position 633 * @param position Iterator pointing to element to be erased. 634 * @return Doc Me! (Iterator pointing to new element at old location?) 635 * 636 * This function will erase the element at the given position and thus 637 * shorten the vector by one. 638 * 639 * Note This operation could be expensive and if it is frequently used the 640 * user should consider using std::list. The user is also cautioned that 641 * this function only erases the element, and that if the element is itself 642 * a pointer, the pointed-to memory is not touched in any way. Managing 643 * the pointer is the user's responsibilty. 644 */ 645 iterator erase(iterator __position) { 646 if (__position + 1 != end()) 647 copy(__position + 1, end(), __position); 648 --_M_finish; 649 _Destroy(_M_finish); 650 return __position; 651 } 652 653 /** 654 * @brief Remove a range of elements from a vector. 655 * @param first Iterator pointing to the first element to be erased. 656 * @param last Iterator pointing to the last element to be erased. 657 * @return Doc Me! (Iterator pointing to new element at old location?) 658 * 659 * This function will erase the elements in the given range and shorten the 660 * vector accordingly. 661 * 662 * Note This operation could be expensive and if it is frequently used the 663 * user should consider using std::list. The user is also cautioned that 664 * this function only erases the elements, and that if the elements 665 * themselves are pointers, the pointed-to memory is not touched in any 666 * way. Managing the pointer is the user's responsibilty. 667 */ 668 iterator erase(iterator __first, iterator __last) { 669 iterator __i(copy(__last, end(), __first)); 670 _Destroy(__i, end()); 671 _M_finish = _M_finish - (__last - __first); 672 return __first; 673 } 674 675 /** 676 * @brief Resizes the vector to the specified number of elements. 677 * @param new_size Number of elements the vector should contain. 678 * @param x Data with which new elements should be populated. 679 * 680 * This function will resize the vector to the specified number of 681 * elements. If the number is smaller than the vector's current size the 682 * vector is truncated, otherwise the vector is extended and new elements 683 * are populated with given data. 684 */ 685 void resize(size_type __new_size, const _Tp& __x) { 686 if (__new_size < size()) 687 erase(begin() + __new_size, end()); 688 else 689 insert(end(), __new_size - size(), __x); 690 } 691 692 /** 693 * @brief Resizes the vector to the specified number of elements. 694 * @param new_size Number of elements the vector should contain. 695 * 696 * This function will resize the vector to the specified number of 697 * elements. If the number is smaller than the vector's current size the 698 * vector is truncated, otherwise the vector is extended and new elements 699 * are left uninitialized. 700 */ 701 void resize(size_type __new_size) { resize(__new_size, _Tp()); } 702 703 /** 704 * Erases all elements in vector. Note that this function only erases the 705 * elements, and that if the elements themselves are pointers, the 706 * pointed-to memory is not touched in any way. Managing the pointer is 707 * the user's responsibilty. 708 */ 709 void clear() { erase(begin(), end()); } 710 711protected: 712 713 template <class _ForwardIterator> 714 pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, 715 _ForwardIterator __last) 716 { 717 pointer __result = _M_allocate(__n); 718 try { 719 uninitialized_copy(__first, __last, __result); 720 return __result; 721 } 722 catch(...) 723 { 724 _M_deallocate(__result, __n); 725 __throw_exception_again; 726 } 727 } 728 729 template <class _InputIterator> 730 void _M_range_initialize(_InputIterator __first, 731 _InputIterator __last, input_iterator_tag) 732 { 733 for ( ; __first != __last; ++__first) 734 push_back(*__first); 735 } 736 737 // This function is only called by the constructor. 738 template <class _ForwardIterator> 739 void _M_range_initialize(_ForwardIterator __first, 740 _ForwardIterator __last, forward_iterator_tag) 741 { 742 size_type __n = distance(__first, __last); 743 _M_start = _M_allocate(__n); 744 _M_end_of_storage = _M_start + __n; 745 _M_finish = uninitialized_copy(__first, __last, _M_start); 746 } 747 748 template <class _InputIterator> 749 void _M_range_insert(iterator __pos, 750 _InputIterator __first, _InputIterator __last, 751 input_iterator_tag); 752 753 template <class _ForwardIterator> 754 void _M_range_insert(iterator __pos, 755 _ForwardIterator __first, _ForwardIterator __last, 756 forward_iterator_tag); 757}; 758 759template <class _Tp, class _Alloc> 760inline bool 761operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 762{ 763 return __x.size() == __y.size() && 764 equal(__x.begin(), __x.end(), __y.begin()); 765} 766 767template <class _Tp, class _Alloc> 768inline bool 769operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 770{ 771 return lexicographical_compare(__x.begin(), __x.end(), 772 __y.begin(), __y.end()); 773} 774 775template <class _Tp, class _Alloc> 776inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 777{ 778 __x.swap(__y); 779} 780 781template <class _Tp, class _Alloc> 782inline bool 783operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { 784 return !(__x == __y); 785} 786 787template <class _Tp, class _Alloc> 788inline bool 789operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { 790 return __y < __x; 791} 792 793template <class _Tp, class _Alloc> 794inline bool 795operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { 796 return !(__y < __x); 797} 798 799template <class _Tp, class _Alloc> 800inline bool 801operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) { 802 return !(__x < __y); 803} 804 805template <class _Tp, class _Alloc> 806vector<_Tp,_Alloc>& 807vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x) 808{ 809 if (&__x != this) { 810 const size_type __xlen = __x.size(); 811 if (__xlen > capacity()) { 812 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); 813 _Destroy(_M_start, _M_finish); 814 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 815 _M_start = __tmp; 816 _M_end_of_storage = _M_start + __xlen; 817 } 818 else if (size() >= __xlen) { 819 iterator __i(copy(__x.begin(), __x.end(), begin())); 820 _Destroy(__i, end()); 821 } 822 else { 823 copy(__x.begin(), __x.begin() + size(), _M_start); 824 uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); 825 } 826 _M_finish = _M_start + __xlen; 827 } 828 return *this; 829} 830 831template <class _Tp, class _Alloc> 832void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val) 833{ 834 if (__n > capacity()) { 835 vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator()); 836 __tmp.swap(*this); 837 } 838 else if (__n > size()) { 839 fill(begin(), end(), __val); 840 _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val); 841 } 842 else 843 erase(fill_n(begin(), __n, __val), end()); 844} 845 846template <class _Tp, class _Alloc> template <class _InputIter> 847void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last, 848 input_iterator_tag) { 849 iterator __cur(begin()); 850 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 851 *__cur = *__first; 852 if (__first == __last) 853 erase(__cur, end()); 854 else 855 insert(end(), __first, __last); 856} 857 858template <class _Tp, class _Alloc> template <class _ForwardIter> 859void 860vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last, 861 forward_iterator_tag) { 862 size_type __len = distance(__first, __last); 863 864 if (__len > capacity()) { 865 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 866 _Destroy(_M_start, _M_finish); 867 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 868 _M_start = __tmp; 869 _M_end_of_storage = _M_finish = _M_start + __len; 870 } 871 else if (size() >= __len) { 872 iterator __new_finish(copy(__first, __last, _M_start)); 873 _Destroy(__new_finish, end()); 874 _M_finish = __new_finish.base(); 875 } 876 else { 877 _ForwardIter __mid = __first; 878 advance(__mid, size()); 879 copy(__first, __mid, _M_start); 880 _M_finish = uninitialized_copy(__mid, __last, _M_finish); 881 } 882} 883 884template <class _Tp, class _Alloc> 885void 886vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) 887{ 888 if (_M_finish != _M_end_of_storage) { 889 _Construct(_M_finish, *(_M_finish - 1)); 890 ++_M_finish; 891 _Tp __x_copy = __x; 892 copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1)); 893 *__position = __x_copy; 894 } 895 else { 896 const size_type __old_size = size(); 897 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 898 iterator __new_start(_M_allocate(__len)); 899 iterator __new_finish(__new_start); 900 try { 901 __new_finish = uninitialized_copy(iterator(_M_start), __position, 902 __new_start); 903 _Construct(__new_finish.base(), __x); 904 ++__new_finish; 905 __new_finish = uninitialized_copy(__position, iterator(_M_finish), 906 __new_finish); 907 } 908 catch(...) 909 { 910 _Destroy(__new_start,__new_finish); 911 _M_deallocate(__new_start.base(),__len); 912 __throw_exception_again; 913 } 914 _Destroy(begin(), end()); 915 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 916 _M_start = __new_start.base(); 917 _M_finish = __new_finish.base(); 918 _M_end_of_storage = __new_start.base() + __len; 919 } 920} 921 922template <class _Tp, class _Alloc> 923void 924vector<_Tp, _Alloc>::_M_insert_aux(iterator __position) 925{ 926 if (_M_finish != _M_end_of_storage) { 927 _Construct(_M_finish, *(_M_finish - 1)); 928 ++_M_finish; 929 copy_backward(__position, iterator(_M_finish - 2), 930 iterator(_M_finish - 1)); 931 *__position = _Tp(); 932 } 933 else { 934 const size_type __old_size = size(); 935 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 936 pointer __new_start = _M_allocate(__len); 937 pointer __new_finish = __new_start; 938 try { 939 __new_finish = uninitialized_copy(iterator(_M_start), __position, 940 __new_start); 941 _Construct(__new_finish); 942 ++__new_finish; 943 __new_finish = uninitialized_copy(__position, iterator(_M_finish), 944 __new_finish); 945 } 946 catch(...) 947 { 948 _Destroy(__new_start,__new_finish); 949 _M_deallocate(__new_start,__len); 950 __throw_exception_again; 951 } 952 _Destroy(begin(), end()); 953 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 954 _M_start = __new_start; 955 _M_finish = __new_finish; 956 _M_end_of_storage = __new_start + __len; 957 } 958} 959 960template <class _Tp, class _Alloc> 961void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, 962 const _Tp& __x) 963{ 964 if (__n != 0) { 965 if (size_type(_M_end_of_storage - _M_finish) >= __n) { 966 _Tp __x_copy = __x; 967 const size_type __elems_after = end() - __position; 968 iterator __old_finish(_M_finish); 969 if (__elems_after > __n) { 970 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 971 _M_finish += __n; 972 copy_backward(__position, __old_finish - __n, __old_finish); 973 fill(__position, __position + __n, __x_copy); 974 } 975 else { 976 uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy); 977 _M_finish += __n - __elems_after; 978 uninitialized_copy(__position, __old_finish, _M_finish); 979 _M_finish += __elems_after; 980 fill(__position, __old_finish, __x_copy); 981 } 982 } 983 else { 984 const size_type __old_size = size(); 985 const size_type __len = __old_size + max(__old_size, __n); 986 iterator __new_start(_M_allocate(__len)); 987 iterator __new_finish(__new_start); 988 try { 989 __new_finish = uninitialized_copy(begin(), __position, __new_start); 990 __new_finish = uninitialized_fill_n(__new_finish, __n, __x); 991 __new_finish 992 = uninitialized_copy(__position, end(), __new_finish); 993 } 994 catch(...) 995 { 996 _Destroy(__new_start,__new_finish); 997 _M_deallocate(__new_start.base(),__len); 998 __throw_exception_again; 999 } 1000 _Destroy(_M_start, _M_finish); 1001 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 1002 _M_start = __new_start.base(); 1003 _M_finish = __new_finish.base(); 1004 _M_end_of_storage = __new_start.base() + __len; 1005 } 1006 } 1007} 1008 1009template <class _Tp, class _Alloc> template <class _InputIterator> 1010void 1011vector<_Tp, _Alloc>::_M_range_insert(iterator __pos, 1012 _InputIterator __first, 1013 _InputIterator __last, 1014 input_iterator_tag) 1015{ 1016 for ( ; __first != __last; ++__first) { 1017 __pos = insert(__pos, *__first); 1018 ++__pos; 1019 } 1020} 1021 1022template <class _Tp, class _Alloc> template <class _ForwardIterator> 1023void 1024vector<_Tp, _Alloc>::_M_range_insert(iterator __position, 1025 _ForwardIterator __first, 1026 _ForwardIterator __last, 1027 forward_iterator_tag) 1028{ 1029 if (__first != __last) { 1030 size_type __n = distance(__first, __last); 1031 if (size_type(_M_end_of_storage - _M_finish) >= __n) { 1032 const size_type __elems_after = end() - __position; 1033 iterator __old_finish(_M_finish); 1034 if (__elems_after > __n) { 1035 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 1036 _M_finish += __n; 1037 copy_backward(__position, __old_finish - __n, __old_finish); 1038 copy(__first, __last, __position); 1039 } 1040 else { 1041 _ForwardIterator __mid = __first; 1042 advance(__mid, __elems_after); 1043 uninitialized_copy(__mid, __last, _M_finish); 1044 _M_finish += __n - __elems_after; 1045 uninitialized_copy(__position, __old_finish, _M_finish); 1046 _M_finish += __elems_after; 1047 copy(__first, __mid, __position); 1048 } 1049 } 1050 else { 1051 const size_type __old_size = size(); 1052 const size_type __len = __old_size + max(__old_size, __n); 1053 iterator __new_start(_M_allocate(__len)); 1054 iterator __new_finish(__new_start); 1055 try { 1056 __new_finish = uninitialized_copy(iterator(_M_start), 1057 __position, __new_start); 1058 __new_finish = uninitialized_copy(__first, __last, __new_finish); 1059 __new_finish 1060 = uninitialized_copy(__position, iterator(_M_finish), __new_finish); 1061 } 1062 catch(...) 1063 { 1064 _Destroy(__new_start,__new_finish); 1065 _M_deallocate(__new_start.base(), __len); 1066 __throw_exception_again; 1067 } 1068 _Destroy(_M_start, _M_finish); 1069 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 1070 _M_start = __new_start.base(); 1071 _M_finish = __new_finish.base(); 1072 _M_end_of_storage = __new_start.base() + __len; 1073 } 1074 } 1075} 1076 1077} // namespace std 1078 1079#endif /* __GLIBCPP_INTERNAL_VECTOR_H */ 1080 1081// Local Variables: 1082// mode:C++ 1083// End: 1084