1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_VECTOR_H 32 #define __SGI_STL_INTERNAL_VECTOR_H 33 34 __STL_BEGIN_NAMESPACE 35 36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 37 #pragma set woff 1174 38 #pragma set woff 1375 39 #endif 40 41 // The vector base class serves two purposes. First, its constructor 42 // and destructor allocate (but don't initialize) storage. This makes 43 // exception safety easier. Second, the base class encapsulates all of 44 // the differences between SGI-style allocators and standard-conforming 45 // allocators. 46 47 #ifdef __STL_USE_STD_ALLOCATORS 48 49 // Base class for ordinary allocators. 50 template <class _Tp, class _Allocator, bool _IsStatic> 51 class _Vector_alloc_base { 52 public: 53 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 54 allocator_type; 55 allocator_type get_allocator() const { return _M_data_allocator; } 56 57 _Vector_alloc_base(const allocator_type& __a) 58 : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 59 {} 60 61 protected: 62 allocator_type _M_data_allocator; 63 _Tp* _M_start; 64 _Tp* _M_finish; 65 _Tp* _M_end_of_storage; 66 67 _Tp* _M_allocate(size_t __n) 68 { return _M_data_allocator.allocate(__n); } 69 void _M_deallocate(_Tp* __p, size_t __n) 70 { if (__p) _M_data_allocator.deallocate(__p, __n); } 71 }; 72 73 // Specialization for allocators that have the property that we don't 74 // actually have to store an allocator object. 75 template <class _Tp, class _Allocator> 76 class _Vector_alloc_base<_Tp, _Allocator, true> { 77 public: 78 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 79 allocator_type; 80 allocator_type get_allocator() const { return allocator_type(); } 81 82 _Vector_alloc_base(const allocator_type&) 83 : _M_start(0), _M_finish(0), _M_end_of_storage(0) 84 {} 85 86 protected: 87 _Tp* _M_start; 88 _Tp* _M_finish; 89 _Tp* _M_end_of_storage; 90 91 typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type; 92 _Tp* _M_allocate(size_t __n) 93 { return _Alloc_type::allocate(__n); } 94 void _M_deallocate(_Tp* __p, size_t __n) 95 { _Alloc_type::deallocate(__p, __n);} 96 }; 97 98 template <class _Tp, class _Alloc> 99 struct _Vector_base 100 : public _Vector_alloc_base<_Tp, _Alloc, 101 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 102 { 103 typedef _Vector_alloc_base<_Tp, _Alloc, 104 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 105 _Base; 106 typedef typename _Base::allocator_type allocator_type; 107 108 _Vector_base(const allocator_type& __a) : _Base(__a) {} 109 _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) { 110 _M_start = _M_allocate(__n); 111 _M_finish = _M_start; 112 _M_end_of_storage = _M_start + __n; 113 } 114 115 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } 116 }; 117 118 #else /* __STL_USE_STD_ALLOCATORS */ 119 120 template <class _Tp, class _Alloc> 121 class _Vector_base { 122 public: 123 typedef _Alloc allocator_type; 124 allocator_type get_allocator() const { return allocator_type(); } 125 126 _Vector_base(const _Alloc&) 127 : _M_start(0), _M_finish(0), _M_end_of_storage(0) {} 128 _Vector_base(size_t __n, const _Alloc&) 129 : _M_start(0), _M_finish(0), _M_end_of_storage(0) 130 { 131 _M_start = _M_allocate(__n); 132 _M_finish = _M_start; 133 _M_end_of_storage = _M_start + __n; 134 } 135 136 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } 137 138 protected: 139 _Tp* _M_start; 140 _Tp* _M_finish; 141 _Tp* _M_end_of_storage; 142 143 typedef simple_alloc<_Tp, _Alloc> _M_data_allocator; 144 _Tp* _M_allocate(size_t __n) 145 { return _M_data_allocator::allocate(__n); } 146 void _M_deallocate(_Tp* __p, size_t __n) 147 { _M_data_allocator::deallocate(__p, __n); } 148 }; 149 150 #endif /* __STL_USE_STD_ALLOCATORS */ 151 152 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 153 class vector : protected _Vector_base<_Tp, _Alloc> 154 { 155 private: 156 typedef _Vector_base<_Tp, _Alloc> _Base; 157 public: 158 typedef _Tp value_type; 159 typedef value_type* pointer; 160 typedef const value_type* const_pointer; 161 typedef value_type* iterator; 162 typedef const value_type* const_iterator; 163 typedef value_type& reference; 164 typedef const value_type& const_reference; 165 typedef size_t size_type; 166 typedef ptrdiff_t difference_type; 167 168 typedef typename _Base::allocator_type allocator_type; 169 allocator_type get_allocator() const { return _Base::get_allocator(); } 170 171 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 172 typedef reverse_iterator<const_iterator> const_reverse_iterator; 173 typedef reverse_iterator<iterator> reverse_iterator; 174 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 175 typedef reverse_iterator<const_iterator, value_type, const_reference, 176 difference_type> const_reverse_iterator; 177 typedef reverse_iterator<iterator, value_type, reference, difference_type> 178 reverse_iterator; 179 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 180 181 protected: 182 #ifdef __STL_HAS_NAMESPACES 183 using _Base::_M_allocate; 184 using _Base::_M_deallocate; 185 using _Base::_M_start; 186 using _Base::_M_finish; 187 using _Base::_M_end_of_storage; 188 #endif /* __STL_HAS_NAMESPACES */ 189 190 protected: 191 void _M_insert_aux(iterator __position, const _Tp& __x); 192 void _M_insert_aux(iterator __position); 193 194 public: 195 iterator begin() { return _M_start; } 196 const_iterator begin() const { return _M_start; } 197 iterator end() { return _M_finish; } 198 const_iterator end() const { return _M_finish; } 199 200 reverse_iterator rbegin() 201 { return reverse_iterator(end()); } 202 const_reverse_iterator rbegin() const 203 { return const_reverse_iterator(end()); } 204 reverse_iterator rend() 205 { return reverse_iterator(begin()); } 206 const_reverse_iterator rend() const 207 { return const_reverse_iterator(begin()); } 208 209 size_type size() const 210 { return size_type(end() - begin()); } 211 size_type max_size() const 212 { return size_type(-1) / sizeof(_Tp); } 213 size_type capacity() const 214 { return size_type(_M_end_of_storage - begin()); } 215 bool empty() const 216 { return begin() == end(); } 217 218 reference operator[](size_type __n) { return *(begin() + __n); } 219 const_reference operator[](size_type __n) const { return *(begin() + __n); } 220 221 explicit vector(const allocator_type& __a = allocator_type()) 222 : _Base(__a) {} 223 224 vector(size_type __n, const _Tp& __value, 225 const allocator_type& __a = allocator_type()) 226 : _Base(__n, __a) 227 { _M_finish = uninitialized_fill_n(_M_start, __n, __value); } 228 229 explicit vector(size_type __n) 230 : _Base(__n, allocator_type()) 231 { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); } 232 233 vector(const vector<_Tp, _Alloc>& __x) 234 : _Base(__x.size(), __x.get_allocator()) 235 { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); } 236 237 #ifdef __STL_MEMBER_TEMPLATES 238 // Check whether it's an integral type. If so, it's not an iterator. 239 template <class _InputIterator> 240 vector(_InputIterator __first, _InputIterator __last, 241 const allocator_type& __a = allocator_type()) : _Base(__a) { 242 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 243 _M_initialize_aux(__first, __last, _Integral()); 244 } 245 246 template <class _Integer> 247 void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) { 248 _M_start = _M_allocate(__n); 249 _M_end_of_storage = _M_start + __n; 250 _M_finish = uninitialized_fill_n(_M_start, __n, __value); 251 } 252 253 template <class _InputIterator> 254 void _M_initialize_aux(_InputIterator __first, _InputIterator __last, 255 __false_type) { 256 _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first)); 257 } 258 259 #else 260 vector(const _Tp* __first, const _Tp* __last, 261 const allocator_type& __a = allocator_type()) 262 : _Base(__last - __first, __a) 263 { _M_finish = uninitialized_copy(__first, __last, _M_start); } 264 #endif /* __STL_MEMBER_TEMPLATES */ 265 266 ~vector() { destroy(_M_start, _M_finish); } 267 268 vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x); 269 void reserve(size_type __n) { 270 if (capacity() < __n) { 271 const size_type __old_size = size(); 272 iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish); 273 destroy(_M_start, _M_finish); 274 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 275 _M_start = __tmp; 276 _M_finish = __tmp + __old_size; 277 _M_end_of_storage = _M_start + __n; 278 } 279 } 280 281 // assign(), a generalized assignment member function. Two 282 // versions: one that takes a count, and one that takes a range. 283 // The range version is a member template, so we dispatch on whether 284 // or not the type is an integer. 285 286 void assign(size_type __n, const _Tp& __val); 287 288 #ifdef __STL_MEMBER_TEMPLATES 289 290 template <class _InputIterator> 291 void assign(_InputIterator __first, _InputIterator __last) { 292 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 293 _M_assign_dispatch(__first, __last, _Integral()); 294 } 295 296 template <class _Integer> 297 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 298 { assign((size_type) __n, (_Tp) __val); } 299 300 template <class _InputIter> 301 void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) 302 { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); } 303 304 template <class _InputIterator> 305 void _M_assign_aux(_InputIterator __first, _InputIterator __last, 306 input_iterator_tag); 307 308 template <class _ForwardIterator> 309 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 310 forward_iterator_tag); 311 312 #endif /* __STL_MEMBER_TEMPLATES */ 313 314 reference front() { return *begin(); } 315 const_reference front() const { return *begin(); } 316 reference back() { return *(end() - 1); } 317 const_reference back() const { return *(end() - 1); } 318 319 void push_back(const _Tp& __x) { 320 if (_M_finish != _M_end_of_storage) { 321 construct(_M_finish, __x); 322 ++_M_finish; 323 } 324 else 325 _M_insert_aux(end(), __x); 326 } 327 void push_back() { 328 if (_M_finish != _M_end_of_storage) { 329 construct(_M_finish); 330 ++_M_finish; 331 } 332 else 333 _M_insert_aux(end()); 334 } 335 void swap(vector<_Tp, _Alloc>& __x) { 336 __STD::swap(_M_start, __x._M_start); 337 __STD::swap(_M_finish, __x._M_finish); 338 __STD::swap(_M_end_of_storage, __x._M_end_of_storage); 339 } 340 341 iterator insert(iterator __position, const _Tp& __x) { 342 size_type __n = __position - begin(); 343 if (_M_finish != _M_end_of_storage && __position == end()) { 344 construct(_M_finish, __x); 345 ++_M_finish; 346 } 347 else 348 _M_insert_aux(__position, __x); 349 return begin() + __n; 350 } 351 iterator insert(iterator __position) { 352 size_type __n = __position - begin(); 353 if (_M_finish != _M_end_of_storage && __position == end()) { 354 construct(_M_finish); 355 ++_M_finish; 356 } 357 else 358 _M_insert_aux(__position); 359 return begin() + __n; 360 } 361 #ifdef __STL_MEMBER_TEMPLATES 362 // Check whether it's an integral type. If so, it's not an iterator. 363 template <class _InputIterator> 364 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 365 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 366 _M_insert_dispatch(__pos, __first, __last, _Integral()); 367 } 368 369 template <class _Integer> 370 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, 371 __true_type) { 372 insert(__pos, (size_type) __n, (_Tp) __val); 373 } 374 375 template <class _InputIterator> 376 void _M_insert_dispatch(iterator __pos, 377 _InputIterator __first, _InputIterator __last, 378 __false_type) { 379 _M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first)); 380 } 381 #else /* __STL_MEMBER_TEMPLATES */ 382 void insert(iterator __position, 383 const_iterator __first, const_iterator __last); 384 #endif /* __STL_MEMBER_TEMPLATES */ 385 386 void insert (iterator __pos, size_type __n, const _Tp& __x); 387 388 void pop_back() { 389 --_M_finish; 390 destroy(_M_finish); 391 } 392 iterator erase(iterator __position) { 393 if (__position + 1 != end()) 394 copy(__position + 1, _M_finish, __position); 395 --_M_finish; 396 destroy(_M_finish); 397 return __position; 398 } 399 iterator erase(iterator __first, iterator __last) { 400 iterator __i = copy(__last, _M_finish, __first); 401 destroy(__i, _M_finish); 402 _M_finish = _M_finish - (__last - __first); 403 return __first; 404 } 405 406 void resize(size_type __new_size, const _Tp& __x) { 407 if (__new_size < size()) 408 erase(begin() + __new_size, end()); 409 else 410 insert(end(), __new_size - size(), __x); 411 } 412 void resize(size_type __new_size) { resize(__new_size, _Tp()); } 413 void clear() { erase(begin(), end()); } 414 415 protected: 416 417 #ifdef __STL_MEMBER_TEMPLATES 418 template <class _ForwardIterator> 419 iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first, 420 _ForwardIterator __last) 421 { 422 iterator __result = _M_allocate(__n); 423 __STL_TRY { 424 uninitialized_copy(__first, __last, __result); 425 return __result; 426 } 427 __STL_UNWIND(_M_deallocate(__result, __n)); 428 } 429 #else /* __STL_MEMBER_TEMPLATES */ 430 iterator _M_allocate_and_copy(size_type __n, const_iterator __first, 431 const_iterator __last) 432 { 433 iterator __result = _M_allocate(__n); 434 __STL_TRY { 435 uninitialized_copy(__first, __last, __result); 436 return __result; 437 } 438 __STL_UNWIND(_M_deallocate(__result, __n)); 439 } 440 #endif /* __STL_MEMBER_TEMPLATES */ 441 442 443 #ifdef __STL_MEMBER_TEMPLATES 444 template <class _InputIterator> 445 void _M_range_initialize(_InputIterator __first, 446 _InputIterator __last, input_iterator_tag) 447 { 448 for ( ; __first != __last; ++__first) 449 push_back(*__first); 450 } 451 452 // This function is only called by the constructor. 453 template <class _ForwardIterator> 454 void _M_range_initialize(_ForwardIterator __first, 455 _ForwardIterator __last, forward_iterator_tag) 456 { 457 size_type __n = 0; 458 distance(__first, __last, __n); 459 _M_start = _M_allocate(__n); 460 _M_end_of_storage = _M_start + __n; 461 _M_finish = uninitialized_copy(__first, __last, _M_start); 462 } 463 464 template <class _InputIterator> 465 void _M_range_insert(iterator __pos, 466 _InputIterator __first, _InputIterator __last, 467 input_iterator_tag); 468 469 template <class _ForwardIterator> 470 void _M_range_insert(iterator __pos, 471 _ForwardIterator __first, _ForwardIterator __last, 472 forward_iterator_tag); 473 474 #endif /* __STL_MEMBER_TEMPLATES */ 475 }; 476 477 template <class _Tp, class _Alloc> 478 inline bool 479 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 480 { 481 return __x.size() == __y.size() && 482 equal(__x.begin(), __x.end(), __y.begin()); 483 } 484 485 template <class _Tp, class _Alloc> 486 inline bool 487 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 488 { 489 return lexicographical_compare(__x.begin(), __x.end(), 490 __y.begin(), __y.end()); 491 } 492 493 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 494 495 template <class _Tp, class _Alloc> 496 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) 497 { 498 __x.swap(__y); 499 } 500 501 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 502 503 template <class _Tp, class _Alloc> 504 vector<_Tp,_Alloc>& 505 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x) 506 { 507 if (&__x != this) { 508 const size_type __xlen = __x.size(); 509 if (__xlen > capacity()) { 510 iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); 511 destroy(_M_start, _M_finish); 512 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 513 _M_start = __tmp; 514 _M_end_of_storage = _M_start + __xlen; 515 } 516 else if (size() >= __xlen) { 517 iterator __i = copy(__x.begin(), __x.end(), begin()); 518 destroy(__i, _M_finish); 519 } 520 else { 521 copy(__x.begin(), __x.begin() + size(), _M_start); 522 uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish); 523 } 524 _M_finish = _M_start + __xlen; 525 } 526 return *this; 527 } 528 529 template <class _Tp, class _Alloc> 530 void vector<_Tp, _Alloc>::assign(size_t __n, const value_type& __val) { 531 if (__n > capacity()) { 532 vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator()); 533 __tmp.swap(*this); 534 } 535 else if (__n > size()) { 536 fill(begin(), end(), __val); 537 _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val); 538 } 539 else 540 erase(fill_n(begin(), __n, __val), end()); 541 } 542 543 #ifdef __STL_MEMBER_TEMPLATES 544 545 template <class _Tp, class _Alloc> template <class _InputIter> 546 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last, 547 input_iterator_tag) { 548 iterator __cur = begin(); 549 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 550 *__cur = *__first; 551 if (__first == __last) 552 erase(__cur, end()); 553 else 554 insert(end(), __first, __last); 555 } 556 557 template <class _Tp, class _Alloc> template <class _ForwardIter> 558 void 559 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last, 560 forward_iterator_tag) { 561 size_type __len = 0; 562 distance(__first, __last, __len); 563 564 if (__len > capacity()) { 565 iterator __tmp = _M_allocate_and_copy(__len, __first, __last); 566 destroy(_M_start, _M_finish); 567 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 568 _M_start = __tmp; 569 _M_end_of_storage = _M_finish = _M_start + __len; 570 } 571 else if (size() >= __len) { 572 iterator __new_finish = copy(__first, __last, _M_start); 573 destroy(__new_finish, _M_finish); 574 _M_finish = __new_finish; 575 } 576 else { 577 _ForwardIter __mid = __first; 578 advance(__mid, size()); 579 copy(__first, __mid, _M_start); 580 _M_finish = uninitialized_copy(__mid, __last, _M_finish); 581 } 582 } 583 584 #endif /* __STL_MEMBER_TEMPLATES */ 585 586 template <class _Tp, class _Alloc> 587 void 588 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) 589 { 590 if (_M_finish != _M_end_of_storage) { 591 construct(_M_finish, *(_M_finish - 1)); 592 ++_M_finish; 593 _Tp __x_copy = __x; 594 copy_backward(__position, _M_finish - 2, _M_finish - 1); 595 *__position = __x_copy; 596 } 597 else { 598 const size_type __old_size = size(); 599 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 600 iterator __new_start = _M_allocate(__len); 601 iterator __new_finish = __new_start; 602 __STL_TRY { 603 __new_finish = uninitialized_copy(_M_start, __position, __new_start); 604 construct(__new_finish, __x); 605 ++__new_finish; 606 __new_finish = uninitialized_copy(__position, _M_finish, __new_finish); 607 } 608 __STL_UNWIND((destroy(__new_start,__new_finish), 609 _M_deallocate(__new_start,__len))); 610 destroy(begin(), end()); 611 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 612 _M_start = __new_start; 613 _M_finish = __new_finish; 614 _M_end_of_storage = __new_start + __len; 615 } 616 } 617 618 template <class _Tp, class _Alloc> 619 void 620 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position) 621 { 622 if (_M_finish != _M_end_of_storage) { 623 construct(_M_finish, *(_M_finish - 1)); 624 ++_M_finish; 625 copy_backward(__position, _M_finish - 2, _M_finish - 1); 626 *__position = _Tp(); 627 } 628 else { 629 const size_type __old_size = size(); 630 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 631 iterator __new_start = _M_allocate(__len); 632 iterator __new_finish = __new_start; 633 __STL_TRY { 634 __new_finish = uninitialized_copy(_M_start, __position, __new_start); 635 construct(__new_finish); 636 ++__new_finish; 637 __new_finish = uninitialized_copy(__position, _M_finish, __new_finish); 638 } 639 __STL_UNWIND((destroy(__new_start,__new_finish), 640 _M_deallocate(__new_start,__len))); 641 destroy(begin(), end()); 642 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 643 _M_start = __new_start; 644 _M_finish = __new_finish; 645 _M_end_of_storage = __new_start + __len; 646 } 647 } 648 649 template <class _Tp, class _Alloc> 650 void vector<_Tp, _Alloc>::insert(iterator __position, size_type __n, 651 const _Tp& __x) 652 { 653 if (__n != 0) { 654 if (size_type(_M_end_of_storage - _M_finish) >= __n) { 655 _Tp __x_copy = __x; 656 const size_type __elems_after = _M_finish - __position; 657 iterator __old_finish = _M_finish; 658 if (__elems_after > __n) { 659 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 660 _M_finish += __n; 661 copy_backward(__position, __old_finish - __n, __old_finish); 662 fill(__position, __position + __n, __x_copy); 663 } 664 else { 665 uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy); 666 _M_finish += __n - __elems_after; 667 uninitialized_copy(__position, __old_finish, _M_finish); 668 _M_finish += __elems_after; 669 fill(__position, __old_finish, __x_copy); 670 } 671 } 672 else { 673 const size_type __old_size = size(); 674 const size_type __len = __old_size + max(__old_size, __n); 675 iterator __new_start = _M_allocate(__len); 676 iterator __new_finish = __new_start; 677 __STL_TRY { 678 __new_finish = uninitialized_copy(_M_start, __position, __new_start); 679 __new_finish = uninitialized_fill_n(__new_finish, __n, __x); 680 __new_finish 681 = uninitialized_copy(__position, _M_finish, __new_finish); 682 } 683 __STL_UNWIND((destroy(__new_start,__new_finish), 684 _M_deallocate(__new_start,__len))); 685 destroy(_M_start, _M_finish); 686 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 687 _M_start = __new_start; 688 _M_finish = __new_finish; 689 _M_end_of_storage = __new_start + __len; 690 } 691 } 692 } 693 694 #ifdef __STL_MEMBER_TEMPLATES 695 696 template <class _Tp, class _Alloc> template <class _InputIterator> 697 void 698 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos, 699 _InputIterator __first, 700 _InputIterator __last, 701 input_iterator_tag) 702 { 703 for ( ; __first != __last; ++__first) { 704 __pos = insert(__pos, *__first); 705 ++__pos; 706 } 707 } 708 709 template <class _Tp, class _Alloc> template <class _ForwardIterator> 710 void 711 vector<_Tp, _Alloc>::_M_range_insert(iterator __position, 712 _ForwardIterator __first, 713 _ForwardIterator __last, 714 forward_iterator_tag) 715 { 716 if (__first != __last) { 717 size_type __n = 0; 718 distance(__first, __last, __n); 719 if (size_type(_M_end_of_storage - _M_finish) >= __n) { 720 const size_type __elems_after = _M_finish - __position; 721 iterator __old_finish = _M_finish; 722 if (__elems_after > __n) { 723 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 724 _M_finish += __n; 725 copy_backward(__position, __old_finish - __n, __old_finish); 726 copy(__first, __last, __position); 727 } 728 else { 729 _ForwardIterator __mid = __first; 730 advance(__mid, __elems_after); 731 uninitialized_copy(__mid, __last, _M_finish); 732 _M_finish += __n - __elems_after; 733 uninitialized_copy(__position, __old_finish, _M_finish); 734 _M_finish += __elems_after; 735 copy(__first, __mid, __position); 736 } 737 } 738 else { 739 const size_type __old_size = size(); 740 const size_type __len = __old_size + max(__old_size, __n); 741 iterator __new_start = _M_allocate(__len); 742 iterator __new_finish = __new_start; 743 __STL_TRY { 744 __new_finish = uninitialized_copy(_M_start, __position, __new_start); 745 __new_finish = uninitialized_copy(__first, __last, __new_finish); 746 __new_finish 747 = uninitialized_copy(__position, _M_finish, __new_finish); 748 } 749 __STL_UNWIND((destroy(__new_start,__new_finish), 750 _M_deallocate(__new_start,__len))); 751 destroy(_M_start, _M_finish); 752 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 753 _M_start = __new_start; 754 _M_finish = __new_finish; 755 _M_end_of_storage = __new_start + __len; 756 } 757 } 758 } 759 760 #else /* __STL_MEMBER_TEMPLATES */ 761 762 template <class _Tp, class _Alloc> 763 void 764 vector<_Tp, _Alloc>::insert(iterator __position, 765 const_iterator __first, 766 const_iterator __last) 767 { 768 if (__first != __last) { 769 size_type __n = 0; 770 distance(__first, __last, __n); 771 if (size_type(_M_end_of_storage - _M_finish) >= __n) { 772 const size_type __elems_after = _M_finish - __position; 773 iterator __old_finish = _M_finish; 774 if (__elems_after > __n) { 775 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); 776 _M_finish += __n; 777 copy_backward(__position, __old_finish - __n, __old_finish); 778 copy(__first, __last, __position); 779 } 780 else { 781 uninitialized_copy(__first + __elems_after, __last, _M_finish); 782 _M_finish += __n - __elems_after; 783 uninitialized_copy(__position, __old_finish, _M_finish); 784 _M_finish += __elems_after; 785 copy(__first, __first + __elems_after, __position); 786 } 787 } 788 else { 789 const size_type __old_size = size(); 790 const size_type __len = __old_size + max(__old_size, __n); 791 iterator __new_start = _M_allocate(__len); 792 iterator __new_finish = __new_start; 793 __STL_TRY { 794 __new_finish = uninitialized_copy(_M_start, __position, __new_start); 795 __new_finish = uninitialized_copy(__first, __last, __new_finish); 796 __new_finish 797 = uninitialized_copy(__position, _M_finish, __new_finish); 798 } 799 __STL_UNWIND((destroy(__new_start,__new_finish), 800 _M_deallocate(__new_start,__len))); 801 destroy(_M_start, _M_finish); 802 _M_deallocate(_M_start, _M_end_of_storage - _M_start); 803 _M_start = __new_start; 804 _M_finish = __new_finish; 805 _M_end_of_storage = __new_start + __len; 806 } 807 } 808 } 809 810 #endif /* __STL_MEMBER_TEMPLATES */ 811 812 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 813 #pragma reset woff 1174 814 #pragma reset woff 1375 815 #endif 816 817 __STL_END_NAMESPACE 818 819 #endif /* __SGI_STL_INTERNAL_VECTOR_H */ 820 821 // Local Variables: 822 // mode:C++ 823 // End: 824