1 // Vector implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003 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 _VECTOR_TCC 62 #define _VECTOR_TCC 1 63 64 namespace _GLIBCXX_STD 65 { 66 template<typename _Tp, typename _Alloc> 67 void 68 vector<_Tp,_Alloc>:: reserve(size_type __n)69 reserve(size_type __n) 70 { 71 if (__n > this->max_size()) 72 __throw_length_error(__N("vector::reserve")); 73 if (this->capacity() < __n) 74 { 75 const size_type __old_size = size(); 76 pointer __tmp = _M_allocate_and_copy(__n, 77 this->_M_impl._M_start, 78 this->_M_impl._M_finish); 79 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 80 _M_deallocate(this->_M_impl._M_start, 81 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 82 this->_M_impl._M_start = __tmp; 83 this->_M_impl._M_finish = __tmp + __old_size; 84 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 85 } 86 } 87 88 template<typename _Tp, typename _Alloc> 89 typename vector<_Tp,_Alloc>::iterator 90 vector<_Tp,_Alloc>:: insert(iterator __position,const value_type & __x)91 insert(iterator __position, const value_type& __x) 92 { 93 size_type __n = __position - begin(); 94 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage && __position == end()) 95 { 96 std::_Construct(this->_M_impl._M_finish, __x); 97 ++this->_M_impl._M_finish; 98 } 99 else 100 _M_insert_aux(__position, __x); 101 return begin() + __n; 102 } 103 104 template<typename _Tp, typename _Alloc> 105 typename vector<_Tp,_Alloc>::iterator 106 vector<_Tp,_Alloc>:: erase(iterator __position)107 erase(iterator __position) 108 { 109 if (__position + 1 != end()) 110 std::copy(__position + 1, end(), __position); 111 --this->_M_impl._M_finish; 112 std::_Destroy(this->_M_impl._M_finish); 113 return __position; 114 } 115 116 template<typename _Tp, typename _Alloc> 117 typename vector<_Tp,_Alloc>::iterator 118 vector<_Tp,_Alloc>:: erase(iterator __first,iterator __last)119 erase(iterator __first, iterator __last) 120 { 121 iterator __i(copy(__last, end(), __first)); 122 std::_Destroy(__i, end()); 123 this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first); 124 return __first; 125 } 126 127 template<typename _Tp, typename _Alloc> 128 vector<_Tp,_Alloc>& 129 vector<_Tp,_Alloc>:: operator =(const vector<_Tp,_Alloc> & __x)130 operator=(const vector<_Tp,_Alloc>& __x) 131 { 132 if (&__x != this) 133 { 134 const size_type __xlen = __x.size(); 135 if (__xlen > capacity()) 136 { 137 pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); 138 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 139 _M_deallocate(this->_M_impl._M_start, 140 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 141 this->_M_impl._M_start = __tmp; 142 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; 143 } 144 else if (size() >= __xlen) 145 { 146 iterator __i(copy(__x.begin(), __x.end(), begin())); 147 std::_Destroy(__i, end()); 148 } 149 else 150 { 151 std::copy(__x.begin(), __x.begin() + size(), this->_M_impl._M_start); 152 std::uninitialized_copy(__x.begin() + size(), __x.end(), this->_M_impl._M_finish); 153 } 154 this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; 155 } 156 return *this; 157 } 158 159 template<typename _Tp, typename _Alloc> 160 void 161 vector<_Tp,_Alloc>:: _M_fill_assign(size_t __n,const value_type & __val)162 _M_fill_assign(size_t __n, const value_type& __val) 163 { 164 if (__n > capacity()) 165 { 166 vector __tmp(__n, __val, get_allocator()); 167 __tmp.swap(*this); 168 } 169 else if (__n > size()) 170 { 171 std::fill(begin(), end(), __val); 172 this->_M_impl._M_finish 173 = std::uninitialized_fill_n(this->_M_impl._M_finish, __n - size(), __val); 174 } 175 else 176 erase(fill_n(begin(), __n, __val), end()); 177 } 178 179 template<typename _Tp, typename _Alloc> template<typename _InputIterator> 180 void 181 vector<_Tp,_Alloc>:: _M_assign_aux(_InputIterator __first,_InputIterator __last,input_iterator_tag)182 _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag) 183 { 184 iterator __cur(begin()); 185 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 186 *__cur = *__first; 187 if (__first == __last) 188 erase(__cur, end()); 189 else 190 insert(end(), __first, __last); 191 } 192 193 template<typename _Tp, typename _Alloc> template<typename _ForwardIterator> 194 void 195 vector<_Tp,_Alloc>:: _M_assign_aux(_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)196 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 197 forward_iterator_tag) 198 { 199 size_type __len = std::distance(__first, __last); 200 201 if (__len > capacity()) 202 { 203 pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); 204 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 205 _M_deallocate(this->_M_impl._M_start, 206 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 207 this->_M_impl._M_start = __tmp; 208 this->_M_impl._M_end_of_storage = this->_M_impl._M_finish = this->_M_impl._M_start + __len; 209 } 210 else if (size() >= __len) 211 { 212 iterator __new_finish(copy(__first, __last, this->_M_impl._M_start)); 213 std::_Destroy(__new_finish, end()); 214 this->_M_impl._M_finish = __new_finish.base(); 215 } 216 else 217 { 218 _ForwardIterator __mid = __first; 219 std::advance(__mid, size()); 220 std::copy(__first, __mid, this->_M_impl._M_start); 221 this->_M_impl._M_finish = std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish); 222 } 223 } 224 225 template<typename _Tp, typename _Alloc> 226 void 227 vector<_Tp,_Alloc>:: _M_insert_aux(iterator __position,const _Tp & __x)228 _M_insert_aux(iterator __position, const _Tp& __x) 229 { 230 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 231 { 232 std::_Construct(this->_M_impl._M_finish, *(this->_M_impl._M_finish - 1)); 233 ++this->_M_impl._M_finish; 234 _Tp __x_copy = __x; 235 std::copy_backward(__position, 236 iterator(this->_M_impl._M_finish-2), 237 iterator(this->_M_impl._M_finish-1)); 238 *__position = __x_copy; 239 } 240 else 241 { 242 const size_type __old_size = size(); 243 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 244 iterator __new_start(this->_M_allocate(__len)); 245 iterator __new_finish(__new_start); 246 try 247 { 248 __new_finish = std::uninitialized_copy(iterator(this->_M_impl._M_start), 249 __position, 250 __new_start); 251 std::_Construct(__new_finish.base(), __x); 252 ++__new_finish; 253 __new_finish = std::uninitialized_copy(__position, 254 iterator(this->_M_impl._M_finish), 255 __new_finish); 256 } 257 catch(...) 258 { 259 std::_Destroy(__new_start,__new_finish); 260 _M_deallocate(__new_start.base(),__len); 261 __throw_exception_again; 262 } 263 std::_Destroy(begin(), end()); 264 _M_deallocate(this->_M_impl._M_start, 265 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 266 this->_M_impl._M_start = __new_start.base(); 267 this->_M_impl._M_finish = __new_finish.base(); 268 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 269 } 270 } 271 272 template<typename _Tp, typename _Alloc> 273 void 274 vector<_Tp,_Alloc>:: _M_fill_insert(iterator __position,size_type __n,const value_type & __x)275 _M_fill_insert(iterator __position, size_type __n, const value_type& __x) 276 { 277 if (__n != 0) 278 { 279 if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n) 280 { 281 value_type __x_copy = __x; 282 const size_type __elems_after = end() - __position; 283 iterator __old_finish(this->_M_impl._M_finish); 284 if (__elems_after > __n) 285 { 286 std::uninitialized_copy(this->_M_impl._M_finish - __n, 287 this->_M_impl._M_finish, 288 this->_M_impl._M_finish); 289 this->_M_impl._M_finish += __n; 290 std::copy_backward(__position, __old_finish - __n, __old_finish); 291 std::fill(__position, __position + __n, __x_copy); 292 } 293 else 294 { 295 std::uninitialized_fill_n(this->_M_impl._M_finish, 296 __n - __elems_after, 297 __x_copy); 298 this->_M_impl._M_finish += __n - __elems_after; 299 std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish); 300 this->_M_impl._M_finish += __elems_after; 301 std::fill(__position, __old_finish, __x_copy); 302 } 303 } 304 else 305 { 306 const size_type __old_size = size(); 307 const size_type __len = __old_size + std::max(__old_size, __n); 308 iterator __new_start(this->_M_allocate(__len)); 309 iterator __new_finish(__new_start); 310 try 311 { 312 __new_finish = std::uninitialized_copy(begin(), __position, 313 __new_start); 314 __new_finish = std::uninitialized_fill_n(__new_finish, __n, __x); 315 __new_finish = std::uninitialized_copy(__position, end(), 316 __new_finish); 317 } 318 catch(...) 319 { 320 std::_Destroy(__new_start,__new_finish); 321 _M_deallocate(__new_start.base(),__len); 322 __throw_exception_again; 323 } 324 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); 325 _M_deallocate(this->_M_impl._M_start, 326 this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 327 this->_M_impl._M_start = __new_start.base(); 328 this->_M_impl._M_finish = __new_finish.base(); 329 this->_M_impl._M_end_of_storage = __new_start.base() + __len; 330 } 331 } 332 } 333 334 template<typename _Tp, typename _Alloc> template<typename _InputIterator> 335 void 336 vector<_Tp,_Alloc>:: _M_range_insert(iterator __pos,_InputIterator __first,_InputIterator __last,input_iterator_tag)337 _M_range_insert(iterator __pos, 338 _InputIterator __first, _InputIterator __last, 339 input_iterator_tag) 340 { 341 for ( ; __first != __last; ++__first) 342 { 343 __pos = insert(__pos, *__first); 344 ++__pos; 345 } 346 } 347 348 template<typename _Tp, typename _Alloc> template<typename _ForwardIterator> 349 void 350 vector<_Tp,_Alloc>:: _M_range_insert(iterator __position,_ForwardIterator __first,_ForwardIterator __last,forward_iterator_tag)351 _M_range_insert(iterator __position,_ForwardIterator __first, 352 _ForwardIterator __last, forward_iterator_tag) 353 { 354 if (__first != __last) 355 { 356 size_type __n = std::distance(__first, __last); 357 if (size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish) >= __n) 358 { 359 const size_type __elems_after = end() - __position; 360 iterator __old_finish(this->_M_impl._M_finish); 361 if (__elems_after > __n) 362 { 363 std::uninitialized_copy(this->_M_impl._M_finish - __n, 364 this->_M_impl._M_finish, 365 this->_M_impl._M_finish); 366 this->_M_impl._M_finish += __n; 367 std::copy_backward(__position, __old_finish - __n, __old_finish); 368 std::copy(__first, __last, __position); 369 } 370 else 371 { 372 _ForwardIterator __mid = __first; 373 std::advance(__mid, __elems_after); 374 std::uninitialized_copy(__mid, __last, this->_M_impl._M_finish); 375 this->_M_impl._M_finish += __n - __elems_after; 376 std::uninitialized_copy(__position, __old_finish, this->_M_impl._M_finish); 377 this->_M_impl._M_finish += __elems_after; 378 std::copy(__first, __mid, __position); 379 } 380 } 381 else 382 { 383 const size_type __old_size = size(); 384 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