libstdc++-v3/include/bits/vector.tcc

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