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