197403Sobrien// Vector implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_vector.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien */ 6197403Sobrien 62132720Skan#ifndef _VECTOR_H 63132720Skan#define _VECTOR_H 1 6497403Sobrien 6597403Sobrien#include <bits/stl_iterator_base_funcs.h> 6697403Sobrien#include <bits/functexcept.h> 6797403Sobrien#include <bits/concept_check.h> 6897403Sobrien 69169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 70169691Skan 7197403Sobrien /** 72117397Skan * @if maint 73132720Skan * See bits/stl_deque.h's _Deque_base for an explanation. 74117397Skan * @endif 7597403Sobrien */ 76132720Skan template<typename _Tp, typename _Alloc> 77132720Skan struct _Vector_base 78117397Skan { 79169691Skan typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 80169691Skan 81132720Skan struct _Vector_impl 82169691Skan : public _Tp_alloc_type 83169691Skan { 84132720Skan _Tp* _M_start; 85132720Skan _Tp* _M_finish; 86132720Skan _Tp* _M_end_of_storage; 87236829Spfg 88236829Spfg _Vector_impl() 89236829Spfg : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) 90236829Spfg { } 91236829Spfg 92169691Skan _Vector_impl(_Tp_alloc_type const& __a) 93169691Skan : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 94132720Skan { } 95132720Skan }; 96132720Skan 97117397Skan public: 98132720Skan typedef _Alloc allocator_type; 9997403Sobrien 100169691Skan _Tp_alloc_type& 101169691Skan _M_get_Tp_allocator() 102169691Skan { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 103169691Skan 104169691Skan const _Tp_alloc_type& 105169691Skan _M_get_Tp_allocator() const 106169691Skan { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 107169691Skan 108117397Skan allocator_type 109169691Skan get_allocator() const 110169691Skan { return allocator_type(_M_get_Tp_allocator()); } 111132720Skan 112236829Spfg _Vector_base() 113236829Spfg : _M_impl() { } 114236829Spfg 115169691Skan _Vector_base(const allocator_type& __a) 116169691Skan : _M_impl(__a) 117117397Skan { } 118132720Skan 119132720Skan _Vector_base(size_t __n, const allocator_type& __a) 120169691Skan : _M_impl(__a) 121132720Skan { 122258429Spfg if (__n) 123258429Spfg { 124258429Spfg this->_M_impl._M_start = this->_M_allocate(__n); 125258429Spfg this->_M_impl._M_finish = this->_M_impl._M_start; 126258429Spfg this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 127258429Spfg } 128132720Skan } 129132720Skan 130132720Skan ~_Vector_base() 131169691Skan { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage 132169691Skan - this->_M_impl._M_start); } 133132720Skan 134132720Skan public: 135132720Skan _Vector_impl _M_impl; 136132720Skan 137117397Skan _Tp* 138169691Skan _M_allocate(size_t __n) 139169691Skan { return _M_impl.allocate(__n); } 140132720Skan 141117397Skan void 142117397Skan _M_deallocate(_Tp* __p, size_t __n) 143169691Skan { 144169691Skan if (__p) 145169691Skan _M_impl.deallocate(__p, __n); 146169691Skan } 147117397Skan }; 14897403Sobrien 149132720Skan 15097403Sobrien /** 151132720Skan * @brief A standard container which offers fixed time access to 152132720Skan * individual elements in any order. 15397403Sobrien * 154117397Skan * @ingroup Containers 155117397Skan * @ingroup Sequences 15697403Sobrien * 157117397Skan * Meets the requirements of a <a href="tables.html#65">container</a>, a 158117397Skan * <a href="tables.html#66">reversible container</a>, and a 159117397Skan * <a href="tables.html#67">sequence</a>, including the 160117397Skan * <a href="tables.html#68">optional sequence requirements</a> with the 161117397Skan * %exception of @c push_front and @c pop_front. 16297403Sobrien * 163132720Skan * In some terminology a %vector can be described as a dynamic 164132720Skan * C-style array, it offers fast and efficient access to individual 165132720Skan * elements in any order and saves the user from worrying about 166132720Skan * memory and size allocation. Subscripting ( @c [] ) access is 167132720Skan * also provided as with C-style arrays. 16897403Sobrien */ 169169691Skan template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 170117397Skan class vector : protected _Vector_base<_Tp, _Alloc> 171117397Skan { 172117397Skan // Concept requirements. 173169691Skan typedef typename _Alloc::value_type _Alloc_value_type; 174132720Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 175169691Skan __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 176169691Skan 177169691Skan typedef _Vector_base<_Tp, _Alloc> _Base; 178169691Skan typedef vector<_Tp, _Alloc> vector_type; 179169691Skan typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 180132720Skan 181117397Skan public: 182132720Skan typedef _Tp value_type; 183169691Skan typedef typename _Tp_alloc_type::pointer pointer; 184169691Skan typedef typename _Tp_alloc_type::const_pointer const_pointer; 185169691Skan typedef typename _Tp_alloc_type::reference reference; 186169691Skan typedef typename _Tp_alloc_type::const_reference const_reference; 187117397Skan typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; 188117397Skan typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> 189117397Skan const_iterator; 190132720Skan typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 191132720Skan typedef std::reverse_iterator<iterator> reverse_iterator; 192132720Skan typedef size_t size_type; 193132720Skan typedef ptrdiff_t difference_type; 194169691Skan typedef _Alloc allocator_type; 195132720Skan 196117397Skan protected: 197117397Skan using _Base::_M_allocate; 198117397Skan using _Base::_M_deallocate; 199132720Skan using _Base::_M_impl; 200169691Skan using _Base::_M_get_Tp_allocator; 201132720Skan 202117397Skan public: 203117397Skan // [23.2.4.1] construct/copy/destroy 204117397Skan // (assign() and get_allocator() are also listed in this section) 205117397Skan /** 206117397Skan * @brief Default constructor creates no elements. 207117397Skan */ 208236829Spfg vector() 209236829Spfg : _Base() { } 210236829Spfg 211117397Skan explicit 212236829Spfg vector(const allocator_type& __a) 213169691Skan : _Base(__a) 214169691Skan { } 215132720Skan 216117397Skan /** 217117397Skan * @brief Create a %vector with copies of an exemplar element. 218117397Skan * @param n The number of elements to initially create. 219117397Skan * @param value An element to copy. 220132720Skan * 221117397Skan * This constructor fills the %vector with @a n copies of @a value. 222117397Skan */ 223169691Skan explicit 224169691Skan vector(size_type __n, const value_type& __value = value_type(), 225117397Skan const allocator_type& __a = allocator_type()) 226117397Skan : _Base(__n, __a) 227169691Skan { 228169691Skan std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 229169691Skan _M_get_Tp_allocator()); 230169691Skan this->_M_impl._M_finish = this->_M_impl._M_start + __n; 231169691Skan } 232132720Skan 233117397Skan /** 234117397Skan * @brief %Vector copy constructor. 235117397Skan * @param x A %vector of identical element and allocator types. 236132720Skan * 237117397Skan * The newly-created %vector uses a copy of the allocation 238117397Skan * object used by @a x. All the elements of @a x are copied, 239117397Skan * but any extra memory in 240117397Skan * @a x (for fast expansion) will not be copied. 241117397Skan */ 242117397Skan vector(const vector& __x) 243169691Skan : _Base(__x.size(), __x._M_get_Tp_allocator()) 244169691Skan { this->_M_impl._M_finish = 245169691Skan std::__uninitialized_copy_a(__x.begin(), __x.end(), 246169691Skan this->_M_impl._M_start, 247169691Skan _M_get_Tp_allocator()); 248132720Skan } 249132720Skan 250117397Skan /** 251117397Skan * @brief Builds a %vector from a range. 252117397Skan * @param first An input iterator. 253117397Skan * @param last An input iterator. 254132720Skan * 255117397Skan * Create a %vector consisting of copies of the elements from 256117397Skan * [first,last). 257117397Skan * 258132720Skan * If the iterators are forward, bidirectional, or 259132720Skan * random-access, then this will call the elements' copy 260132720Skan * constructor N times (where N is distance(first,last)) and do 261132720Skan * no memory reallocation. But if only input iterators are 262132720Skan * used, then this will do at most 2N calls to the copy 263132720Skan * constructor, and logN memory reallocations. 264117397Skan */ 265117397Skan template<typename _InputIterator> 266117397Skan vector(_InputIterator __first, _InputIterator __last, 267117397Skan const allocator_type& __a = allocator_type()) 26897403Sobrien : _Base(__a) 269117397Skan { 270117397Skan // Check whether it's an integral type. If so, it's not an iterator. 271169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 272117397Skan _M_initialize_dispatch(__first, __last, _Integral()); 273117397Skan } 274132720Skan 275117397Skan /** 276132720Skan * The dtor only erases the elements, and note that if the 277132720Skan * elements themselves are pointers, the pointed-to memory is 278132720Skan * not touched in any way. Managing the pointer is the user's 279132720Skan * responsibilty. 280117397Skan */ 281169691Skan ~vector() 282169691Skan { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 283169691Skan _M_get_Tp_allocator()); } 284132720Skan 285117397Skan /** 286117397Skan * @brief %Vector assignment operator. 287117397Skan * @param x A %vector of identical element and allocator types. 288132720Skan * 289117397Skan * All the elements of @a x are copied, but any extra memory in 290117397Skan * @a x (for fast expansion) will not be copied. Unlike the 291117397Skan * copy constructor, the allocator object is not copied. 292117397Skan */ 293117397Skan vector& 294117397Skan operator=(const vector& __x); 295132720Skan 296117397Skan /** 297117397Skan * @brief Assigns a given value to a %vector. 298117397Skan * @param n Number of elements to be assigned. 299117397Skan * @param val Value to be assigned. 300117397Skan * 301117397Skan * This function fills a %vector with @a n copies of the given 302117397Skan * value. Note that the assignment completely changes the 303117397Skan * %vector and that the resulting %vector's size is the same as 304117397Skan * the number of elements assigned. Old data may be lost. 305117397Skan */ 306117397Skan void 307132720Skan assign(size_type __n, const value_type& __val) 308117397Skan { _M_fill_assign(__n, __val); } 309132720Skan 310117397Skan /** 311117397Skan * @brief Assigns a range to a %vector. 312117397Skan * @param first An input iterator. 313117397Skan * @param last An input iterator. 314117397Skan * 315117397Skan * This function fills a %vector with copies of the elements in the 316117397Skan * range [first,last). 317117397Skan * 318117397Skan * Note that the assignment completely changes the %vector and 319117397Skan * that the resulting %vector's size is the same as the number 320117397Skan * of elements assigned. Old data may be lost. 321117397Skan */ 322117397Skan template<typename _InputIterator> 323117397Skan void 324117397Skan assign(_InputIterator __first, _InputIterator __last) 325117397Skan { 326117397Skan // Check whether it's an integral type. If so, it's not an iterator. 327169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 328117397Skan _M_assign_dispatch(__first, __last, _Integral()); 329117397Skan } 330132720Skan 331117397Skan /// Get a copy of the memory allocation object. 332132720Skan using _Base::get_allocator; 333132720Skan 334117397Skan // iterators 335117397Skan /** 336132720Skan * Returns a read/write iterator that points to the first 337132720Skan * element in the %vector. Iteration is done in ordinary 338132720Skan * element order. 339117397Skan */ 340117397Skan iterator 341169691Skan begin() 342169691Skan { return iterator(this->_M_impl._M_start); } 343132720Skan 344117397Skan /** 345117397Skan * Returns a read-only (constant) iterator that points to the 346117397Skan * first element in the %vector. Iteration is done in ordinary 347117397Skan * element order. 348117397Skan */ 349117397Skan const_iterator 350169691Skan begin() const 351169691Skan { return const_iterator(this->_M_impl._M_start); } 352132720Skan 353117397Skan /** 354117397Skan * Returns a read/write iterator that points one past the last 355117397Skan * element in the %vector. Iteration is done in ordinary 356117397Skan * element order. 357117397Skan */ 358117397Skan iterator 359169691Skan end() 360169691Skan { return iterator(this->_M_impl._M_finish); } 361132720Skan 362117397Skan /** 363132720Skan * Returns a read-only (constant) iterator that points one past 364132720Skan * the last element in the %vector. Iteration is done in 365132720Skan * ordinary element order. 366117397Skan */ 367117397Skan const_iterator 368169691Skan end() const 369169691Skan { return const_iterator(this->_M_impl._M_finish); } 370132720Skan 371117397Skan /** 372117397Skan * Returns a read/write reverse iterator that points to the 373117397Skan * last element in the %vector. Iteration is done in reverse 374117397Skan * element order. 375117397Skan */ 376117397Skan reverse_iterator 377169691Skan rbegin() 378169691Skan { return reverse_iterator(end()); } 379132720Skan 380117397Skan /** 381117397Skan * Returns a read-only (constant) reverse iterator that points 382117397Skan * to the last element in the %vector. Iteration is done in 383117397Skan * reverse element order. 384117397Skan */ 385117397Skan const_reverse_iterator 386169691Skan rbegin() const 387169691Skan { return const_reverse_iterator(end()); } 388132720Skan 389117397Skan /** 390132720Skan * Returns a read/write reverse iterator that points to one 391132720Skan * before the first element in the %vector. Iteration is done 392132720Skan * in reverse element order. 393117397Skan */ 394117397Skan reverse_iterator 395169691Skan rend() 396169691Skan { return reverse_iterator(begin()); } 397132720Skan 398117397Skan /** 399117397Skan * Returns a read-only (constant) reverse iterator that points 400117397Skan * to one before the first element in the %vector. Iteration 401117397Skan * is done in reverse element order. 402117397Skan */ 403117397Skan const_reverse_iterator 404169691Skan rend() const 405169691Skan { return const_reverse_iterator(begin()); } 406132720Skan 407117397Skan // [23.2.4.2] capacity 408117397Skan /** Returns the number of elements in the %vector. */ 409117397Skan size_type 410169691Skan size() const 411169691Skan { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } 412132720Skan 413117397Skan /** Returns the size() of the largest possible %vector. */ 414117397Skan size_type 415169691Skan max_size() const 416169691Skan { return _M_get_Tp_allocator().max_size(); } 417132720Skan 418117397Skan /** 419117397Skan * @brief Resizes the %vector to the specified number of elements. 420117397Skan * @param new_size Number of elements the %vector should contain. 421117397Skan * @param x Data with which new elements should be populated. 422117397Skan * 423117397Skan * This function will %resize the %vector to the specified 424117397Skan * number of elements. If the number is smaller than the 425117397Skan * %vector's current size the %vector is truncated, otherwise 426117397Skan * the %vector is extended and new elements are populated with 427117397Skan * given data. 428117397Skan */ 429117397Skan void 430169691Skan resize(size_type __new_size, value_type __x = value_type()) 431117397Skan { 432117397Skan if (__new_size < size()) 433169691Skan _M_erase_at_end(this->_M_impl._M_start + __new_size); 434117397Skan else 435117397Skan insert(end(), __new_size - size(), __x); 436117397Skan } 437132720Skan 438117397Skan /** 439132720Skan * Returns the total number of elements that the %vector can 440132720Skan * hold before needing to allocate more memory. 441117397Skan */ 442117397Skan size_type 443117397Skan capacity() const 444169691Skan { return size_type(this->_M_impl._M_end_of_storage 445169691Skan - this->_M_impl._M_start); } 446132720Skan 447117397Skan /** 448117397Skan * Returns true if the %vector is empty. (Thus begin() would 449117397Skan * equal end().) 450117397Skan */ 451117397Skan bool 452169691Skan empty() const 453169691Skan { return begin() == end(); } 454132720Skan 455117397Skan /** 456117397Skan * @brief Attempt to preallocate enough memory for specified number of 457117397Skan * elements. 458117397Skan * @param n Number of elements required. 459117397Skan * @throw std::length_error If @a n exceeds @c max_size(). 460117397Skan * 461117397Skan * This function attempts to reserve enough memory for the 462117397Skan * %vector to hold the specified number of elements. If the 463117397Skan * number requested is more than max_size(), length_error is 464117397Skan * thrown. 465117397Skan * 466117397Skan * The advantage of this function is that if optimal code is a 467117397Skan * necessity and the user can determine the number of elements 468117397Skan * that will be required, the user can reserve the memory in 469117397Skan * %advance, and thus prevent a possible reallocation of memory 470117397Skan * and copying of %vector data. 471117397Skan */ 472117397Skan void 473117397Skan reserve(size_type __n); 474132720Skan 475117397Skan // element access 476117397Skan /** 477117397Skan * @brief Subscript access to the data contained in the %vector. 478132720Skan * @param n The index of the element for which data should be 479132720Skan * accessed. 480117397Skan * @return Read/write reference to data. 481117397Skan * 482117397Skan * This operator allows for easy, array-style, data access. 483117397Skan * Note that data access with this operator is unchecked and 484117397Skan * out_of_range lookups are not defined. (For checked lookups 485117397Skan * see at().) 486117397Skan */ 487117397Skan reference 488169691Skan operator[](size_type __n) 489169691Skan { return *(this->_M_impl._M_start + __n); } 490132720Skan 491117397Skan /** 492117397Skan * @brief Subscript access to the data contained in the %vector. 493117397Skan * @param n The index of the element for which data should be 494117397Skan * accessed. 495117397Skan * @return Read-only (constant) reference to data. 496117397Skan * 497117397Skan * This operator allows for easy, array-style, data access. 498117397Skan * Note that data access with this operator is unchecked and 499117397Skan * out_of_range lookups are not defined. (For checked lookups 500117397Skan * see at().) 501117397Skan */ 502117397Skan const_reference 503169691Skan operator[](size_type __n) const 504169691Skan { return *(this->_M_impl._M_start + __n); } 505132720Skan 506117397Skan protected: 507117397Skan /// @if maint Safety check used only from at(). @endif 508117397Skan void 509117397Skan _M_range_check(size_type __n) const 510117397Skan { 511117397Skan if (__n >= this->size()) 512132720Skan __throw_out_of_range(__N("vector::_M_range_check")); 513117397Skan } 514132720Skan 515117397Skan public: 516117397Skan /** 517117397Skan * @brief Provides access to the data contained in the %vector. 518117397Skan * @param n The index of the element for which data should be 519117397Skan * accessed. 520117397Skan * @return Read/write reference to data. 521117397Skan * @throw std::out_of_range If @a n is an invalid index. 522117397Skan * 523132720Skan * This function provides for safer data access. The parameter 524132720Skan * is first checked that it is in the range of the vector. The 525132720Skan * function throws out_of_range if the check fails. 526117397Skan */ 527117397Skan reference 528169691Skan at(size_type __n) 529169691Skan { 530169691Skan _M_range_check(__n); 531169691Skan return (*this)[__n]; 532169691Skan } 533132720Skan 534117397Skan /** 535117397Skan * @brief Provides access to the data contained in the %vector. 536117397Skan * @param n The index of the element for which data should be 537117397Skan * accessed. 538117397Skan * @return Read-only (constant) reference to data. 539117397Skan * @throw std::out_of_range If @a n is an invalid index. 540117397Skan * 541117397Skan * This function provides for safer data access. The parameter 542117397Skan * is first checked that it is in the range of the vector. The 543117397Skan * function throws out_of_range if the check fails. 544117397Skan */ 545117397Skan const_reference 546169691Skan at(size_type __n) const 547169691Skan { 548169691Skan _M_range_check(__n); 549169691Skan return (*this)[__n]; 550169691Skan } 551132720Skan 552117397Skan /** 553117397Skan * Returns a read/write reference to the data at the first 554117397Skan * element of the %vector. 555117397Skan */ 556117397Skan reference 557169691Skan front() 558169691Skan { return *begin(); } 559132720Skan 560117397Skan /** 561117397Skan * Returns a read-only (constant) reference to the data at the first 562117397Skan * element of the %vector. 563117397Skan */ 564117397Skan const_reference 565169691Skan front() const 566169691Skan { return *begin(); } 567132720Skan 568117397Skan /** 569132720Skan * Returns a read/write reference to the data at the last 570132720Skan * element of the %vector. 571117397Skan */ 572117397Skan reference 573169691Skan back() 574169691Skan { return *(end() - 1); } 575169691Skan 576117397Skan /** 577132720Skan * Returns a read-only (constant) reference to the data at the 578132720Skan * last element of the %vector. 579117397Skan */ 580117397Skan const_reference 581169691Skan back() const 582169691Skan { return *(end() - 1); } 583132720Skan 584169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 585169691Skan // DR 464. Suggestion for new member functions in standard containers. 586169691Skan // data access 587169691Skan /** 588169691Skan * Returns a pointer such that [data(), data() + size()) is a valid 589169691Skan * range. For a non-empty %vector, data() == &front(). 590169691Skan */ 591169691Skan pointer 592169691Skan data() 593169691Skan { return pointer(this->_M_impl._M_start); } 594169691Skan 595169691Skan const_pointer 596169691Skan data() const 597169691Skan { return const_pointer(this->_M_impl._M_start); } 598169691Skan 599117397Skan // [23.2.4.3] modifiers 600117397Skan /** 601117397Skan * @brief Add data to the end of the %vector. 602117397Skan * @param x Data to be added. 603117397Skan * 604117397Skan * This is a typical stack operation. The function creates an 605117397Skan * element at the end of the %vector and assigns the given data 606117397Skan * to it. Due to the nature of a %vector this operation can be 607117397Skan * done in constant time if the %vector has preallocated space 608117397Skan * available. 609117397Skan */ 610117397Skan void 611117397Skan push_back(const value_type& __x) 612117397Skan { 613132720Skan if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 614117397Skan { 615169691Skan this->_M_impl.construct(this->_M_impl._M_finish, __x); 616132720Skan ++this->_M_impl._M_finish; 617117397Skan } 618117397Skan else 619117397Skan _M_insert_aux(end(), __x); 620117397Skan } 621132720Skan 622117397Skan /** 623117397Skan * @brief Removes last element. 624117397Skan * 625117397Skan * This is a typical stack operation. It shrinks the %vector by one. 626117397Skan * 627132720Skan * Note that no data is returned, and if the last element's 628132720Skan * data is needed, it should be retrieved before pop_back() is 629132720Skan * called. 630117397Skan */ 631117397Skan void 632117397Skan pop_back() 633117397Skan { 634132720Skan --this->_M_impl._M_finish; 635169691Skan this->_M_impl.destroy(this->_M_impl._M_finish); 636117397Skan } 637132720Skan 638117397Skan /** 639117397Skan * @brief Inserts given value into %vector before specified iterator. 640117397Skan * @param position An iterator into the %vector. 641117397Skan * @param x Data to be inserted. 642117397Skan * @return An iterator that points to the inserted data. 643117397Skan * 644117397Skan * This function will insert a copy of the given value before 645117397Skan * the specified location. Note that this kind of operation 646117397Skan * could be expensive for a %vector and if it is frequently 647117397Skan * used the user should consider using std::list. 648117397Skan */ 649117397Skan iterator 650117397Skan insert(iterator __position, const value_type& __x); 651132720Skan 652117397Skan /** 653117397Skan * @brief Inserts a number of copies of given data into the %vector. 654117397Skan * @param position An iterator into the %vector. 655117397Skan * @param n Number of elements to be inserted. 656117397Skan * @param x Data to be inserted. 657117397Skan * 658117397Skan * This function will insert a specified number of copies of 659117397Skan * the given data before the location specified by @a position. 660117397Skan * 661117397Skan * Note that this kind of operation could be expensive for a 662117397Skan * %vector and if it is frequently used the user should 663117397Skan * consider using std::list. 664117397Skan */ 665117397Skan void 666132720Skan insert(iterator __position, size_type __n, const value_type& __x) 667132720Skan { _M_fill_insert(__position, __n, __x); } 668132720Skan 669117397Skan /** 670117397Skan * @brief Inserts a range into the %vector. 671132720Skan * @param position An iterator into the %vector. 672117397Skan * @param first An input iterator. 673117397Skan * @param last An input iterator. 674117397Skan * 675117397Skan * This function will insert copies of the data in the range 676117397Skan * [first,last) into the %vector before the location specified 677117397Skan * by @a pos. 678117397Skan * 679117397Skan * Note that this kind of operation could be expensive for a 680117397Skan * %vector and if it is frequently used the user should 681117397Skan * consider using std::list. 682117397Skan */ 683117397Skan template<typename _InputIterator> 684117397Skan void 685132720Skan insert(iterator __position, _InputIterator __first, 686132720Skan _InputIterator __last) 687117397Skan { 688117397Skan // Check whether it's an integral type. If so, it's not an iterator. 689169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 690132720Skan _M_insert_dispatch(__position, __first, __last, _Integral()); 691117397Skan } 692132720Skan 693117397Skan /** 694117397Skan * @brief Remove element at given position. 695117397Skan * @param position Iterator pointing to element to be erased. 696117397Skan * @return An iterator pointing to the next element (or end()). 697117397Skan * 698117397Skan * This function will erase the element at the given position and thus 699117397Skan * shorten the %vector by one. 700117397Skan * 701117397Skan * Note This operation could be expensive and if it is 702117397Skan * frequently used the user should consider using std::list. 703117397Skan * The user is also cautioned that this function only erases 704117397Skan * the element, and that if the element is itself a pointer, 705117397Skan * the pointed-to memory is not touched in any way. Managing 706117397Skan * the pointer is the user's responsibilty. 707117397Skan */ 708117397Skan iterator 709117397Skan erase(iterator __position); 710132720Skan 711117397Skan /** 712117397Skan * @brief Remove a range of elements. 713117397Skan * @param first Iterator pointing to the first element to be erased. 714117397Skan * @param last Iterator pointing to one past the last element to be 715117397Skan * erased. 716117397Skan * @return An iterator pointing to the element pointed to by @a last 717117397Skan * prior to erasing (or end()). 718117397Skan * 719117397Skan * This function will erase the elements in the range [first,last) and 720117397Skan * shorten the %vector accordingly. 721117397Skan * 722117397Skan * Note This operation could be expensive and if it is 723117397Skan * frequently used the user should consider using std::list. 724117397Skan * The user is also cautioned that this function only erases 725117397Skan * the elements, and that if the elements themselves are 726117397Skan * pointers, the pointed-to memory is not touched in any way. 727117397Skan * Managing the pointer is the user's responsibilty. 728117397Skan */ 729117397Skan iterator 730117397Skan erase(iterator __first, iterator __last); 731132720Skan 732117397Skan /** 733117397Skan * @brief Swaps data with another %vector. 734117397Skan * @param x A %vector of the same element and allocator types. 735117397Skan * 736117397Skan * This exchanges the elements between two vectors in constant time. 737117397Skan * (Three pointers, so it should be quite fast.) 738117397Skan * Note that the global std::swap() function is specialized such that 739117397Skan * std::swap(v1,v2) will feed to this function. 740117397Skan */ 741117397Skan void 742117397Skan swap(vector& __x) 743117397Skan { 744132720Skan std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 745132720Skan std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 746169691Skan std::swap(this->_M_impl._M_end_of_storage, 747169691Skan __x._M_impl._M_end_of_storage); 748169691Skan 749169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 750169691Skan // 431. Swapping containers with unequal allocators. 751169691Skan std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 752169691Skan __x._M_get_Tp_allocator()); 753117397Skan } 754132720Skan 755117397Skan /** 756117397Skan * Erases all the elements. Note that this function only erases the 757117397Skan * elements, and that if the elements themselves are pointers, the 758117397Skan * pointed-to memory is not touched in any way. Managing the pointer is 759117397Skan * the user's responsibilty. 760117397Skan */ 761117397Skan void 762169691Skan clear() 763169691Skan { _M_erase_at_end(this->_M_impl._M_start); } 764132720Skan 765117397Skan protected: 766117397Skan /** 767117397Skan * @if maint 768117397Skan * Memory expansion handler. Uses the member allocation function to 769117397Skan * obtain @a n bytes of memory, and then copies [first,last) into it. 770117397Skan * @endif 771117397Skan */ 772117397Skan template<typename _ForwardIterator> 773117397Skan pointer 774117397Skan _M_allocate_and_copy(size_type __n, 775117397Skan _ForwardIterator __first, _ForwardIterator __last) 776117397Skan { 777132720Skan pointer __result = this->_M_allocate(__n); 778117397Skan try 779117397Skan { 780169691Skan std::__uninitialized_copy_a(__first, __last, __result, 781169691Skan _M_get_Tp_allocator()); 782117397Skan return __result; 783117397Skan } 784117397Skan catch(...) 785117397Skan { 786117397Skan _M_deallocate(__result, __n); 787117397Skan __throw_exception_again; 788117397Skan } 789117397Skan } 790132720Skan 791132720Skan 792117397Skan // Internal constructor functions follow. 793132720Skan 794117397Skan // Called by the range constructor to implement [23.1.1]/9 795117397Skan template<typename _Integer> 796117397Skan void 797117397Skan _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) 798117397Skan { 799132720Skan this->_M_impl._M_start = _M_allocate(__n); 800132720Skan this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 801169691Skan std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 802169691Skan _M_get_Tp_allocator()); 803169691Skan this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; 804117397Skan } 805132720Skan 806117397Skan // Called by the range constructor to implement [23.1.1]/9 807132720Skan template<typename _InputIterator> 808117397Skan void 809132720Skan _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 810117397Skan __false_type) 811117397Skan { 812169691Skan typedef typename std::iterator_traits<_InputIterator>:: 813169691Skan iterator_category _IterCategory; 81497403Sobrien _M_range_initialize(__first, __last, _IterCategory()); 81597403Sobrien } 816132720Skan 817117397Skan // Called by the second initialize_dispatch above 818117397Skan template<typename _InputIterator> 819117397Skan void 820117397Skan _M_range_initialize(_InputIterator __first, 821169691Skan _InputIterator __last, std::input_iterator_tag) 822117397Skan { 823169691Skan for (; __first != __last; ++__first) 824117397Skan push_back(*__first); 825117397Skan } 826132720Skan 827117397Skan // Called by the second initialize_dispatch above 828117397Skan template<typename _ForwardIterator> 829132720Skan void 830117397Skan _M_range_initialize(_ForwardIterator __first, 831169691Skan _ForwardIterator __last, std::forward_iterator_tag) 832117397Skan { 833169691Skan const size_type __n = std::distance(__first, __last); 834132720Skan this->_M_impl._M_start = this->_M_allocate(__n); 835132720Skan this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 836169691Skan this->_M_impl._M_finish = 837169691Skan std::__uninitialized_copy_a(__first, __last, 838169691Skan this->_M_impl._M_start, 839169691Skan _M_get_Tp_allocator()); 840117397Skan } 841132720Skan 842132720Skan 843117397Skan // Internal assign functions follow. The *_aux functions do the actual 844117397Skan // assignment work for the range versions. 845132720Skan 846117397Skan // Called by the range assign to implement [23.1.1]/9 847117397Skan template<typename _Integer> 848117397Skan void 849117397Skan _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 850117397Skan { 851117397Skan _M_fill_assign(static_cast<size_type>(__n), 852117397Skan static_cast<value_type>(__val)); 853117397Skan } 854132720Skan 855117397Skan // Called by the range assign to implement [23.1.1]/9 856132720Skan template<typename _InputIterator> 857117397Skan void 858132720Skan _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 859132720Skan __false_type) 860117397Skan { 861169691Skan typedef typename std::iterator_traits<_InputIterator>:: 862169691Skan iterator_category _IterCategory; 863117397Skan _M_assign_aux(__first, __last, _IterCategory()); 864117397Skan } 865132720Skan 866117397Skan // Called by the second assign_dispatch above 867117397Skan template<typename _InputIterator> 868132720Skan void 869117397Skan _M_assign_aux(_InputIterator __first, _InputIterator __last, 870169691Skan std::input_iterator_tag); 871132720Skan 872117397Skan // Called by the second assign_dispatch above 873117397Skan template<typename _ForwardIterator> 874132720Skan void 875117397Skan _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 876169691Skan std::forward_iterator_tag); 877132720Skan 878117397Skan // Called by assign(n,t), and the range assign when it turns out 879117397Skan // to be the same thing. 880117397Skan void 881117397Skan _M_fill_assign(size_type __n, const value_type& __val); 882132720Skan 883132720Skan 884117397Skan // Internal insert functions follow. 885132720Skan 886117397Skan // Called by the range insert to implement [23.1.1]/9 887117397Skan template<typename _Integer> 888117397Skan void 889117397Skan _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 890117397Skan __true_type) 891117397Skan { 892117397Skan _M_fill_insert(__pos, static_cast<size_type>(__n), 893117397Skan static_cast<value_type>(__val)); 894117397Skan } 895132720Skan 896117397Skan // Called by the range insert to implement [23.1.1]/9 897117397Skan template<typename _InputIterator> 898117397Skan void 899117397Skan _M_insert_dispatch(iterator __pos, _InputIterator __first, 900117397Skan _InputIterator __last, __false_type) 901117397Skan { 902169691Skan typedef typename std::iterator_traits<_InputIterator>:: 903169691Skan iterator_category _IterCategory; 904117397Skan _M_range_insert(__pos, __first, __last, _IterCategory()); 905117397Skan } 906132720Skan 907117397Skan // Called by the second insert_dispatch above 908117397Skan template<typename _InputIterator> 909117397Skan void 910132720Skan _M_range_insert(iterator __pos, _InputIterator __first, 911169691Skan _InputIterator __last, std::input_iterator_tag); 912132720Skan 913117397Skan // Called by the second insert_dispatch above 914117397Skan template<typename _ForwardIterator> 915117397Skan void 916132720Skan _M_range_insert(iterator __pos, _ForwardIterator __first, 917169691Skan _ForwardIterator __last, std::forward_iterator_tag); 918132720Skan 919117397Skan // Called by insert(p,n,x), and the range insert when it turns out to be 920117397Skan // the same thing. 921117397Skan void 922117397Skan _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 923132720Skan 924117397Skan // Called by insert(p,x) 925117397Skan void 926117397Skan _M_insert_aux(iterator __position, const value_type& __x); 927169691Skan 928169691Skan // Internal erase functions follow. 929169691Skan 930169691Skan // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, 931169691Skan // _M_assign_aux. 932169691Skan void 933169691Skan _M_erase_at_end(pointer __pos) 934169691Skan { 935169691Skan std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 936169691Skan this->_M_impl._M_finish = __pos; 937169691Skan } 938117397Skan }; 939132720Skan 940132720Skan 94197403Sobrien /** 942117397Skan * @brief Vector equality comparison. 943117397Skan * @param x A %vector. 944117397Skan * @param y A %vector of the same type as @a x. 945117397Skan * @return True iff the size and elements of the vectors are equal. 94697403Sobrien * 947117397Skan * This is an equivalence relation. It is linear in the size of the 948117397Skan * vectors. Vectors are considered equivalent if their sizes are equal, 949117397Skan * and if corresponding elements compare equal. 95097403Sobrien */ 951117397Skan template<typename _Tp, typename _Alloc> 952117397Skan inline bool 953169691Skan operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 954169691Skan { return (__x.size() == __y.size() 955169691Skan && std::equal(__x.begin(), __x.end(), __y.begin())); } 956132720Skan 95797403Sobrien /** 958117397Skan * @brief Vector ordering relation. 959117397Skan * @param x A %vector. 960117397Skan * @param y A %vector of the same type as @a x. 961132720Skan * @return True iff @a x is lexicographically less than @a y. 96297403Sobrien * 963117397Skan * This is a total ordering relation. It is linear in the size of the 964117397Skan * vectors. The elements must be comparable with @c <. 96597403Sobrien * 966132720Skan * See std::lexicographical_compare() for how the determination is made. 96797403Sobrien */ 968117397Skan template<typename _Tp, typename _Alloc> 969117397Skan inline bool 970169691Skan operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 971169691Skan { return std::lexicographical_compare(__x.begin(), __x.end(), 972169691Skan __y.begin(), __y.end()); } 973132720Skan 974117397Skan /// Based on operator== 975117397Skan template<typename _Tp, typename _Alloc> 976117397Skan inline bool 977169691Skan operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 978117397Skan { return !(__x == __y); } 979132720Skan 980117397Skan /// Based on operator< 981117397Skan template<typename _Tp, typename _Alloc> 982117397Skan inline bool 983169691Skan operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 984117397Skan { return __y < __x; } 985132720Skan 986117397Skan /// Based on operator< 987117397Skan template<typename _Tp, typename _Alloc> 988117397Skan inline bool 989169691Skan operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 990117397Skan { return !(__y < __x); } 991132720Skan 992117397Skan /// Based on operator< 993117397Skan template<typename _Tp, typename _Alloc> 994117397Skan inline bool 995169691Skan operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 996117397Skan { return !(__x < __y); } 997132720Skan 998117397Skan /// See std::vector::swap(). 999117397Skan template<typename _Tp, typename _Alloc> 1000117397Skan inline void 1001169691Skan swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 1002117397Skan { __x.swap(__y); } 100397403Sobrien 1004169691Skan_GLIBCXX_END_NESTED_NAMESPACE 1005169691Skan 1006132720Skan#endif /* _VECTOR_H */ 1007