vector.tcc revision 132720
1208625Sjkim// Vector implementation (out of line) -*- C++ -*- 2208625Sjkim 3208625Sjkim// Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. 4208625Sjkim// 5208625Sjkim// This file is part of the GNU ISO C++ Library. This library is free 6208625Sjkim// software; you can redistribute it and/or modify it under the 7217365Sjkim// terms of the GNU General Public License as published by the 8306536Sjkim// Free Software Foundation; either version 2, or (at your option) 9208625Sjkim// any later version. 10208625Sjkim 11217365Sjkim// This library is distributed in the hope that it will be useful, 12217365Sjkim// but WITHOUT ANY WARRANTY; without even the implied warranty of 13217365Sjkim// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14217365Sjkim// GNU General Public License for more details. 15217365Sjkim 16217365Sjkim// You should have received a copy of the GNU General Public License along 17217365Sjkim// with this library; see the file COPYING. If not, write to the Free 18217365Sjkim// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19217365Sjkim// USA. 20217365Sjkim 21217365Sjkim// As a special exception, you may use this file as part of a free software 22217365Sjkim// library without restriction. Specifically, if other files instantiate 23217365Sjkim// templates or use macros or inline functions from this file, or you compile 24217365Sjkim// this file and link it with other files to produce an executable, this 25208625Sjkim// file does not by itself cause the resulting executable to be covered by 26217365Sjkim// the GNU General Public License. This exception does not however 27217365Sjkim// invalidate any other reasons why the executable file might be covered by 28217365Sjkim// the GNU General Public License. 29208625Sjkim 30217365Sjkim/* 31217365Sjkim * 32217365Sjkim * Copyright (c) 1994 33217365Sjkim * Hewlett-Packard Company 34217365Sjkim * 35217365Sjkim * Permission to use, copy, modify, distribute and sell this software 36217365Sjkim * and its documentation for any purpose is hereby granted without fee, 37217365Sjkim * provided that the above copyright notice appear in all copies and 38217365Sjkim * that both that copyright notice and this permission notice appear 39217365Sjkim * in supporting documentation. Hewlett-Packard Company makes no 40217365Sjkim * representations about the suitability of this software for any 41217365Sjkim * purpose. It is provided "as is" without express or implied warranty. 42217365Sjkim * 43208625Sjkim * 44209746Sjkim * Copyright (c) 1996 45209746Sjkim * Silicon Graphics Computer Systems, Inc. 46208625Sjkim * 47208625Sjkim * Permission to use, copy, modify, distribute and sell this software 48208625Sjkim * and its documentation for any purpose is hereby granted without fee, 49208625Sjkim * provided that the above copyright notice appear in all copies and 50208625Sjkim * that both that copyright notice and this permission notice appear 51208625Sjkim * in supporting documentation. Silicon Graphics makes no 52208625Sjkim * representations about the suitability of this software for any 53208625Sjkim * purpose. It is provided "as is" without express or implied warranty. 54208625Sjkim */ 55208625Sjkim 56208625Sjkim/** @file vector.tcc 57208625Sjkim * This is an internal header file, included by other library headers. 58208625Sjkim * You should not attempt to use it directly. 59208625Sjkim */ 60208625Sjkim 61208625Sjkim#ifndef _VECTOR_TCC 62208625Sjkim#define _VECTOR_TCC 1 63208625Sjkim 64208625Sjkimnamespace _GLIBCXX_STD 65208625Sjkim{ 66208625Sjkim template<typename _Tp, typename _Alloc> 67208625Sjkim void 68208625Sjkim vector<_Tp,_Alloc>:: 69208625Sjkim reserve(size_type __n) 70208625Sjkim { 71208625Sjkim if (__n > this->max_size()) 72208625Sjkim __throw_length_error(__N("vector::reserve")); 73208625Sjkim if (this->capacity() < __n) 74281075Sdim { 75208625Sjkim const size_type __old_size = size(); 76208625Sjkim pointer __tmp = _M_allocate_and_copy(__n, 77281075Sdim this->_M_impl._M_start, 78208625Sjkim this->_M_impl._M_finish); 79208625Sjkim std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 80208625Sjkim _M_deallocate(this->_M_impl._M_start, 81281075Sdim this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 82281075Sdim this->_M_impl._M_start = __tmp; 83306536Sjkim this->_M_impl._M_finish = __tmp + __old_size; 84208625Sjkim this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 85208625Sjkim } 86208625Sjkim } 87208625Sjkim 88208625Sjkim template<typename _Tp, typename _Alloc> 89208625Sjkim typename vector<_Tp,_Alloc>::iterator 90208625Sjkim vector<_Tp,_Alloc>:: 91208625Sjkim insert(iterator __position, const value_type& __x) 92208625Sjkim { 93208625Sjkim size_type __n = __position - begin(); 94208625Sjkim if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage && __position == end()) 95208625Sjkim { 96208625Sjkim std::_Construct(this->_M_impl._M_finish, __x); 97208625Sjkim ++this->_M_impl._M_finish; 98208625Sjkim } 99208625Sjkim else 100208625Sjkim _M_insert_aux(__position, __x); 101208625Sjkim return begin() + __n; 102208625Sjkim } 103208625Sjkim 104208625Sjkim template<typename _Tp, typename _Alloc> 105208625Sjkim typename vector<_Tp,_Alloc>::iterator 106208625Sjkim vector<_Tp,_Alloc>:: 107208625Sjkim erase(iterator __position) 108208625Sjkim { 109208625Sjkim if (__position + 1 != end()) 110208625Sjkim std::copy(__position + 1, end(), __position); 111208625Sjkim --this->_M_impl._M_finish; 112208625Sjkim std::_Destroy(this->_M_impl._M_finish); 113208625Sjkim return __position; 114208625Sjkim } 115245582Sjkim 116208625Sjkim template<typename _Tp, typename _Alloc> 117208625Sjkim typename vector<_Tp,_Alloc>::iterator 118208625Sjkim vector<_Tp,_Alloc>:: 119208625Sjkim erase(iterator __first, iterator __last) 120208625Sjkim { 121208625Sjkim iterator __i(copy(__last, end(), __first)); 122208625Sjkim std::_Destroy(__i, end()); 123208625Sjkim this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first); 124208625Sjkim return __first; 125208625Sjkim } 126208625Sjkim 127208625Sjkim template<typename _Tp, typename _Alloc> 128208625Sjkim vector<_Tp,_Alloc>& 129208625Sjkim vector<_Tp,_Alloc>:: 130208625Sjkim operator=(const vector<_Tp,_Alloc>& __x) 131208625Sjkim { 132208625Sjkim if (&__x != this) 133208625Sjkim { 134208625Sjkim const size_type __xlen = __x.size(); 135208625Sjkim if (__xlen > capacity()) 136208625Sjkim { 137208625Sjkim pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); 138208625Sjkim std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 139208625Sjkim _M_deallocate(this->_M_impl._M_start, 140208625Sjkim this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 141208625Sjkim this->_M_impl._M_start = __tmp; 142208625Sjkim this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 143208625Sjkim } 144208625Sjkim else if (size() >= __xlen) 145208625Sjkim { 146208625Sjkim iterator __i(copy(__x.begin(), __x.end(), begin())); 147208625Sjkim std::_Destroy(__i, end()); 148208625Sjkim } 149208625Sjkim else 150208625Sjkim { 151208625Sjkim std::copy(__x.begin(), __x.begin() + size(), this->_M_impl._M_start); 152208625Sjkim std::uninitialized_copy(__x.begin() + size(), __x.end(), this->_M_impl._M_finish); 153208625Sjkim } 154208625Sjkim this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 155208625Sjkim } 156208625Sjkim return *this; 157208625Sjkim } 158208625Sjkim 159208625Sjkim template<typename _Tp, typename _Alloc> 160208625Sjkim void 161208625Sjkim vector<_Tp,_Alloc>:: 162208625Sjkim _M_fill_assign(size_t __n, const value_type& __val) 163208625Sjkim { 164208625Sjkim if (__n > capacity()) 165208625Sjkim { 166208625Sjkim vector __tmp(__n, __val, get_allocator()); 167208625Sjkim __tmp.swap(*this); 168208625Sjkim } 169208625Sjkim else if (__n > size()) 170208625Sjkim { 171208625Sjkim std::fill(begin(), end(), __val); 172208625Sjkim this->_M_impl._M_finish 173208625Sjkim = std::uninitialized_fill_n(this->_M_impl._M_finish, __n - size(), __val); 174208625Sjkim } 175208625Sjkim else 176208625Sjkim erase(fill_n(begin(), __n, __val), end()); 177208625Sjkim } 178208625Sjkim 179208625Sjkim template<typename _Tp, typename _Alloc> template<typename _InputIterator> 180208625Sjkim void 181208625Sjkim vector<_Tp,_Alloc>:: 182208625Sjkim _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag) 183208625Sjkim { 184208625Sjkim iterator __cur(begin()); 185208625Sjkim for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 186208625Sjkim *__cur = *__first; 187208625Sjkim if (__first == __last) 188208625Sjkim erase(__cur, end()); 189208625Sjkim else 190208625Sjkim insert(end(), __first, __last); 191208625Sjkim } 192208625Sjkim 193208625Sjkim template<typename _Tp, typename _Alloc> template<typename _ForwardIterator> 194208625Sjkim void 195208625Sjkim vector<_Tp,_Alloc>:: 196208625Sjkim _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 197208625Sjkim forward_iterator_tag) 198208625Sjkim { 199208625Sjkim size_type __len = std::distance(__first, __last); 200208625Sjkim 201208625Sjkim if (__len > capacity()) 202208625Sjkim { 203208625Sjkim pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 204208625Sjkim std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 205208625Sjkim _M_deallocate(this->_M_impl._M_start, 206208625Sjkim this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 207208625Sjkim this->_M_impl._M_start = __tmp; 208208625Sjkim this->_M_impl._M_end_of_storage = this->_M_impl._M_finish = this->_M_impl._M_start + __len; 209208625Sjkim } 210208625Sjkim else if (size() >= __len) 211208625Sjkim { 212208625Sjkim iterator __new_finish(copy(__first, __last, this->_M_impl._M_start)); 213208625Sjkim std::_Destroy(__new_finish, end()); 214208625Sjkim this->_M_impl._M_finish = __new_finish.base(); 215208625Sjkim } 216208625Sjkim else 217208625Sjkim { 218208625Sjkim _ForwardIterator __mid = __first; 219208625Sjkim std::advance(__mid, size()); 220208625Sjkim std::copy(__first, __mid, this->_M_impl._M_start); 221208625Sjkim this->_M_impl._M_finish = std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish); 222208625Sjkim } 223208625Sjkim } 224208625Sjkim 225208625Sjkim template<typename _Tp, typename _Alloc> 226208625Sjkim void 227208625Sjkim vector<_Tp,_Alloc>:: 228208625Sjkim _M_insert_aux(iterator __position, const _Tp& __x) 229208625Sjkim { 230208625Sjkim if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 231208625Sjkim { 232208625Sjkim std::_Construct(this->_M_impl._M_finish, *(this->_M_impl._M_finish - 1)); 233208625Sjkim ++this->_M_impl._M_finish; 234208625Sjkim _Tp __x_copy = __x; 235208625Sjkim std::copy_backward(__position, 236208625Sjkim iterator(this->_M_impl._M_finish-2), 237208625Sjkim iterator(this->_M_impl._M_finish-1)); 238208625Sjkim *__position = __x_copy; 239208625Sjkim } 240208625Sjkim else 241208625Sjkim { 242208625Sjkim const size_type __old_size = size(); 243208625Sjkim const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 244208625Sjkim iterator __new_start(this->_M_allocate(__len)); 245208625Sjkim iterator __new_finish(__new_start); 246208625Sjkim try 247208625Sjkim { 248208625Sjkim __new_finish = std::uninitialized_copy(iterator(this->_M_impl._M_start), 249208625Sjkim __position, 250208625Sjkim __new_start); 251208625Sjkim std::_Construct(__new_finish.base(), __x); 252208625Sjkim ++__new_finish; 253208625Sjkim __new_finish = std::uninitialized_copy(__position, 254208625Sjkim iterator(this->_M_impl._M_finish), 255208625Sjkim __new_finish); 256208625Sjkim } 257208625Sjkim catch(...) 258208625Sjkim { 259208625Sjkim std::_Destroy(__new_start,__new_finish); 260208625Sjkim _M_deallocate(__new_start.base(),__len); 261208625Sjkim __throw_exception_again; 262208625Sjkim } 263208625Sjkim std::_Destroy(begin(), end()); 264208625Sjkim _M_deallocate(this->_M_impl._M_start, 265208625Sjkim this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 266208625Sjkim this->_M_impl._M_start = __new_start.base(); 267208625Sjkim this->_M_impl._M_finish = __new_finish.base(); 268208625Sjkim this->_M_impl._M_end_of_storage = __new_start.base() + __len; 269208625Sjkim } 270208625Sjkim } 271208625Sjkim 272208625Sjkim template<typename _Tp, typename _Alloc> 273208625Sjkim void 274208625Sjkim vector<_Tp,_Alloc>:: 275208625Sjkim _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 276208625Sjkim { 277208625Sjkim if (__n != 0) 278208625Sjkim { 279208625Sjkim if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n) 280208625Sjkim { 281208625Sjkim value_type __x_copy = __x; 282208625Sjkim const size_type __elems_after = end() - __position; 283208625Sjkim iterator __old_finish(this->_M_impl._M_finish); 284208625Sjkim if (__elems_after > __n) 285208625Sjkim { 286208625Sjkim std::uninitialized_copy(this->_M_impl._M_finish - __n, 287208625Sjkim this->_M_impl._M_finish, 288208625Sjkim this->_M_impl._M_finish); 289208625Sjkim this->_M_impl._M_finish += __n; 290208625Sjkim std::copy_backward(__position, __old_finish - __n, __old_finish); 291208625Sjkim std::fill(__position, __position + __n, __x_copy); 292220663Sjkim } 293220663Sjkim else 294208625Sjkim { 295208625Sjkim std::uninitialized_fill_n(this->_M_impl._M_finish, 296208625Sjkim __n - __elems_after, 297208625Sjkim __x_copy); 298208625Sjkim this->_M_impl._M_finish += __n - __elems_after; 299208625Sjkim std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish); 300228110Sjkim this->_M_impl._M_finish += __elems_after; 301228110Sjkim std::fill(__position, __old_finish, __x_copy); 302228110Sjkim } 303228110Sjkim } 304228110Sjkim else 305220663Sjkim { 306220663Sjkim const size_type __old_size = size(); 307220663Sjkim const size_type __len = __old_size + std::max(__old_size, __n); 308220663Sjkim iterator __new_start(this->_M_allocate(__len)); 309220663Sjkim iterator __new_finish(__new_start); 310208625Sjkim try 311220663Sjkim { 312220663Sjkim __new_finish = std::uninitialized_copy(begin(), __position, 313220663Sjkim __new_start); 314220663Sjkim __new_finish = std::uninitialized_fill_n(__new_finish, __n, __x); 315250838Sjkim __new_finish = std::uninitialized_copy(__position, end(), 316220663Sjkim __new_finish); 317220663Sjkim } 318220663Sjkim catch(...) 319220663Sjkim { 320250838Sjkim std::_Destroy(__new_start,__new_finish); 321220663Sjkim _M_deallocate(__new_start.base(),__len); 322220663Sjkim __throw_exception_again; 323220663Sjkim } 324284460Sjkim std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 325284460Sjkim _M_deallocate(this->_M_impl._M_start, 326284460Sjkim this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 327284460Sjkim this->_M_impl._M_start = __new_start.base(); 328284460Sjkim this->_M_impl._M_finish = __new_finish.base(); 329220663Sjkim this->_M_impl._M_end_of_storage = __new_start.base() + __len; 330250838Sjkim } 331220663Sjkim } 332220663Sjkim } 333220663Sjkim 334220663Sjkim template<typename _Tp, typename _Alloc> template<typename _InputIterator> 335220663Sjkim void 336220663Sjkim vector<_Tp,_Alloc>:: 337220663Sjkim _M_range_insert(iterator __pos, 338220663Sjkim _InputIterator __first, _InputIterator __last, 339220663Sjkim input_iterator_tag) 340220663Sjkim { 341220663Sjkim for ( ; __first != __last; ++__first) 342220663Sjkim { 343220663Sjkim __pos = insert(__pos, *__first); 344208625Sjkim ++__pos; 345208625Sjkim } 346208625Sjkim } 347220663Sjkim 348220663Sjkim template<typename _Tp, typename _Alloc> template<typename _ForwardIterator> 349220663Sjkim void 350220663Sjkim vector<_Tp,_Alloc>:: 351220663Sjkim _M_range_insert(iterator __position,_ForwardIterator __first, 352220663Sjkim _ForwardIterator __last, forward_iterator_tag) 353220663Sjkim { 354220663Sjkim if (__first != __last) 355220663Sjkim { 356220663Sjkim size_type __n = std::distance(__first, __last); 357208625Sjkim if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n) 358208625Sjkim { 359208625Sjkim const size_type __elems_after = end() - __position; 360208625Sjkim iterator __old_finish(this->_M_impl._M_finish); 361208625Sjkim if (__elems_after > __n) 362208625Sjkim { 363208625Sjkim std::uninitialized_copy(this->_M_impl._M_finish - __n, 364208625Sjkim this->_M_impl._M_finish, 365208625Sjkim this->_M_impl._M_finish); 366208625Sjkim this->_M_impl._M_finish += __n; 367208625Sjkim std::copy_backward(__position, __old_finish - __n, __old_finish); 368208625Sjkim std::copy(__first, __last, __position); 369208625Sjkim } 370208625Sjkim else 371208625Sjkim { 372208625Sjkim _ForwardIterator __mid = __first; 373208625Sjkim std::advance(__mid, __elems_after); 374208625Sjkim std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish); 375208625Sjkim this->_M_impl._M_finish += __n - __elems_after; 376208625Sjkim std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish); 377208625Sjkim this->_M_impl._M_finish += __elems_after; 378208625Sjkim std::copy(__first, __mid, __position); 379208625Sjkim } 380208625Sjkim } 381208625Sjkim else 382306536Sjkim { 383208625Sjkim const size_type __old_size = size(); 384208625Sjkim const size_type __len = __old_size + std::max(__old_size, __n); 385 iterator __new_start(this->_M_allocate(__len)); 386 iterator __new_finish(__new_start); 387 try 388 { 389 __new_finish = std::uninitialized_copy(iterator(this->_M_impl._M_start), 390 __position, __new_start); 391 __new_finish = std::uninitialized_copy(__first, __last, 392 __new_finish); 393 __new_finish = std::uninitialized_copy(__position, 394 iterator(this->_M_impl._M_finish), 395 __new_finish); 396 } 397 catch(...) 398 { 399 std::_Destroy(__new_start,__new_finish); 400 _M_deallocate(__new_start.base(), __len); 401 __throw_exception_again; 402 } 403 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 404 _M_deallocate(this->_M_impl._M_start, 405 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 406 this->_M_impl._M_start = __new_start.base(); 407 this->_M_impl._M_finish = __new_finish.base(); 408 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 409 } 410 } 411 } 412} // namespace std 413 414#endif /* _VECTOR_TCC */ 415