libstdc++
vector.tcc
Go to the documentation of this file.
00001 // Vector implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this  software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/vector.tcc
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{vector}
00054  */
00055 
00056 #ifndef _VECTOR_TCC
00057 #define _VECTOR_TCC 1
00058 
00059 namespace std _GLIBCXX_VISIBILITY(default)
00060 {
00061 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00063 
00064   template<typename _Tp, typename _Alloc>
00065     void
00066     vector<_Tp, _Alloc>::
00067     reserve(size_type __n)
00068     {
00069       if (__n > this->max_size())
00070         __throw_length_error(__N("vector::reserve"));
00071       if (this->capacity() < __n)
00072         {
00073           const size_type __old_size = size();
00074           pointer __tmp;
00075 #if __cplusplus >= 201103L
00076           if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
00077             {
00078               __tmp = this->_M_allocate(__n);
00079               _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
00080                           __tmp, _M_get_Tp_allocator());
00081             }
00082           else
00083 #endif
00084             {
00085               __tmp = _M_allocate_and_copy(__n,
00086                 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
00087                 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
00088               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00089                             _M_get_Tp_allocator());
00090             }
00091           _GLIBCXX_ASAN_ANNOTATE_REINIT;
00092           _M_deallocate(this->_M_impl._M_start,
00093                         this->_M_impl._M_end_of_storage
00094                         - this->_M_impl._M_start);
00095           this->_M_impl._M_start = __tmp;
00096           this->_M_impl._M_finish = __tmp + __old_size;
00097           this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00098         }
00099     }
00100 
00101 #if __cplusplus >= 201103L
00102   template<typename _Tp, typename _Alloc>
00103     template<typename... _Args>
00104 #if __cplusplus > 201402L
00105       typename vector<_Tp, _Alloc>::reference
00106 #else
00107       void
00108 #endif
00109       vector<_Tp, _Alloc>::
00110       emplace_back(_Args&&... __args)
00111       {
00112         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00113           {
00114             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
00115             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00116                                      std::forward<_Args>(__args)...);
00117             ++this->_M_impl._M_finish;
00118             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
00119           }
00120         else
00121           _M_realloc_insert(end(), std::forward<_Args>(__args)...);
00122 #if __cplusplus > 201402L
00123         return back();
00124 #endif
00125       }
00126 #endif
00127 
00128   template<typename _Tp, typename _Alloc>
00129     typename vector<_Tp, _Alloc>::iterator
00130     vector<_Tp, _Alloc>::
00131 #if __cplusplus >= 201103L
00132     insert(const_iterator __position, const value_type& __x)
00133 #else
00134     insert(iterator __position, const value_type& __x)
00135 #endif
00136     {
00137       const size_type __n = __position - begin();
00138       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00139         if (__position == end())
00140           {
00141             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
00142             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00143                                      __x);
00144             ++this->_M_impl._M_finish;
00145             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
00146           }
00147         else
00148           {
00149 #if __cplusplus >= 201103L
00150             const auto __pos = begin() + (__position - cbegin());
00151             // __x could be an existing element of this vector, so make a
00152             // copy of it before _M_insert_aux moves elements around.
00153             _Temporary_value __x_copy(this, __x);
00154             _M_insert_aux(__pos, std::move(__x_copy._M_val()));
00155 #else
00156             _M_insert_aux(__position, __x);
00157 #endif
00158           }
00159       else
00160 #if __cplusplus >= 201103L
00161         _M_realloc_insert(begin() + (__position - cbegin()), __x);
00162 #else
00163         _M_realloc_insert(__position, __x);
00164 #endif
00165 
00166       return iterator(this->_M_impl._M_start + __n);
00167     }
00168 
00169   template<typename _Tp, typename _Alloc>
00170     typename vector<_Tp, _Alloc>::iterator
00171     vector<_Tp, _Alloc>::
00172     _M_erase(iterator __position)
00173     {
00174       if (__position + 1 != end())
00175         _GLIBCXX_MOVE3(__position + 1, end(), __position);
00176       --this->_M_impl._M_finish;
00177       _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
00178       _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
00179       return __position;
00180     }
00181 
00182   template<typename _Tp, typename _Alloc>
00183     typename vector<_Tp, _Alloc>::iterator
00184     vector<_Tp, _Alloc>::
00185     _M_erase(iterator __first, iterator __last)
00186     {
00187       if (__first != __last)
00188         {
00189           if (__last != end())
00190             _GLIBCXX_MOVE3(__last, end(), __first);
00191           _M_erase_at_end(__first.base() + (end() - __last));
00192         }
00193       return __first;
00194     }
00195 
00196   template<typename _Tp, typename _Alloc>
00197     vector<_Tp, _Alloc>&
00198     vector<_Tp, _Alloc>::
00199     operator=(const vector<_Tp, _Alloc>& __x)
00200     {
00201       if (&__x != this)
00202         {
00203           _GLIBCXX_ASAN_ANNOTATE_REINIT;
00204 #if __cplusplus >= 201103L
00205           if (_Alloc_traits::_S_propagate_on_copy_assign())
00206             {
00207               if (!_Alloc_traits::_S_always_equal()
00208                   && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
00209                 {
00210                   // replacement allocator cannot free existing storage
00211                   this->clear();
00212                   _M_deallocate(this->_M_impl._M_start,
00213                                 this->_M_impl._M_end_of_storage
00214                                 - this->_M_impl._M_start);
00215                   this->_M_impl._M_start = nullptr;
00216                   this->_M_impl._M_finish = nullptr;
00217                   this->_M_impl._M_end_of_storage = nullptr;
00218                 }
00219               std::__alloc_on_copy(_M_get_Tp_allocator(),
00220                                    __x._M_get_Tp_allocator());
00221             }
00222 #endif
00223           const size_type __xlen = __x.size();
00224           if (__xlen > capacity())
00225             {
00226               pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
00227                                                    __x.end());
00228               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00229                             _M_get_Tp_allocator());
00230               _M_deallocate(this->_M_impl._M_start,
00231                             this->_M_impl._M_end_of_storage
00232                             - this->_M_impl._M_start);
00233               this->_M_impl._M_start = __tmp;
00234               this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
00235             }
00236           else if (size() >= __xlen)
00237             {
00238               std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
00239                             end(), _M_get_Tp_allocator());
00240             }
00241           else
00242             {
00243               std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
00244                         this->_M_impl._M_start);
00245               std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
00246                                           __x._M_impl._M_finish,
00247                                           this->_M_impl._M_finish,
00248                                           _M_get_Tp_allocator());
00249             }
00250           this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
00251         }
00252       return *this;
00253     }
00254 
00255   template<typename _Tp, typename _Alloc>
00256     void
00257     vector<_Tp, _Alloc>::
00258     _M_fill_assign(size_t __n, const value_type& __val)
00259     {
00260       if (__n > capacity())
00261         {
00262           vector __tmp(__n, __val, _M_get_Tp_allocator());
00263           __tmp._M_impl._M_swap_data(this->_M_impl);
00264         }
00265       else if (__n > size())
00266         {
00267           std::fill(begin(), end(), __val);
00268           const size_type __add = __n - size();
00269           _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
00270           this->_M_impl._M_finish =
00271             std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00272                                           __add, __val, _M_get_Tp_allocator());
00273           _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
00274         }
00275       else
00276         _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
00277     }
00278 
00279   template<typename _Tp, typename _Alloc>
00280     template<typename _InputIterator>
00281       void
00282       vector<_Tp, _Alloc>::
00283       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00284                     std::input_iterator_tag)
00285       {
00286         pointer __cur(this->_M_impl._M_start);
00287         for (; __first != __last && __cur != this->_M_impl._M_finish;
00288              ++__cur, (void)++__first)
00289           *__cur = *__first;
00290         if (__first == __last)
00291           _M_erase_at_end(__cur);
00292         else
00293           _M_range_insert(end(), __first, __last,
00294                           std::__iterator_category(__first));
00295       }
00296 
00297   template<typename _Tp, typename _Alloc>
00298     template<typename _ForwardIterator>
00299       void
00300       vector<_Tp, _Alloc>::
00301       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00302                     std::forward_iterator_tag)
00303       {
00304         const size_type __len = std::distance(__first, __last);
00305 
00306         if (__len > capacity())
00307           {
00308             _S_check_init_len(__len, _M_get_Tp_allocator());
00309             pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
00310             std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00311                           _M_get_Tp_allocator());
00312             _GLIBCXX_ASAN_ANNOTATE_REINIT;
00313             _M_deallocate(this->_M_impl._M_start,
00314                           this->_M_impl._M_end_of_storage
00315                           - this->_M_impl._M_start);
00316             this->_M_impl._M_start = __tmp;
00317             this->_M_impl._M_finish = this->_M_impl._M_start + __len;
00318             this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
00319           }
00320         else if (size() >= __len)
00321           _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
00322         else
00323           {
00324             _ForwardIterator __mid = __first;
00325             std::advance(__mid, size());
00326             std::copy(__first, __mid, this->_M_impl._M_start);
00327             const size_type __attribute__((__unused__)) __n = __len - size();
00328             _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00329             this->_M_impl._M_finish =
00330               std::__uninitialized_copy_a(__mid, __last,
00331                                           this->_M_impl._M_finish,
00332                                           _M_get_Tp_allocator());
00333             _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
00334           }
00335       }
00336 
00337 #if __cplusplus >= 201103L
00338   template<typename _Tp, typename _Alloc>
00339     auto
00340     vector<_Tp, _Alloc>::
00341     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
00342     {
00343       const auto __n = __position - cbegin();
00344       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00345         if (__position == cend())
00346           {
00347             _GLIBCXX_ASAN_ANNOTATE_GROW(1);
00348             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00349                                      std::move(__v));
00350             ++this->_M_impl._M_finish;
00351             _GLIBCXX_ASAN_ANNOTATE_GREW(1);
00352           }
00353         else
00354           _M_insert_aux(begin() + __n, std::move(__v));
00355       else
00356         _M_realloc_insert(begin() + __n, std::move(__v));
00357 
00358       return iterator(this->_M_impl._M_start + __n);
00359     }
00360 
00361   template<typename _Tp, typename _Alloc>
00362     template<typename... _Args>
00363       auto
00364       vector<_Tp, _Alloc>::
00365       _M_emplace_aux(const_iterator __position, _Args&&... __args)
00366       -> iterator
00367       {
00368         const auto __n = __position - cbegin();
00369         if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00370           if (__position == cend())
00371             {
00372               _GLIBCXX_ASAN_ANNOTATE_GROW(1);
00373               _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00374                                        std::forward<_Args>(__args)...);
00375               ++this->_M_impl._M_finish;
00376               _GLIBCXX_ASAN_ANNOTATE_GREW(1);
00377             }
00378           else
00379             {
00380               // We need to construct a temporary because something in __args...
00381               // could alias one of the elements of the container and so we
00382               // need to use it before _M_insert_aux moves elements around.
00383               _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
00384               _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
00385             }
00386         else
00387           _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
00388 
00389         return iterator(this->_M_impl._M_start + __n);
00390       }
00391 
00392   template<typename _Tp, typename _Alloc>
00393     template<typename _Arg>
00394       void
00395       vector<_Tp, _Alloc>::
00396       _M_insert_aux(iterator __position, _Arg&& __arg)
00397 #else
00398   template<typename _Tp, typename _Alloc>
00399     void
00400     vector<_Tp, _Alloc>::
00401     _M_insert_aux(iterator __position, const _Tp& __x)
00402 #endif
00403     {
00404       _GLIBCXX_ASAN_ANNOTATE_GROW(1);
00405       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00406                                _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
00407       ++this->_M_impl._M_finish;
00408       _GLIBCXX_ASAN_ANNOTATE_GREW(1);
00409 #if __cplusplus < 201103L
00410       _Tp __x_copy = __x;
00411 #endif
00412       _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00413                               this->_M_impl._M_finish - 2,
00414                               this->_M_impl._M_finish - 1);
00415 #if __cplusplus < 201103L
00416       *__position = __x_copy;
00417 #else
00418       *__position = std::forward<_Arg>(__arg);
00419 #endif
00420     }
00421 
00422 #if __cplusplus >= 201103L
00423   template<typename _Tp, typename _Alloc>
00424     template<typename... _Args>
00425       void
00426       vector<_Tp, _Alloc>::
00427       _M_realloc_insert(iterator __position, _Args&&... __args)
00428 #else
00429   template<typename _Tp, typename _Alloc>
00430     void
00431     vector<_Tp, _Alloc>::
00432     _M_realloc_insert(iterator __position, const _Tp& __x)
00433 #endif
00434     {
00435       const size_type __len =
00436         _M_check_len(size_type(1), "vector::_M_realloc_insert");
00437       pointer __old_start = this->_M_impl._M_start;
00438       pointer __old_finish = this->_M_impl._M_finish;
00439       const size_type __elems_before = __position - begin();
00440       pointer __new_start(this->_M_allocate(__len));
00441       pointer __new_finish(__new_start);
00442       __try
00443         {
00444           // The order of the three operations is dictated by the C++11
00445           // case, where the moves could alter a new element belonging
00446           // to the existing vector.  This is an issue only for callers
00447           // taking the element by lvalue ref (see last bullet of C++11
00448           // [res.on.arguments]).
00449           _Alloc_traits::construct(this->_M_impl,
00450                                    __new_start + __elems_before,
00451 #if __cplusplus >= 201103L
00452                                    std::forward<_Args>(__args)...);
00453 #else
00454                                    __x);
00455 #endif
00456           __new_finish = pointer();
00457 
00458 #if __cplusplus >= 201103L
00459           if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
00460             {
00461               __new_finish = _S_relocate(__old_start, __position.base(),
00462                                          __new_start, _M_get_Tp_allocator());
00463 
00464               ++__new_finish;
00465 
00466               __new_finish = _S_relocate(__position.base(), __old_finish,
00467                                          __new_finish, _M_get_Tp_allocator());
00468             }
00469           else
00470 #endif
00471             {
00472               __new_finish
00473                 = std::__uninitialized_move_if_noexcept_a
00474                 (__old_start, __position.base(),
00475                  __new_start, _M_get_Tp_allocator());
00476 
00477               ++__new_finish;
00478 
00479               __new_finish
00480                 = std::__uninitialized_move_if_noexcept_a
00481                 (__position.base(), __old_finish,
00482                  __new_finish, _M_get_Tp_allocator());
00483             }
00484         }
00485       __catch(...)
00486         {
00487           if (!__new_finish)
00488             _Alloc_traits::destroy(this->_M_impl,
00489                                    __new_start + __elems_before);
00490           else
00491             std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
00492           _M_deallocate(__new_start, __len);
00493           __throw_exception_again;
00494         }
00495 #if __cplusplus >= 201103L
00496       if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
00497 #endif
00498         std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
00499       _GLIBCXX_ASAN_ANNOTATE_REINIT;
00500       _M_deallocate(__old_start,
00501                     this->_M_impl._M_end_of_storage - __old_start);
00502       this->_M_impl._M_start = __new_start;
00503       this->_M_impl._M_finish = __new_finish;
00504       this->_M_impl._M_end_of_storage = __new_start + __len;
00505     }
00506 
00507   template<typename _Tp, typename _Alloc>
00508     void
00509     vector<_Tp, _Alloc>::
00510     _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
00511     {
00512       if (__n != 0)
00513         {
00514           if (size_type(this->_M_impl._M_end_of_storage
00515                         - this->_M_impl._M_finish) >= __n)
00516             {
00517 #if __cplusplus < 201103L
00518               value_type __x_copy = __x;
00519 #else
00520               _Temporary_value __tmp(this, __x);
00521               value_type& __x_copy = __tmp._M_val();
00522 #endif
00523               const size_type __elems_after = end() - __position;
00524               pointer __old_finish(this->_M_impl._M_finish);
00525               if (__elems_after > __n)
00526                 {
00527                   _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00528                   std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00529                                               this->_M_impl._M_finish,
00530                                               this->_M_impl._M_finish,
00531                                               _M_get_Tp_allocator());
00532                   this->_M_impl._M_finish += __n;
00533                   _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
00534                   _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00535                                           __old_finish - __n, __old_finish);
00536                   std::fill(__position.base(), __position.base() + __n,
00537                             __x_copy);
00538                 }
00539               else
00540                 {
00541                   _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00542                   this->_M_impl._M_finish =
00543                     std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
00544                                                   __n - __elems_after,
00545                                                   __x_copy,
00546                                                   _M_get_Tp_allocator());
00547                   _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
00548                   std::__uninitialized_move_a(__position.base(), __old_finish,
00549                                               this->_M_impl._M_finish,
00550                                               _M_get_Tp_allocator());
00551                   this->_M_impl._M_finish += __elems_after;
00552                   _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
00553                   std::fill(__position.base(), __old_finish, __x_copy);
00554                 }
00555             }
00556           else
00557             {
00558               const size_type __len =
00559                 _M_check_len(__n, "vector::_M_fill_insert");
00560               const size_type __elems_before = __position - begin();
00561               pointer __new_start(this->_M_allocate(__len));
00562               pointer __new_finish(__new_start);
00563               __try
00564                 {
00565                   // See _M_realloc_insert above.
00566                   std::__uninitialized_fill_n_a(__new_start + __elems_before,
00567                                                 __n, __x,
00568                                                 _M_get_Tp_allocator());
00569                   __new_finish = pointer();
00570 
00571                   __new_finish
00572                     = std::__uninitialized_move_if_noexcept_a
00573                     (this->_M_impl._M_start, __position.base(),
00574                      __new_start, _M_get_Tp_allocator());
00575 
00576                   __new_finish += __n;
00577 
00578                   __new_finish
00579                     = std::__uninitialized_move_if_noexcept_a
00580                     (__position.base(), this->_M_impl._M_finish,
00581                      __new_finish, _M_get_Tp_allocator());
00582                 }
00583               __catch(...)
00584                 {
00585                   if (!__new_finish)
00586                     std::_Destroy(__new_start + __elems_before,
00587                                   __new_start + __elems_before + __n,
00588                                   _M_get_Tp_allocator());
00589                   else
00590                     std::_Destroy(__new_start, __new_finish,
00591                                   _M_get_Tp_allocator());
00592                   _M_deallocate(__new_start, __len);
00593                   __throw_exception_again;
00594                 }
00595               std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00596                             _M_get_Tp_allocator());
00597               _GLIBCXX_ASAN_ANNOTATE_REINIT;
00598               _M_deallocate(this->_M_impl._M_start,
00599                             this->_M_impl._M_end_of_storage
00600                             - this->_M_impl._M_start);
00601               this->_M_impl._M_start = __new_start;
00602               this->_M_impl._M_finish = __new_finish;
00603               this->_M_impl._M_end_of_storage = __new_start + __len;
00604             }
00605         }
00606     }
00607 
00608 #if __cplusplus >= 201103L
00609   template<typename _Tp, typename _Alloc>
00610     void
00611     vector<_Tp, _Alloc>::
00612     _M_default_append(size_type __n)
00613     {
00614       if (__n != 0)
00615         {
00616           const size_type __size = size();
00617           size_type __navail = size_type(this->_M_impl._M_end_of_storage
00618                                          - this->_M_impl._M_finish);
00619 
00620           if (__size > max_size() || __navail > max_size() - __size)
00621             __builtin_unreachable();
00622 
00623           if (__navail >= __n)
00624             {
00625               _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00626               this->_M_impl._M_finish =
00627                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
00628                                                  __n, _M_get_Tp_allocator());
00629               _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
00630             }
00631           else
00632             {
00633               const size_type __len =
00634                 _M_check_len(__n, "vector::_M_default_append");
00635               pointer __new_start(this->_M_allocate(__len));
00636               if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
00637                 {
00638                   __try
00639                     {
00640                       std::__uninitialized_default_n_a(__new_start + __size,
00641                               __n, _M_get_Tp_allocator());
00642                     }
00643                   __catch(...)
00644                     {
00645                       _M_deallocate(__new_start, __len);
00646                       __throw_exception_again;
00647                     }
00648                   _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
00649                               __new_start, _M_get_Tp_allocator());
00650                 }
00651               else
00652                 {
00653                   pointer __destroy_from = pointer();
00654                   __try
00655                     {
00656                       std::__uninitialized_default_n_a(__new_start + __size,
00657                               __n, _M_get_Tp_allocator());
00658                       __destroy_from = __new_start + __size;
00659                       std::__uninitialized_move_if_noexcept_a(
00660                               this->_M_impl._M_start, this->_M_impl._M_finish,
00661                               __new_start, _M_get_Tp_allocator());
00662                     }
00663                   __catch(...)
00664                     {
00665                       if (__destroy_from)
00666                         std::_Destroy(__destroy_from, __destroy_from + __n,
00667                                       _M_get_Tp_allocator());
00668                       _M_deallocate(__new_start, __len);
00669                       __throw_exception_again;
00670                     }
00671                   std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00672                                 _M_get_Tp_allocator());
00673                 }
00674               _GLIBCXX_ASAN_ANNOTATE_REINIT;
00675               _M_deallocate(this->_M_impl._M_start,
00676                             this->_M_impl._M_end_of_storage
00677                             - this->_M_impl._M_start);
00678               this->_M_impl._M_start = __new_start;
00679               this->_M_impl._M_finish = __new_start + __size + __n;
00680               this->_M_impl._M_end_of_storage = __new_start + __len;
00681             }
00682         }
00683     }
00684 
00685   template<typename _Tp, typename _Alloc>
00686     bool
00687     vector<_Tp, _Alloc>::
00688     _M_shrink_to_fit()
00689     {
00690       if (capacity() == size())
00691         return false;
00692       _GLIBCXX_ASAN_ANNOTATE_REINIT;
00693       return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
00694     }
00695 #endif
00696 
00697   template<typename _Tp, typename _Alloc>
00698     template<typename _InputIterator>
00699       void
00700       vector<_Tp, _Alloc>::
00701       _M_range_insert(iterator __pos, _InputIterator __first,
00702                       _InputIterator __last, std::input_iterator_tag)
00703       {
00704         if (__pos == end())
00705           {
00706             for (; __first != __last; ++__first)
00707               insert(end(), *__first);
00708           }
00709         else if (__first != __last)
00710           {
00711             vector __tmp(__first, __last, _M_get_Tp_allocator());
00712             insert(__pos,
00713                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
00714                    _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
00715           }
00716       }
00717 
00718   template<typename _Tp, typename _Alloc>
00719     template<typename _ForwardIterator>
00720       void
00721       vector<_Tp, _Alloc>::
00722       _M_range_insert(iterator __position, _ForwardIterator __first,
00723                       _ForwardIterator __last, std::forward_iterator_tag)
00724       {
00725         if (__first != __last)
00726           {
00727             const size_type __n = std::distance(__first, __last);
00728             if (size_type(this->_M_impl._M_end_of_storage
00729                           - this->_M_impl._M_finish) >= __n)
00730               {
00731                 const size_type __elems_after = end() - __position;
00732                 pointer __old_finish(this->_M_impl._M_finish);
00733                 if (__elems_after > __n)
00734                   {
00735                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00736                     std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
00737                                                 this->_M_impl._M_finish,
00738                                                 this->_M_impl._M_finish,
00739                                                 _M_get_Tp_allocator());
00740                     this->_M_impl._M_finish += __n;
00741                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
00742                     _GLIBCXX_MOVE_BACKWARD3(__position.base(),
00743                                             __old_finish - __n, __old_finish);
00744                     std::copy(__first, __last, __position);
00745                   }
00746                 else
00747                   {
00748                     _ForwardIterator __mid = __first;
00749                     std::advance(__mid, __elems_after);
00750                     _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
00751                     std::__uninitialized_copy_a(__mid, __last,
00752                                                 this->_M_impl._M_finish,
00753                                                 _M_get_Tp_allocator());
00754                     this->_M_impl._M_finish += __n - __elems_after;
00755                     _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
00756                     std::__uninitialized_move_a(__position.base(),
00757                                                 __old_finish,
00758                                                 this->_M_impl._M_finish,
00759                                                 _M_get_Tp_allocator());
00760                     this->_M_impl._M_finish += __elems_after;
00761                     _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
00762                     std::copy(__first, __mid, __position);
00763                   }
00764               }
00765             else
00766               {
00767                 const size_type __len =
00768                   _M_check_len(__n, "vector::_M_range_insert");
00769                 pointer __new_start(this->_M_allocate(__len));
00770                 pointer __new_finish(__new_start);
00771                 __try
00772                   {
00773                     __new_finish
00774                       = std::__uninitialized_move_if_noexcept_a
00775                       (this->_M_impl._M_start, __position.base(),
00776                        __new_start, _M_get_Tp_allocator());
00777                     __new_finish
00778                       = std::__uninitialized_copy_a(__first, __last,
00779                                                     __new_finish,
00780                                                     _M_get_Tp_allocator());
00781                     __new_finish
00782                       = std::__uninitialized_move_if_noexcept_a
00783                       (__position.base(), this->_M_impl._M_finish,
00784                        __new_finish, _M_get_Tp_allocator());
00785                   }
00786                 __catch(...)
00787                   {
00788                     std::_Destroy(__new_start, __new_finish,
00789                                   _M_get_Tp_allocator());
00790                     _M_deallocate(__new_start, __len);
00791                     __throw_exception_again;
00792                   }
00793                 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00794                               _M_get_Tp_allocator());
00795                 _GLIBCXX_ASAN_ANNOTATE_REINIT;
00796                 _M_deallocate(this->_M_impl._M_start,
00797                               this->_M_impl._M_end_of_storage
00798                               - this->_M_impl._M_start);
00799                 this->_M_impl._M_start = __new_start;
00800                 this->_M_impl._M_finish = __new_finish;
00801                 this->_M_impl._M_end_of_storage = __new_start + __len;
00802               }
00803           }
00804       }
00805 
00806 
00807   // vector<bool>
00808   template<typename _Alloc>
00809     void
00810     vector<bool, _Alloc>::
00811     _M_reallocate(size_type __n)
00812     {
00813       _Bit_pointer __q = this->_M_allocate(__n);
00814       iterator __start(std::__addressof(*__q), 0);
00815       iterator __finish(_M_copy_aligned(begin(), end(), __start));
00816       this->_M_deallocate();
00817       this->_M_impl._M_start = __start;
00818       this->_M_impl._M_finish = __finish;
00819       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
00820     }
00821 
00822   template<typename _Alloc>
00823     void
00824     vector<bool, _Alloc>::
00825     _M_fill_insert(iterator __position, size_type __n, bool __x)
00826     {
00827       if (__n == 0)
00828         return;
00829       if (capacity() - size() >= __n)
00830         {
00831           std::copy_backward(__position, end(),
00832                              this->_M_impl._M_finish + difference_type(__n));
00833           std::fill(__position, __position + difference_type(__n), __x);
00834           this->_M_impl._M_finish += difference_type(__n);
00835         }
00836       else
00837         {
00838           const size_type __len = 
00839             _M_check_len(__n, "vector<bool>::_M_fill_insert");
00840           _Bit_pointer __q = this->_M_allocate(__len);
00841           iterator __start(std::__addressof(*__q), 0);
00842           iterator __i = _M_copy_aligned(begin(), __position, __start);
00843           std::fill(__i, __i + difference_type(__n), __x);
00844           iterator __finish = std::copy(__position, end(),
00845                                         __i + difference_type(__n));
00846           this->_M_deallocate();
00847           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00848           this->_M_impl._M_start = __start;
00849           this->_M_impl._M_finish = __finish;
00850         }
00851     }
00852 
00853   template<typename _Alloc>
00854     template<typename _ForwardIterator>
00855       void
00856       vector<bool, _Alloc>::
00857       _M_insert_range(iterator __position, _ForwardIterator __first, 
00858                       _ForwardIterator __last, std::forward_iterator_tag)
00859       {
00860         if (__first != __last)
00861           {
00862             size_type __n = std::distance(__first, __last);
00863             if (capacity() - size() >= __n)
00864               {
00865                 std::copy_backward(__position, end(),
00866                                    this->_M_impl._M_finish
00867                                    + difference_type(__n));
00868                 std::copy(__first, __last, __position);
00869                 this->_M_impl._M_finish += difference_type(__n);
00870               }
00871             else
00872               {
00873                 const size_type __len =
00874                   _M_check_len(__n, "vector<bool>::_M_insert_range");
00875                 _Bit_pointer __q = this->_M_allocate(__len);
00876                 iterator __start(std::__addressof(*__q), 0);
00877                 iterator __i = _M_copy_aligned(begin(), __position, __start);
00878                 __i = std::copy(__first, __last, __i);
00879                 iterator __finish = std::copy(__position, end(), __i);
00880                 this->_M_deallocate();
00881                 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00882                 this->_M_impl._M_start = __start;
00883                 this->_M_impl._M_finish = __finish;
00884               }
00885           }
00886       }
00887 
00888   template<typename _Alloc>
00889     void
00890     vector<bool, _Alloc>::
00891     _M_insert_aux(iterator __position, bool __x)
00892     {
00893       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
00894         {
00895           std::copy_backward(__position, this->_M_impl._M_finish, 
00896                              this->_M_impl._M_finish + 1);
00897           *__position = __x;
00898           ++this->_M_impl._M_finish;
00899         }
00900       else
00901         {
00902           const size_type __len =
00903             _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
00904           _Bit_pointer __q = this->_M_allocate(__len);
00905           iterator __start(std::__addressof(*__q), 0);
00906           iterator __i = _M_copy_aligned(begin(), __position, __start);
00907           *__i++ = __x;
00908           iterator __finish = std::copy(__position, end(), __i);
00909           this->_M_deallocate();
00910           this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
00911           this->_M_impl._M_start = __start;
00912           this->_M_impl._M_finish = __finish;
00913         }
00914     }
00915 
00916   template<typename _Alloc>
00917     typename vector<bool, _Alloc>::iterator
00918     vector<bool, _Alloc>::
00919     _M_erase(iterator __position)
00920     {
00921       if (__position + 1 != end())
00922         std::copy(__position + 1, end(), __position);
00923       --this->_M_impl._M_finish;
00924       return __position;
00925     }
00926 
00927   template<typename _Alloc>
00928     typename vector<bool, _Alloc>::iterator
00929     vector<bool, _Alloc>::
00930     _M_erase(iterator __first, iterator __last)
00931     {
00932       if (__first != __last)
00933         _M_erase_at_end(std::copy(__last, end(), __first));
00934       return __first;
00935     }
00936 
00937 #if __cplusplus >= 201103L
00938   template<typename _Alloc>
00939     bool
00940     vector<bool, _Alloc>::
00941     _M_shrink_to_fit()
00942     {
00943       if (capacity() - size() < int(_S_word_bit))
00944         return false;
00945       __try
00946         {
00947           _M_reallocate(size());
00948           return true;
00949         }
00950       __catch(...)
00951         { return false; }
00952     }
00953 #endif
00954 
00955 _GLIBCXX_END_NAMESPACE_CONTAINER
00956 _GLIBCXX_END_NAMESPACE_VERSION
00957 } // namespace std
00958 
00959 #if __cplusplus >= 201103L
00960 
00961 namespace std _GLIBCXX_VISIBILITY(default)
00962 {
00963 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00964 
00965   template<typename _Alloc>
00966     size_t
00967     hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
00968     operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
00969     {
00970       size_t __hash = 0;
00971       using _GLIBCXX_STD_C::_S_word_bit;
00972       using _GLIBCXX_STD_C::_Bit_type;
00973 
00974       const size_t __words = __b.size() / _S_word_bit;
00975       if (__words)
00976         {
00977           const size_t __clength = __words * sizeof(_Bit_type);
00978           __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
00979         }
00980 
00981       const size_t __extrabits = __b.size() % _S_word_bit;
00982       if (__extrabits)
00983         {
00984           _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
00985           __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
00986 
00987           const size_t __clength
00988             = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
00989           if (__words)
00990             __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
00991           else
00992             __hash = std::_Hash_impl::hash(&__hiword, __clength);
00993         }
00994 
00995       return __hash;
00996     }
00997 
00998 _GLIBCXX_END_NAMESPACE_VERSION
00999 } // namespace std
01000 
01001 #endif // C++11
01002 
01003 #undef _GLIBCXX_ASAN_ANNOTATE_REINIT
01004 #undef _GLIBCXX_ASAN_ANNOTATE_GROW
01005 #undef _GLIBCXX_ASAN_ANNOTATE_GREW
01006 #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
01007 
01008 #endif /* _VECTOR_TCC */