stl_vector.h revision 236829
1// Vector implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 2, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING. If not, write to the Free 19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20// USA. 21 22// As a special exception, you may use this file as part of a free software 23// library without restriction. Specifically, if other files instantiate 24// templates or use macros or inline functions from this file, or you compile 25// this file and link it with other files to produce an executable, this 26// file does not by itself cause the resulting executable to be covered by 27// the GNU General Public License. This exception does not however 28// invalidate any other reasons why the executable file might be covered by 29// the GNU General Public License. 30 31/* 32 * 33 * Copyright (c) 1994 34 * Hewlett-Packard Company 35 * 36 * Permission to use, copy, modify, distribute and sell this software 37 * and its documentation for any purpose is hereby granted without fee, 38 * provided that the above copyright notice appear in all copies and 39 * that both that copyright notice and this permission notice appear 40 * in supporting documentation. Hewlett-Packard Company makes no 41 * representations about the suitability of this software for any 42 * purpose. It is provided "as is" without express or implied warranty. 43 * 44 * 45 * Copyright (c) 1996 46 * Silicon Graphics Computer Systems, Inc. 47 * 48 * Permission to use, copy, modify, distribute and sell this software 49 * and its documentation for any purpose is hereby granted without fee, 50 * provided that the above copyright notice appear in all copies and 51 * that both that copyright notice and this permission notice appear 52 * in supporting documentation. Silicon Graphics makes no 53 * representations about the suitability of this software for any 54 * purpose. It is provided "as is" without express or implied warranty. 55 */ 56 57/** @file stl_vector.h 58 * This is an internal header file, included by other library headers. 59 * You should not attempt to use it directly. 60 */ 61 62#ifndef _VECTOR_H 63#define _VECTOR_H 1 64 65#include <bits/stl_iterator_base_funcs.h> 66#include <bits/functexcept.h> 67#include <bits/concept_check.h> 68 69_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 70 71 /** 72 * @if maint 73 * See bits/stl_deque.h's _Deque_base for an explanation. 74 * @endif 75 */ 76 template<typename _Tp, typename _Alloc> 77 struct _Vector_base 78 { 79 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 80 81 struct _Vector_impl 82 : public _Tp_alloc_type 83 { 84 _Tp* _M_start; 85 _Tp* _M_finish; 86 _Tp* _M_end_of_storage; 87 88 _Vector_impl() 89 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) 90 { } 91 92 _Vector_impl(_Tp_alloc_type const& __a) 93 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 94 { } 95 }; 96 97 public: 98 typedef _Alloc allocator_type; 99 100 _Tp_alloc_type& 101 _M_get_Tp_allocator() 102 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 103 104 const _Tp_alloc_type& 105 _M_get_Tp_allocator() const 106 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 107 108 allocator_type 109 get_allocator() const 110 { return allocator_type(_M_get_Tp_allocator()); } 111 112 _Vector_base() 113 : _M_impl() { } 114 115 _Vector_base(const allocator_type& __a) 116 : _M_impl(__a) 117 { } 118 119 _Vector_base(size_t __n, const allocator_type& __a) 120 : _M_impl(__a) 121 { 122 this->_M_impl._M_start = this->_M_allocate(__n); 123 this->_M_impl._M_finish = this->_M_impl._M_start; 124 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 125 } 126 127 ~_Vector_base() 128 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 129 - this->_M_impl._M_start); } 130 131 public: 132 _Vector_impl _M_impl; 133 134 _Tp* 135 _M_allocate(size_t __n) 136 { return _M_impl.allocate(__n); } 137 138 void 139 _M_deallocate(_Tp* __p, size_t __n) 140 { 141 if (__p) 142 _M_impl.deallocate(__p, __n); 143 } 144 }; 145 146 147 /** 148 * @brief A standard container which offers fixed time access to 149 * individual 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 161 * C-style array, it offers fast and efficient access to individual 162 * elements in any order and saves the user from worrying about 163 * memory and size allocation. Subscripting ( @c [] ) access is 164 * also provided as with C-style arrays. 165 */ 166 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 167 class vector : protected _Vector_base<_Tp, _Alloc> 168 { 169 // Concept requirements. 170 typedef typename _Alloc::value_type _Alloc_value_type; 171 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 172 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 173 174 typedef _Vector_base<_Tp, _Alloc> _Base; 175 typedef vector<_Tp, _Alloc> vector_type; 176 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 177 178 public: 179 typedef _Tp value_type; 180 typedef typename _Tp_alloc_type::pointer pointer; 181 typedef typename _Tp_alloc_type::const_pointer const_pointer; 182 typedef typename _Tp_alloc_type::reference reference; 183 typedef typename _Tp_alloc_type::const_reference const_reference; 184 typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; 185 typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> 186 const_iterator; 187 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 188 typedef std::reverse_iterator<iterator> reverse_iterator; 189 typedef size_t size_type; 190 typedef ptrdiff_t difference_type; 191 typedef _Alloc allocator_type; 192 193 protected: 194 using _Base::_M_allocate; 195 using _Base::_M_deallocate; 196 using _Base::_M_impl; 197 using _Base::_M_get_Tp_allocator; 198 199 public: 200 // [23.2.4.1] construct/copy/destroy 201 // (assign() and get_allocator() are also listed in this section) 202 /** 203 * @brief Default constructor creates no elements. 204 */ 205 vector() 206 : _Base() { } 207 208 explicit 209 vector(const allocator_type& __a) 210 : _Base(__a) 211 { } 212 213 /** 214 * @brief Create a %vector with copies of an exemplar element. 215 * @param n The number of elements to initially create. 216 * @param value An element to copy. 217 * 218 * This constructor fills the %vector with @a n copies of @a value. 219 */ 220 explicit 221 vector(size_type __n, const value_type& __value = value_type(), 222 const allocator_type& __a = allocator_type()) 223 : _Base(__n, __a) 224 { 225 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 226 _M_get_Tp_allocator()); 227 this->_M_impl._M_finish = this->_M_impl._M_start + __n; 228 } 229 230 /** 231 * @brief %Vector copy constructor. 232 * @param x A %vector of identical element and allocator types. 233 * 234 * The newly-created %vector uses a copy of the allocation 235 * object used by @a x. All the elements of @a x are copied, 236 * but any extra memory in 237 * @a x (for fast expansion) will not be copied. 238 */ 239 vector(const vector& __x) 240 : _Base(__x.size(), __x._M_get_Tp_allocator()) 241 { this->_M_impl._M_finish = 242 std::__uninitialized_copy_a(__x.begin(), __x.end(), 243 this->_M_impl._M_start, 244 _M_get_Tp_allocator()); 245 } 246 247 /** 248 * @brief Builds a %vector from a range. 249 * @param first An input iterator. 250 * @param last An input iterator. 251 * 252 * Create a %vector consisting of copies of the elements from 253 * [first,last). 254 * 255 * If the iterators are forward, bidirectional, or 256 * random-access, then this will call the elements' copy 257 * constructor N times (where N is distance(first,last)) and do 258 * no memory reallocation. But if only input iterators are 259 * used, then this will do at most 2N calls to the copy 260 * constructor, and logN memory reallocations. 261 */ 262 template<typename _InputIterator> 263 vector(_InputIterator __first, _InputIterator __last, 264 const allocator_type& __a = allocator_type()) 265 : _Base(__a) 266 { 267 // Check whether it's an integral type. If so, it's not an iterator. 268 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 269 _M_initialize_dispatch(__first, __last, _Integral()); 270 } 271 272 /** 273 * The dtor only erases the elements, and note that if the 274 * elements themselves are pointers, the pointed-to memory is 275 * not touched in any way. Managing the pointer is the user's 276 * responsibilty. 277 */ 278 ~vector() 279 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 280 _M_get_Tp_allocator()); } 281 282 /** 283 * @brief %Vector assignment operator. 284 * @param x A %vector of identical element and allocator types. 285 * 286 * All the elements of @a x are copied, but any extra memory in 287 * @a x (for fast expansion) will not be copied. Unlike the 288 * copy constructor, the allocator object is not copied. 289 */ 290 vector& 291 operator=(const vector& __x); 292 293 /** 294 * @brief Assigns a given value to a %vector. 295 * @param n Number of elements to be assigned. 296 * @param val Value to be assigned. 297 * 298 * This function fills a %vector with @a n copies of the given 299 * value. Note that the assignment completely changes the 300 * %vector and that the resulting %vector's size is the same as 301 * the number of elements assigned. Old data may be lost. 302 */ 303 void 304 assign(size_type __n, const value_type& __val) 305 { _M_fill_assign(__n, __val); } 306 307 /** 308 * @brief Assigns a range to a %vector. 309 * @param first An input iterator. 310 * @param last An input iterator. 311 * 312 * This function fills a %vector with copies of the elements in the 313 * range [first,last). 314 * 315 * Note that the assignment completely changes the %vector and 316 * that the resulting %vector's size is the same as the number 317 * of elements assigned. Old data may be lost. 318 */ 319 template<typename _InputIterator> 320 void 321 assign(_InputIterator __first, _InputIterator __last) 322 { 323 // Check whether it's an integral type. If so, it's not an iterator. 324 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 325 _M_assign_dispatch(__first, __last, _Integral()); 326 } 327 328 /// Get a copy of the memory allocation object. 329 using _Base::get_allocator; 330 331 // iterators 332 /** 333 * Returns a read/write iterator that points to the first 334 * element in the %vector. Iteration is done in ordinary 335 * element order. 336 */ 337 iterator 338 begin() 339 { return iterator(this->_M_impl._M_start); } 340 341 /** 342 * Returns a read-only (constant) iterator that points to the 343 * first element in the %vector. Iteration is done in ordinary 344 * element order. 345 */ 346 const_iterator 347 begin() const 348 { return const_iterator(this->_M_impl._M_start); } 349 350 /** 351 * Returns a read/write iterator that points one past the last 352 * element in the %vector. Iteration is done in ordinary 353 * element order. 354 */ 355 iterator 356 end() 357 { return iterator(this->_M_impl._M_finish); } 358 359 /** 360 * Returns a read-only (constant) iterator that points one past 361 * the last element in the %vector. Iteration is done in 362 * ordinary element order. 363 */ 364 const_iterator 365 end() const 366 { return const_iterator(this->_M_impl._M_finish); } 367 368 /** 369 * Returns a read/write reverse iterator that points to the 370 * last element in the %vector. Iteration is done in reverse 371 * element order. 372 */ 373 reverse_iterator 374 rbegin() 375 { return reverse_iterator(end()); } 376 377 /** 378 * Returns a read-only (constant) reverse iterator that points 379 * to the last element in the %vector. Iteration is done in 380 * reverse element order. 381 */ 382 const_reverse_iterator 383 rbegin() const 384 { return const_reverse_iterator(end()); } 385 386 /** 387 * Returns a read/write reverse iterator that points to one 388 * before the first element in the %vector. Iteration is done 389 * in reverse element order. 390 */ 391 reverse_iterator 392 rend() 393 { return reverse_iterator(begin()); } 394 395 /** 396 * Returns a read-only (constant) reverse iterator that points 397 * to one before the first element in the %vector. Iteration 398 * is done in reverse element order. 399 */ 400 const_reverse_iterator 401 rend() const 402 { return const_reverse_iterator(begin()); } 403 404 // [23.2.4.2] capacity 405 /** Returns the number of elements in the %vector. */ 406 size_type 407 size() const 408 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 409 410 /** Returns the size() of the largest possible %vector. */ 411 size_type 412 max_size() const 413 { return _M_get_Tp_allocator().max_size(); } 414 415 /** 416 * @brief Resizes the %vector to the specified number of elements. 417 * @param new_size Number of elements the %vector should contain. 418 * @param x Data with which new elements should be populated. 419 * 420 * This function will %resize the %vector to the specified 421 * number of elements. If the number is smaller than the 422 * %vector's current size the %vector is truncated, otherwise 423 * the %vector is extended and new elements are populated with 424 * given data. 425 */ 426 void 427 resize(size_type __new_size, value_type __x = value_type()) 428 { 429 if (__new_size < size()) 430 _M_erase_at_end(this->_M_impl._M_start + __new_size); 431 else 432 insert(end(), __new_size - size(), __x); 433 } 434 435 /** 436 * Returns the total number of elements that the %vector can 437 * hold before needing to allocate more memory. 438 */ 439 size_type 440 capacity() const 441 { return size_type(this->_M_impl._M_end_of_storage 442 - this->_M_impl._M_start); } 443 444 /** 445 * Returns true if the %vector is empty. (Thus begin() would 446 * equal end().) 447 */ 448 bool 449 empty() const 450 { return begin() == end(); } 451 452 /** 453 * @brief Attempt to preallocate enough memory for specified number of 454 * elements. 455 * @param n Number of elements required. 456 * @throw std::length_error If @a n exceeds @c max_size(). 457 * 458 * This function attempts to reserve enough memory for the 459 * %vector to hold the specified number of elements. If the 460 * number requested is more than max_size(), length_error is 461 * thrown. 462 * 463 * The advantage of this function is that if optimal code is a 464 * necessity and the user can determine the number of elements 465 * that will be required, the user can reserve the memory in 466 * %advance, and thus prevent a possible reallocation of memory 467 * and copying of %vector data. 468 */ 469 void 470 reserve(size_type __n); 471 472 // element access 473 /** 474 * @brief Subscript access to the data contained in the %vector. 475 * @param n The index of the element for which data should be 476 * accessed. 477 * @return Read/write reference to data. 478 * 479 * This operator allows for easy, array-style, data access. 480 * Note that data access with this operator is unchecked and 481 * out_of_range lookups are not defined. (For checked lookups 482 * see at().) 483 */ 484 reference 485 operator[](size_type __n) 486 { return *(this->_M_impl._M_start + __n); } 487 488 /** 489 * @brief Subscript access to the data contained in the %vector. 490 * @param n The index of the element for which data should be 491 * accessed. 492 * @return Read-only (constant) reference to data. 493 * 494 * This operator allows for easy, array-style, data access. 495 * Note that data access with this operator is unchecked and 496 * out_of_range lookups are not defined. (For checked lookups 497 * see at().) 498 */ 499 const_reference 500 operator[](size_type __n) const 501 { return *(this->_M_impl._M_start + __n); } 502 503 protected: 504 /// @if maint Safety check used only from at(). @endif 505 void 506 _M_range_check(size_type __n) const 507 { 508 if (__n >= this->size()) 509 __throw_out_of_range(__N("vector::_M_range_check")); 510 } 511 512 public: 513 /** 514 * @brief Provides access to the data contained in the %vector. 515 * @param n The index of the element for which data should be 516 * accessed. 517 * @return Read/write reference to data. 518 * @throw std::out_of_range If @a n is an invalid index. 519 * 520 * This function provides for safer data access. The parameter 521 * is first checked that it is in the range of the vector. The 522 * function throws out_of_range if the check fails. 523 */ 524 reference 525 at(size_type __n) 526 { 527 _M_range_check(__n); 528 return (*this)[__n]; 529 } 530 531 /** 532 * @brief Provides access to the data contained in the %vector. 533 * @param n The index of the element for which data should be 534 * accessed. 535 * @return Read-only (constant) reference to data. 536 * @throw std::out_of_range If @a n is an invalid index. 537 * 538 * This function provides for safer data access. The parameter 539 * is first checked that it is in the range of the vector. The 540 * function throws out_of_range if the check fails. 541 */ 542 const_reference 543 at(size_type __n) const 544 { 545 _M_range_check(__n); 546 return (*this)[__n]; 547 } 548 549 /** 550 * Returns a read/write reference to the data at the first 551 * element of the %vector. 552 */ 553 reference 554 front() 555 { return *begin(); } 556 557 /** 558 * Returns a read-only (constant) reference to the data at the first 559 * element of the %vector. 560 */ 561 const_reference 562 front() const 563 { return *begin(); } 564 565 /** 566 * Returns a read/write reference to the data at the last 567 * element of the %vector. 568 */ 569 reference 570 back() 571 { return *(end() - 1); } 572 573 /** 574 * Returns a read-only (constant) reference to the data at the 575 * last element of the %vector. 576 */ 577 const_reference 578 back() const 579 { return *(end() - 1); } 580 581 // _GLIBCXX_RESOLVE_LIB_DEFECTS 582 // DR 464. Suggestion for new member functions in standard containers. 583 // data access 584 /** 585 * Returns a pointer such that [data(), data() + size()) is a valid 586 * range. For a non-empty %vector, data() == &front(). 587 */ 588 pointer 589 data() 590 { return pointer(this->_M_impl._M_start); } 591 592 const_pointer 593 data() const 594 { return const_pointer(this->_M_impl._M_start); } 595 596 // [23.2.4.3] modifiers 597 /** 598 * @brief Add data to the end of the %vector. 599 * @param x Data to be added. 600 * 601 * This is a typical stack operation. The function creates an 602 * element at the end of the %vector and assigns the given data 603 * to it. Due to the nature of a %vector this operation can be 604 * done in constant time if the %vector has preallocated space 605 * available. 606 */ 607 void 608 push_back(const value_type& __x) 609 { 610 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 611 { 612 this->_M_impl.construct(this->_M_impl._M_finish, __x); 613 ++this->_M_impl._M_finish; 614 } 615 else 616 _M_insert_aux(end(), __x); 617 } 618 619 /** 620 * @brief Removes last element. 621 * 622 * This is a typical stack operation. It shrinks the %vector by one. 623 * 624 * Note that no data is returned, and if the last element's 625 * data is needed, it should be retrieved before pop_back() is 626 * called. 627 */ 628 void 629 pop_back() 630 { 631 --this->_M_impl._M_finish; 632 this->_M_impl.destroy(this->_M_impl._M_finish); 633 } 634 635 /** 636 * @brief Inserts given value into %vector before specified iterator. 637 * @param position An iterator into the %vector. 638 * @param x Data to be inserted. 639 * @return An iterator that points to the inserted data. 640 * 641 * This function will insert a copy of the given value before 642 * the specified location. Note that this kind of operation 643 * could be expensive for a %vector and if it is frequently 644 * used the user should consider using std::list. 645 */ 646 iterator 647 insert(iterator __position, const value_type& __x); 648 649 /** 650 * @brief Inserts a number of copies of given data into the %vector. 651 * @param position An iterator into the %vector. 652 * @param n Number of elements to be inserted. 653 * @param x Data to be inserted. 654 * 655 * This function will insert a specified number of copies of 656 * the given data before the location specified by @a position. 657 * 658 * Note that this kind of operation could be expensive for a 659 * %vector and if it is frequently used the user should 660 * consider using std::list. 661 */ 662 void 663 insert(iterator __position, size_type __n, const value_type& __x) 664 { _M_fill_insert(__position, __n, __x); } 665 666 /** 667 * @brief Inserts a range into the %vector. 668 * @param position An iterator into the %vector. 669 * @param first An input iterator. 670 * @param last An input iterator. 671 * 672 * This function will insert copies of the data in the range 673 * [first,last) into the %vector before the location specified 674 * by @a pos. 675 * 676 * Note that this kind of operation could be expensive for a 677 * %vector and if it is frequently used the user should 678 * consider using std::list. 679 */ 680 template<typename _InputIterator> 681 void 682 insert(iterator __position, _InputIterator __first, 683 _InputIterator __last) 684 { 685 // Check whether it's an integral type. If so, it's not an iterator. 686 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 687 _M_insert_dispatch(__position, __first, __last, _Integral()); 688 } 689 690 /** 691 * @brief Remove element at given position. 692 * @param position Iterator pointing to element to be erased. 693 * @return An iterator pointing to the next element (or end()). 694 * 695 * This function will erase the element at the given position and thus 696 * shorten the %vector by one. 697 * 698 * Note This operation could be expensive and if it is 699 * frequently used the user should consider using std::list. 700 * The user is also cautioned that this function only erases 701 * the element, and that if the element is itself a pointer, 702 * the pointed-to memory is not touched in any way. Managing 703 * the pointer is the user's responsibilty. 704 */ 705 iterator 706 erase(iterator __position); 707 708 /** 709 * @brief Remove a range of elements. 710 * @param first Iterator pointing to the first element to be erased. 711 * @param last Iterator pointing to one past the last element to be 712 * erased. 713 * @return An iterator pointing to the element pointed to by @a last 714 * prior to erasing (or end()). 715 * 716 * This function will erase the elements in the range [first,last) and 717 * shorten the %vector accordingly. 718 * 719 * Note This operation could be expensive and if it is 720 * frequently used the user should consider using std::list. 721 * The user is also cautioned that this function only erases 722 * the elements, and that if the elements themselves are 723 * pointers, the pointed-to memory is not touched in any way. 724 * Managing the pointer is the user's responsibilty. 725 */ 726 iterator 727 erase(iterator __first, iterator __last); 728 729 /** 730 * @brief Swaps data with another %vector. 731 * @param x A %vector of the same element and allocator types. 732 * 733 * This exchanges the elements between two vectors in constant time. 734 * (Three pointers, so it should be quite fast.) 735 * Note that the global std::swap() function is specialized such that 736 * std::swap(v1,v2) will feed to this function. 737 */ 738 void 739 swap(vector& __x) 740 { 741 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 742 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 743 std::swap(this->_M_impl._M_end_of_storage, 744 __x._M_impl._M_end_of_storage); 745 746 // _GLIBCXX_RESOLVE_LIB_DEFECTS 747 // 431. Swapping containers with unequal allocators. 748 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 749 __x._M_get_Tp_allocator()); 750 } 751 752 /** 753 * Erases all the elements. Note that this function only erases the 754 * elements, and that if the elements themselves are pointers, the 755 * pointed-to memory is not touched in any way. Managing the pointer is 756 * the user's responsibilty. 757 */ 758 void 759 clear() 760 { _M_erase_at_end(this->_M_impl._M_start); } 761 762 protected: 763 /** 764 * @if maint 765 * Memory expansion handler. Uses the member allocation function to 766 * obtain @a n bytes of memory, and then copies [first,last) into it. 767 * @endif 768 */ 769 template<typename _ForwardIterator> 770 pointer 771 _M_allocate_and_copy(size_type __n, 772 _ForwardIterator __first, _ForwardIterator __last) 773 { 774 pointer __result = this->_M_allocate(__n); 775 try 776 { 777 std::__uninitialized_copy_a(__first, __last, __result, 778 _M_get_Tp_allocator()); 779 return __result; 780 } 781 catch(...) 782 { 783 _M_deallocate(__result, __n); 784 __throw_exception_again; 785 } 786 } 787 788 789 // Internal constructor functions follow. 790 791 // Called by the range constructor to implement [23.1.1]/9 792 template<typename _Integer> 793 void 794 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 795 { 796 this->_M_impl._M_start = _M_allocate(__n); 797 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 798 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 799 _M_get_Tp_allocator()); 800 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 801 } 802 803 // Called by the range constructor to implement [23.1.1]/9 804 template<typename _InputIterator> 805 void 806 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 807 __false_type) 808 { 809 typedef typename std::iterator_traits<_InputIterator>:: 810 iterator_category _IterCategory; 811 _M_range_initialize(__first, __last, _IterCategory()); 812 } 813 814 // Called by the second initialize_dispatch above 815 template<typename _InputIterator> 816 void 817 _M_range_initialize(_InputIterator __first, 818 _InputIterator __last, std::input_iterator_tag) 819 { 820 for (; __first != __last; ++__first) 821 push_back(*__first); 822 } 823 824 // Called by the second initialize_dispatch above 825 template<typename _ForwardIterator> 826 void 827 _M_range_initialize(_ForwardIterator __first, 828 _ForwardIterator __last, std::forward_iterator_tag) 829 { 830 const size_type __n = std::distance(__first, __last); 831 this->_M_impl._M_start = this->_M_allocate(__n); 832 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 833 this->_M_impl._M_finish = 834 std::__uninitialized_copy_a(__first, __last, 835 this->_M_impl._M_start, 836 _M_get_Tp_allocator()); 837 } 838 839 840 // Internal assign functions follow. The *_aux functions do the actual 841 // assignment work for the range versions. 842 843 // Called by the range assign to implement [23.1.1]/9 844 template<typename _Integer> 845 void 846 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 847 { 848 _M_fill_assign(static_cast<size_type>(__n), 849 static_cast<value_type>(__val)); 850 } 851 852 // Called by the range assign to implement [23.1.1]/9 853 template<typename _InputIterator> 854 void 855 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 856 __false_type) 857 { 858 typedef typename std::iterator_traits<_InputIterator>:: 859 iterator_category _IterCategory; 860 _M_assign_aux(__first, __last, _IterCategory()); 861 } 862 863 // Called by the second assign_dispatch above 864 template<typename _InputIterator> 865 void 866 _M_assign_aux(_InputIterator __first, _InputIterator __last, 867 std::input_iterator_tag); 868 869 // Called by the second assign_dispatch above 870 template<typename _ForwardIterator> 871 void 872 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 873 std::forward_iterator_tag); 874 875 // Called by assign(n,t), and the range assign when it turns out 876 // to be the same thing. 877 void 878 _M_fill_assign(size_type __n, const value_type& __val); 879 880 881 // Internal insert functions follow. 882 883 // Called by the range insert to implement [23.1.1]/9 884 template<typename _Integer> 885 void 886 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 887 __true_type) 888 { 889 _M_fill_insert(__pos, static_cast<size_type>(__n), 890 static_cast<value_type>(__val)); 891 } 892 893 // Called by the range insert to implement [23.1.1]/9 894 template<typename _InputIterator> 895 void 896 _M_insert_dispatch(iterator __pos, _InputIterator __first, 897 _InputIterator __last, __false_type) 898 { 899 typedef typename std::iterator_traits<_InputIterator>:: 900 iterator_category _IterCategory; 901 _M_range_insert(__pos, __first, __last, _IterCategory()); 902 } 903 904 // Called by the second insert_dispatch above 905 template<typename _InputIterator> 906 void 907 _M_range_insert(iterator __pos, _InputIterator __first, 908 _InputIterator __last, std::input_iterator_tag); 909 910 // Called by the second insert_dispatch above 911 template<typename _ForwardIterator> 912 void 913 _M_range_insert(iterator __pos, _ForwardIterator __first, 914 _ForwardIterator __last, std::forward_iterator_tag); 915 916 // Called by insert(p,n,x), and the range insert when it turns out to be 917 // the same thing. 918 void 919 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 920 921 // Called by insert(p,x) 922 void 923 _M_insert_aux(iterator __position, const value_type& __x); 924 925 // Internal erase functions follow. 926 927 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 928 // _M_assign_aux. 929 void 930 _M_erase_at_end(pointer __pos) 931 { 932 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 933 this->_M_impl._M_finish = __pos; 934 } 935 }; 936 937 938 /** 939 * @brief Vector equality comparison. 940 * @param x A %vector. 941 * @param y A %vector of the same type as @a x. 942 * @return True iff the size and elements of the vectors are equal. 943 * 944 * This is an equivalence relation. It is linear in the size of the 945 * vectors. Vectors are considered equivalent if their sizes are equal, 946 * and if corresponding elements compare equal. 947 */ 948 template<typename _Tp, typename _Alloc> 949 inline bool 950 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 951 { return (__x.size() == __y.size() 952 && std::equal(__x.begin(), __x.end(), __y.begin())); } 953 954 /** 955 * @brief Vector ordering relation. 956 * @param x A %vector. 957 * @param y A %vector of the same type as @a x. 958 * @return True iff @a x is lexicographically less than @a y. 959 * 960 * This is a total ordering relation. It is linear in the size of the 961 * vectors. The elements must be comparable with @c <. 962 * 963 * See std::lexicographical_compare() for how the determination is made. 964 */ 965 template<typename _Tp, typename _Alloc> 966 inline bool 967 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 968 { return std::lexicographical_compare(__x.begin(), __x.end(), 969 __y.begin(), __y.end()); } 970 971 /// Based on operator== 972 template<typename _Tp, typename _Alloc> 973 inline bool 974 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 975 { return !(__x == __y); } 976 977 /// Based on operator< 978 template<typename _Tp, typename _Alloc> 979 inline bool 980 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 981 { return __y < __x; } 982 983 /// Based on operator< 984 template<typename _Tp, typename _Alloc> 985 inline bool 986 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 987 { return !(__y < __x); } 988 989 /// Based on operator< 990 template<typename _Tp, typename _Alloc> 991 inline bool 992 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 993 { return !(__x < __y); } 994 995 /// See std::vector::swap(). 996 template<typename _Tp, typename _Alloc> 997 inline void 998 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 999 { __x.swap(__y); } 1000 1001_GLIBCXX_END_NESTED_NAMESPACE 1002 1003#endif /* _VECTOR_H */ 1004