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 namespace 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 */