vector.tcc revision 117397
1// Vector implementation (out of line) -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file vector.tcc 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_VECTOR_TCC 62#define __GLIBCPP_INTERNAL_VECTOR_TCC 63 64namespace std 65{ 66 template<typename _Tp, typename _Alloc> 67 void 68 vector<_Tp,_Alloc>:: 69 reserve(size_type __n) 70 { 71 if (__n > this->max_size()) 72 __throw_length_error("vector::reserve"); 73 if (this->capacity() < __n) 74 { 75 const size_type __old_size = size(); 76 pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); 77 _Destroy(_M_start, _M_finish); 78 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 79 _M_start = __tmp; 80 _M_finish = __tmp + __old_size; 81 _M_end_of_storage = _M_start + __n; 82 } 83 } 84 85 template<typename _Tp, typename _Alloc> 86 typename vector<_Tp,_Alloc>::iterator 87 vector<_Tp,_Alloc>:: 88 insert(iterator __position, const value_type& __x) 89 { 90 size_type __n = __position - begin(); 91 if (_M_finish != _M_end_of_storage && __position == end()) 92 { 93 _Construct(_M_finish, __x); 94 ++_M_finish; 95 } 96 else 97 _M_insert_aux(__position, __x); 98 return begin() + __n; 99 } 100 101 template<typename _Tp, typename _Alloc> 102 typename vector<_Tp,_Alloc>::iterator 103 vector<_Tp,_Alloc>:: 104 erase(iterator __position) 105 { 106 if (__position + 1 != end()) 107 copy(__position + 1, end(), __position); 108 --_M_finish; 109 _Destroy(_M_finish); 110 return __position; 111 } 112 113 template<typename _Tp, typename _Alloc> 114 typename vector<_Tp,_Alloc>::iterator 115 vector<_Tp,_Alloc>:: 116 erase(iterator __first, iterator __last) 117 { 118 iterator __i(copy(__last, end(), __first)); 119 _Destroy(__i, end()); 120 _M_finish = _M_finish - (__last - __first); 121 return __first; 122 } 123 124 template<typename _Tp, typename _Alloc> 125 vector<_Tp,_Alloc>& 126 vector<_Tp,_Alloc>:: 127 operator=(const vector<_Tp,_Alloc>& __x) 128 { 129 if (&__x != this) 130 { 131 const size_type __xlen = __x.size(); 132 if (__xlen > capacity()) 133 { 134 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); 135 _Destroy(_M_start, _M_finish); 136 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 137 _M_start = __tmp; 138 _M_end_of_storage = _M_start + __xlen; 139 } 140 else if (size() >= __xlen) 141 { 142 iterator __i(copy(__x.begin(), __x.end(), begin())); 143 _Destroy(__i, end()); 144 } 145 else 146 { 147 copy(__x.begin(), __x.begin() + size(), _M_start); 148 uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); 149 } 150 _M_finish = _M_start + __xlen; 151 } 152 return *this; 153 } 154 155 template<typename _Tp, typename _Alloc> 156 void 157 vector<_Tp,_Alloc>:: 158 _M_fill_assign(size_t __n, const value_type& __val) 159 { 160 if (__n > capacity()) 161 { 162 vector __tmp(__n, __val, get_allocator()); 163 __tmp.swap(*this); 164 } 165 else if (__n > size()) 166 { 167 fill(begin(), end(), __val); 168 _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val); 169 } 170 else 171 erase(fill_n(begin(), __n, __val), end()); 172 } 173 174 template<typename _Tp, typename _Alloc> template<typename _InputIter> 175 void 176 vector<_Tp,_Alloc>:: 177 _M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) 178 { 179 iterator __cur(begin()); 180 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 181 *__cur = *__first; 182 if (__first == __last) 183 erase(__cur, end()); 184 else 185 insert(end(), __first, __last); 186 } 187 188 template<typename _Tp, typename _Alloc> template<typename _ForwardIter> 189 void 190 vector<_Tp,_Alloc>:: 191 _M_assign_aux(_ForwardIter __first, _ForwardIter __last, 192 forward_iterator_tag) 193 { 194 size_type __len = distance(__first, __last); 195 196 if (__len > capacity()) 197 { 198 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 199 _Destroy(_M_start, _M_finish); 200 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 201 _M_start = __tmp; 202 _M_end_of_storage = _M_finish = _M_start + __len; 203 } 204 else if (size() >= __len) 205 { 206 iterator __new_finish(copy(__first, __last, _M_start)); 207 _Destroy(__new_finish, end()); 208 _M_finish = __new_finish.base(); 209 } 210 else 211 { 212 _ForwardIter __mid = __first; 213 advance(__mid, size()); 214 copy(__first, __mid, _M_start); 215 _M_finish = uninitialized_copy(__mid, __last, _M_finish); 216 } 217 } 218 219 template<typename _Tp, typename _Alloc> 220 void 221 vector<_Tp,_Alloc>:: 222 _M_insert_aux(iterator __position, const _Tp& __x) 223 { 224 if (_M_finish != _M_end_of_storage) 225 { 226 _Construct(_M_finish, *(_M_finish - 1)); 227 ++_M_finish; 228 _Tp __x_copy = __x; 229 copy_backward(__position, iterator(_M_finish-2), iterator(_M_finish-1)); 230 *__position = __x_copy; 231 } 232 else 233 { 234 const size_type __old_size = size(); 235 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 236 iterator __new_start(_M_allocate(__len)); 237 iterator __new_finish(__new_start); 238 try 239 { 240 __new_finish = uninitialized_copy(iterator(_M_start), __position, 241 __new_start); 242 _Construct(__new_finish.base(), __x); 243 ++__new_finish; 244 __new_finish = uninitialized_copy(__position, iterator(_M_finish), 245 __new_finish); 246 } 247 catch(...) 248 { 249 _Destroy(__new_start,__new_finish); 250 _M_deallocate(__new_start.base(),__len); 251 __throw_exception_again; 252 } 253 _Destroy(begin(), end()); 254 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 255 _M_start = __new_start.base(); 256 _M_finish = __new_finish.base(); 257 _M_end_of_storage = __new_start.base() + __len; 258 } 259 } 260 261 #ifdef _GLIBCPP_DEPRECATED 262 template<typename _Tp, typename _Alloc> 263 void 264 vector<_Tp,_Alloc>:: 265 _M_insert_aux(iterator __position) 266 { 267 if (_M_finish != _M_end_of_storage) 268 { 269 _Construct(_M_finish, *(_M_finish - 1)); 270 ++_M_finish; 271 copy_backward(__position, iterator(_M_finish - 2), 272 iterator(_M_finish - 1)); 273 *__position = value_type(); 274 } 275 else 276 { 277 const size_type __old_size = size(); 278 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 279 pointer __new_start = _M_allocate(__len); 280 pointer __new_finish = __new_start; 281 try 282 { 283 __new_finish = uninitialized_copy(iterator(_M_start), __position, 284 __new_start); 285 _Construct(__new_finish); 286 ++__new_finish; 287 __new_finish = uninitialized_copy(__position, iterator(_M_finish), 288 __new_finish); 289 } 290 catch(...) 291 { 292 _Destroy(__new_start,__new_finish); 293 _M_deallocate(__new_start,__len); 294 __throw_exception_again; 295 } 296 _Destroy(begin(), end()); 297 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 298 _M_start = __new_start; 299 _M_finish = __new_finish; 300 _M_end_of_storage = __new_start + __len; 301 } 302 } 303 #endif 304 305 template<typename _Tp, typename _Alloc> 306 void 307 vector<_Tp,_Alloc>:: 308 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 309 { 310 if (__n != 0) 311 { 312 if (size_type(_M_end_of_storage - _M_finish) >= __n) 313 { 314 value_type __x_copy = __x; 315 const size_type __elems_after = end() - __position; 316 iterator __old_finish(_M_finish); 317 if (__elems_after > __n) 318 { 319 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 320 _M_finish += __n; 321 copy_backward(__position, __old_finish - __n, __old_finish); 322 fill(__position, __position + __n, __x_copy); 323 } 324 else 325 { 326 uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy); 327 _M_finish += __n - __elems_after; 328 uninitialized_copy(__position, __old_finish, _M_finish); 329 _M_finish += __elems_after; 330 fill(__position, __old_finish, __x_copy); 331 } 332 } 333 else 334 { 335 const size_type __old_size = size(); 336 const size_type __len = __old_size + max(__old_size, __n); 337 iterator __new_start(_M_allocate(__len)); 338 iterator __new_finish(__new_start); 339 try 340 { 341 __new_finish = uninitialized_copy(begin(), __position, 342 __new_start); 343 __new_finish = uninitialized_fill_n(__new_finish, __n, __x); 344 __new_finish = uninitialized_copy(__position, end(), 345 __new_finish); 346 } 347 catch(...) 348 { 349 _Destroy(__new_start,__new_finish); 350 _M_deallocate(__new_start.base(),__len); 351 __throw_exception_again; 352 } 353 _Destroy(_M_start, _M_finish); 354 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 355 _M_start = __new_start.base(); 356 _M_finish = __new_finish.base(); 357 _M_end_of_storage = __new_start.base() + __len; 358 } 359 } 360 } 361 362 template<typename _Tp, typename _Alloc> template<typename _InputIterator> 363 void 364 vector<_Tp,_Alloc>:: 365 _M_range_insert(iterator __pos, 366 _InputIterator __first, _InputIterator __last, 367 input_iterator_tag) 368 { 369 for ( ; __first != __last; ++__first) 370 { 371 __pos = insert(__pos, *__first); 372 ++__pos; 373 } 374 } 375 376 template<typename _Tp, typename _Alloc> template<typename _ForwardIterator> 377 void 378 vector<_Tp,_Alloc>:: 379 _M_range_insert(iterator __position,_ForwardIterator __first, 380 _ForwardIterator __last, forward_iterator_tag) 381 { 382 if (__first != __last) 383 { 384 size_type __n = distance(__first, __last); 385 if (size_type(_M_end_of_storage - _M_finish) >= __n) 386 { 387 const size_type __elems_after = end() - __position; 388 iterator __old_finish(_M_finish); 389 if (__elems_after > __n) 390 { 391 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 392 _M_finish += __n; 393 copy_backward(__position, __old_finish - __n, __old_finish); 394 copy(__first, __last, __position); 395 } 396 else 397 { 398 _ForwardIterator __mid = __first; 399 advance(__mid, __elems_after); 400 uninitialized_copy(__mid, __last, _M_finish); 401 _M_finish += __n - __elems_after; 402 uninitialized_copy(__position, __old_finish, _M_finish); 403 _M_finish += __elems_after; 404 copy(__first, __mid, __position); 405 } 406 } 407 else 408 { 409 const size_type __old_size = size(); 410 const size_type __len = __old_size + max(__old_size, __n); 411 iterator __new_start(_M_allocate(__len)); 412 iterator __new_finish(__new_start); 413 try 414 { 415 __new_finish = uninitialized_copy(iterator(_M_start), 416 __position, __new_start); 417 __new_finish = uninitialized_copy(__first, __last, __new_finish); 418 __new_finish = uninitialized_copy(__position, iterator(_M_finish), 419 __new_finish); 420 } 421 catch(...) 422 { 423 _Destroy(__new_start,__new_finish); 424 _M_deallocate(__new_start.base(), __len); 425 __throw_exception_again; 426 } 427 _Destroy(_M_start, _M_finish); 428 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 429 _M_start = __new_start.base(); 430 _M_finish = __new_finish.base(); 431 _M_end_of_storage = __new_start.base() + __len; 432 } 433 } 434 } 435} // namespace std 436 437#endif /* __GLIBCPP_INTERNAL_VECTOR_TCC */ 438