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