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