898 lines
29 KiB
C++
898 lines
29 KiB
C++
/***************************************************************************
|
|
*
|
|
* vector.cc - Non-inline definitions for the Standard Library vector class
|
|
*
|
|
* $Id: vector.cc 596318 2007-11-19 14:57:10Z faridz $
|
|
*
|
|
***************************************************************************
|
|
*
|
|
* Copyright (c) 1994
|
|
* Hewlett-Packard Company
|
|
*
|
|
* Permission to use, copy, modify, distribute and sell this software
|
|
* and its documentation for any purpose is hereby granted without fee,
|
|
* provided that the above copyright notice appear in all copies and
|
|
* that both that copyright notice and this permission notice appear
|
|
* in supporting documentation. Hewlett-Packard Company makes no
|
|
* representations about the suitability of this software for any
|
|
* purpose. It is provided "as is" without express or implied warranty.
|
|
*
|
|
***************************************************************************
|
|
*
|
|
* Licensed to the Apache Software Foundation (ASF) under one or more
|
|
* contributor license agreements. See the NOTICE file distributed
|
|
* with this work for additional information regarding copyright
|
|
* ownership. The ASF licenses this file to you under the Apache
|
|
* License, Version 2.0 (the "License"); you may not use this file
|
|
* except in compliance with the License. You may obtain a copy of
|
|
* the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
|
|
* implied. See the License for the specific language governing
|
|
* permissions and limitations under the License.
|
|
*
|
|
* Copyright 1994-2006 Rogue Wave Software.
|
|
*
|
|
**************************************************************************/
|
|
|
|
_RWSTD_NAMESPACE (std) {
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
vector<_TypeT, _Allocator>&
|
|
vector<_TypeT, _Allocator>::
|
|
operator= (const vector &__rhs)
|
|
{
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
if (capacity () < __rhs.size ())
|
|
vector (__rhs).swap (*this);
|
|
else if (&__rhs != this)
|
|
assign (__rhs.begin (), __rhs.end ());
|
|
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE)
|
|
|
|
vector (__rhs).swap (*this);
|
|
|
|
#endif // _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
return *this;
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void
|
|
vector<_TypeT, _Allocator>::
|
|
_C_realloc (size_type __n)
|
|
{
|
|
const size_type __max_size = max_size ();
|
|
|
|
// compute the new capacity from the greater of the current size
|
|
// and the requested size, but no greater than max_size()
|
|
size_type __cap = _RWSTD_NEW_CAPACITY (vector, this, (max)(size (), __n));
|
|
|
|
// do not exceed max_size()
|
|
if (__max_size < __cap)
|
|
__cap = __max_size;
|
|
|
|
// create an empty temporary vector
|
|
vector __tmp (get_allocator ());
|
|
|
|
// allocate storage of requested capacity
|
|
__tmp._C_begin =
|
|
_RWSTD_VALUE_ALLOC (_C_value_alloc_type, __tmp,
|
|
allocate (__cap, this));
|
|
|
|
// initialize pointers
|
|
__tmp._C_end = __tmp._C_begin;
|
|
__tmp._C_bufend = __tmp._C_begin + __cap;
|
|
|
|
// copy *this into the temporary one element at a time, as if
|
|
// by calling std::unitialized_copy(), growing the temporary
|
|
// at each iteration so that an exception thrown by the copy
|
|
// ctor will cause the destruction of all already constructed
|
|
// elements (by invoking the temporary's dtor)
|
|
for (pointer __ptr = _C_begin; !(__ptr == _C_end); ++__ptr) {
|
|
__tmp._C_push_back (*__ptr);
|
|
}
|
|
|
|
// swap *this with the temporary, having its dtor clean up
|
|
swap (__tmp);
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_destroy (iterator __first)
|
|
{
|
|
_RWSTD_ASSERT_RANGE (__first, end ());
|
|
|
|
_C_value_alloc_type __alloc = _RWSTD_VALUE_ALLOC_CAST (*this);
|
|
|
|
for (size_type __n = end () - __first; !(0 == __n); --__n)
|
|
__alloc.destroy (--_C_end);
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_unsafe_swap (vector &__other)
|
|
{
|
|
// called only from vector::swap() for unequal allocators
|
|
_RWSTD_ASSERT (!(get_allocator () == __other.get_allocator ()));
|
|
|
|
// avoid passing the whole object to other vector member
|
|
// functions (i.e., assign()) in case they are implemented
|
|
// in terms of swap(); use iterators instead
|
|
|
|
vector __tmp (__other.get_allocator ());
|
|
|
|
// assert that the copy of the allocator compares equal
|
|
// to the original (otherwise the swap() below will cause
|
|
// a recursive call)
|
|
_RWSTD_ASSERT (__tmp.get_allocator () == __other.get_allocator ());
|
|
|
|
__tmp.assign (begin (), end ());
|
|
__other.swap (__tmp);
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_assign_n (size_type __n, const_reference __x)
|
|
{
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
// FIXME: implement in-place assignment with repetition
|
|
|
|
clear ();
|
|
insert (begin (), __n, __x);
|
|
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE)
|
|
|
|
clear ();
|
|
insert (begin (), __n, __x);
|
|
|
|
#endif // _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_insert_1 (const iterator &__it, const_reference __x)
|
|
{
|
|
_RWSTD_ASSERT_RANGE (begin (), __it);
|
|
|
|
if (size () < capacity ()) {
|
|
|
|
if (__it < end ()) {
|
|
|
|
const pointer __end = _C_end;
|
|
|
|
// construct a copy of the last element in the range [it, end)
|
|
// in the uninitialized slot just past the end of the range
|
|
// and bump up end()
|
|
_C_push_back (*(_C_end - difference_type (1)));
|
|
|
|
// move the remaining elements from the range above one slot
|
|
// toward the end starting with the last element
|
|
_STD::copy_backward (__it, end () - 2, __end);
|
|
|
|
// overwrite the element at the given position
|
|
*__it = __x;
|
|
}
|
|
else {
|
|
// construct a copy of the value to be inserted
|
|
// in the uninitialized slot
|
|
_C_push_back (__x);
|
|
}
|
|
}
|
|
else {
|
|
_C_insert_n (__it, size_type (1), __x);
|
|
}
|
|
}
|
|
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_insert_n (const iterator &__it, size_type __n, const_reference __x)
|
|
{
|
|
_RWSTD_ASSERT_RANGE (begin (), __it);
|
|
|
|
if (!__n)
|
|
return;
|
|
|
|
// 23.2.4.2, p5: calls to insert() must not reallocate storage
|
|
// unless the new size of the container would exceed its capacity
|
|
|
|
// compute the numbers of elements to be copied and inserted
|
|
const size_type __size1 = _DISTANCE (begin (), __it, size_type);
|
|
const size_type __size2 = size () + __n;
|
|
|
|
if (capacity () < __size2) {
|
|
|
|
// allocate a temporary vector large enough to hold all elements
|
|
vector __tmp (get_allocator ());
|
|
__tmp.reserve (__size2);
|
|
|
|
_RWSTD_ASSERT (!(pointer () == __tmp._C_end));
|
|
|
|
iterator __i;
|
|
|
|
// copy the initial range prior to `it' as if by a call to
|
|
// std::uninitialized_copy (begin (), __it, __tmp._C_begin);
|
|
for (__i = begin (); !(__i == __it); ++__i) {
|
|
|
|
_RWSTD_ASSERT (!(__tmp._C_end == __tmp._C_bufend));
|
|
|
|
__tmp._C_push_back (*__i);
|
|
}
|
|
|
|
// construct `n' copies of `x' just past the initial range,
|
|
// as if by a call to
|
|
// std::uninitialized_fill_n (__tmp._C_begin + __size1, __n, __x);
|
|
for ( ; __n; --__n) {
|
|
|
|
_RWSTD_ASSERT (!(__tmp._C_end == __tmp._C_bufend));
|
|
|
|
__tmp._C_push_back (__x);
|
|
}
|
|
|
|
// copy the final range of elements starting with `it'
|
|
// as if by a call to
|
|
// uninitialized_copy (__it, end (), __tmp._C_begin + __size1 + __n);
|
|
|
|
for (__i = __it; !(__i == end ()); ++__i) {
|
|
|
|
_RWSTD_ASSERT (!(__tmp._C_end == __tmp._C_bufend));
|
|
|
|
__tmp._C_push_back (*__i);
|
|
}
|
|
|
|
// swap the sequences controlled by the temporary vector and *this
|
|
__tmp.swap (*this);
|
|
|
|
return;
|
|
}
|
|
|
|
// compute the beginning of the range of elements in the sequence
|
|
// controlled by *this that need to be moved (copy contructed past
|
|
// the end of the end of the sequence or assigned over existing
|
|
// elements)
|
|
const pointer __movbeg = _C_begin + __size1;
|
|
const pointer __movend = __movbeg + __n;
|
|
|
|
_RWSTD_ASSERT (_C_make_iter (__movbeg) == __it);
|
|
|
|
_C_value_alloc_type __alloc = _RWSTD_VALUE_ALLOC_CAST (*this);
|
|
|
|
if (__movend <= _C_end) {
|
|
|
|
// the end of the range of existing elements after being
|
|
// moved to make room for the elements to be inserted is
|
|
// before the current end of the sequence
|
|
|
|
// compute the beginning of the range of elements whose copies
|
|
// will be constructed just past the current end of the sequence
|
|
const pointer __ucpbeg = _C_end - __n;
|
|
const pointer __ucpend = _C_end;
|
|
|
|
// construct copies of elements that will be moved beyond
|
|
// the current end of the sequence controlled by *this
|
|
_STD::uninitialized_copy (__ucpbeg, _C_end, _C_end, __alloc);
|
|
|
|
// advance end to maintain consistent state
|
|
_C_end += __n;
|
|
|
|
// copy elements the will be overwritten below
|
|
// over the range of elements moved above
|
|
_STD::copy_backward (__movbeg, __ucpbeg, __ucpend);
|
|
}
|
|
else {
|
|
|
|
// compute the length of the initial subsequence of the range
|
|
// of element being inserted that overlaps the end of the
|
|
// sequence being inserted into
|
|
const size_type __n1 = size () - __size1;
|
|
const size_type __n2 = __n - __n1;
|
|
|
|
_STD::uninitialized_fill_n (_C_end, __n2, __x, __alloc);
|
|
|
|
const pointer __end = _C_end;
|
|
|
|
_C_end += __n2;
|
|
|
|
// construct copies of the range of elements [pos, end)
|
|
// past the end of the range of elements inserted above
|
|
_STD::uninitialized_copy (__movbeg, __end, _C_end, __alloc);
|
|
|
|
_C_end += __end - __movbeg;
|
|
|
|
__n = __n1;
|
|
}
|
|
|
|
_STD::fill_n (__movbeg, __n, __x);
|
|
}
|
|
|
|
|
|
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
template<class _TypeT, class _Allocator>
|
|
template<class _InputIter>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_assign_range (_InputIter __first, _InputIter __last, input_iterator_tag)
|
|
{
|
|
vector* const __self = this;
|
|
|
|
#else // if defined (_RWSTD_NO_MEMBER_TEMPLATES)
|
|
|
|
template<class _TypeT, class _Allocator, class _InputIter>
|
|
void
|
|
__rw_assign_range (vector<_TypeT, _Allocator> *__self,
|
|
_InputIter __first, _InputIter __last, input_iterator_tag)
|
|
{
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::iterator iterator;
|
|
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
_RWSTD_ASSERT_RANGE (__first, __last);
|
|
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
// assign over existing elements for better efficiency
|
|
// and exception safety
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// -- exactly A=min(size(), distance(first, last)) calls
|
|
// to value_type's assignment operator
|
|
// -- exactly (max(size(), distance(first, last)) - A)
|
|
// calls to value_type's copy ctor
|
|
//
|
|
// exception safety:
|
|
// -- nothrow if size() >= distance(first, last), and value_type's
|
|
// assignment operator and iterator operations do not throw
|
|
// -- basic otherwise
|
|
|
|
const iterator __end = __self->end ();
|
|
|
|
for (iterator __it = __self->begin (); __it != __end; ++__it, ++__first) {
|
|
if (__first == __last) {
|
|
__self->erase (__it, __end);
|
|
return;
|
|
}
|
|
*__it = *__first;
|
|
}
|
|
|
|
__self->insert (__end, __first, __last);
|
|
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE)
|
|
|
|
// follow the inefficient requirement in 23.2.4.1, p2
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// exactly distance(first, last) calls to value_type's copy ctor
|
|
// exception safety: basic
|
|
|
|
__self->clear ();
|
|
__self->insert (__self->begin (), __first, __last);
|
|
|
|
#endif // _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
}
|
|
|
|
|
|
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
template <class _FwdIter>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_assign_range (_FwdIter __first, _FwdIter __last, forward_iterator_tag)
|
|
{
|
|
vector* const __self = this;
|
|
|
|
#else // if defined (_RWSTD_NO_MEMBER_TEMPLATES)
|
|
|
|
template <class _TypeT, class _Allocator, class _FwdIter>
|
|
void
|
|
__rw_assign_range (vector<_TypeT, _Allocator> *__self,
|
|
_FwdIter __first, _FwdIter __last, forward_iterator_tag)
|
|
{
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::value_type value_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::allocator_type
|
|
allocator_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::_C_value_alloc_type
|
|
_C_value_alloc_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::size_type size_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::iterator iterator;
|
|
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
_RWSTD_ASSERT_RANGE (__first, __last);
|
|
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
// assign over existing elements for better efficiency
|
|
// and exception safety
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// exception safety:
|
|
// -- nothrow if size() >= distance(first, last), and value_type's
|
|
// assignment operator and iterator operations do not throw
|
|
// -- strong if capacity() < size() + distance(first, last)
|
|
// -- basic otherwise
|
|
|
|
const size_type __size1 = _DISTANCE (__first, __last, size_type);
|
|
const size_type __size2 = __self->size () + __size1;
|
|
|
|
if (__self->capacity () < __size2) {
|
|
|
|
// exception safety: strong
|
|
|
|
vector<value_type, allocator_type> __tmp (__self->get_allocator ());
|
|
__tmp.reserve (__size2);
|
|
|
|
// copy elements in the range [first, last) into the temporary
|
|
// one element at a time, as if by calling
|
|
// std::unitialized_copy(), growing the temporary at each
|
|
// iteration so that an exception thrown by the copy ctor will
|
|
// cause the destruction of all already constructed elements
|
|
// (by invoking the temporary's dtor)
|
|
for ( ; !(__first == __last); ++__first)
|
|
__tmp._C_push_back (*__first);
|
|
|
|
// swap *this with the temporary, having its dtor clean up
|
|
__self->swap (__tmp);
|
|
}
|
|
else {
|
|
// exception safety: nothrow or basic
|
|
|
|
const iterator __end = __self->end ();
|
|
|
|
for (iterator __i = __self->begin (); __i != __end; ++__i, ++__first) {
|
|
if (__first == __last) {
|
|
__self->erase (__i, __end);
|
|
return;
|
|
}
|
|
*__i = *__first;
|
|
}
|
|
|
|
__self->insert (__end, __first, __last);
|
|
}
|
|
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE)
|
|
|
|
// follow the inefficient requirement in 23.2.4.1, p2
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// exception safety: basic
|
|
|
|
__self->clear ();
|
|
__self->insert (__self->begin (), __first, __last);
|
|
|
|
#endif // _RWSTD_NO_EXT_VECTOR_ASSIGN_IN_PLACE
|
|
|
|
}
|
|
|
|
|
|
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
template <class _InputIter>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_insert_range (iterator __it, _InputIter __first, _InputIter __last,
|
|
input_iterator_tag)
|
|
{
|
|
vector* const __self = this;
|
|
|
|
#else // if defined (_RWSTD_NO_MEMBER_TEMPLATES)
|
|
|
|
template <class _TypeT, class _Allocator, class _VectorIter, class _InputIter>
|
|
void
|
|
__rw_insert_range (vector<_TypeT, _Allocator> *__self, _VectorIter __it,
|
|
_InputIter __first, _InputIter __last, input_iterator_tag)
|
|
{
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::value_type value_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::allocator_type
|
|
allocator_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::size_type size_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::pointer pointer;
|
|
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
_RWSTD_ASSERT_RANGE (__it, end ());
|
|
_RWSTD_ASSERT_RANGE (__first, __last);
|
|
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE
|
|
|
|
// note that this extension does not satisfy the strong exception
|
|
// safety requirement in 23.2.4.3, p1
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// exception safety: basic
|
|
|
|
// append one element at a time to prevent the loss of data
|
|
// from the input sequence in the case of an exception
|
|
|
|
const size_type __size = __self->size ();
|
|
const size_type __inx = _DISTANCE (__self->begin (), __it, size_type);
|
|
|
|
_RWSTD_ASSERT (__inx <= __size);
|
|
|
|
for (; !(__first == __last); ++__first)
|
|
__self->push_back (*__first);
|
|
|
|
if (__inx < __size) {
|
|
// swap the inserted elements with the elements before which
|
|
// they should be inserted, as if by calling
|
|
// std::rotate (__beg, __mid, _C_end)
|
|
const pointer __beg = __self->_C_begin + __inx;
|
|
const pointer __mid = __self->_C_begin + __size;
|
|
|
|
if (__beg < __mid) {
|
|
for (pointer __p0 = __beg, __p1 = __mid; __p0 < --__p1; ++__p0)
|
|
_STD::iter_swap (__p0, __p1);
|
|
}
|
|
|
|
if (__mid < __self->_C_end) {
|
|
for (pointer __p0 = __mid, __p1 = __self->_C_end;
|
|
__p0 < --__p1; ++__p0)
|
|
_STD::iter_swap (__p0, __p1);
|
|
}
|
|
|
|
if (__beg < __self->_C_end) {
|
|
for (pointer __p0 = __beg, __p1 = __self->_C_end;
|
|
__p0 < --__p1; ++__p0)
|
|
_STD::iter_swap (__p0, __p1);
|
|
}
|
|
}
|
|
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE)
|
|
|
|
// 23.2.4.3, p1: If an exception is thrown other than by the copy
|
|
// constructor or assignment operator of T there are no effects.
|
|
// see also lwg issue 406
|
|
|
|
// complexity: linear in distance(first, last)
|
|
// exception safety:
|
|
// -- strong if capacity() < size() + distance(first, last) and
|
|
// value_type's assignment operator and copy ctor do not throw
|
|
// -- basic otherwise
|
|
|
|
// insert input range into a temporary sequence rather than into *this
|
|
// to coid modifying *this in case an exception (e.g., bad_alloc) is
|
|
// thrown
|
|
vector<value_type, allocator_type> __tmp (__self->get_allocator ());
|
|
|
|
for ( ; !(__first == __last); ++__first)
|
|
__tmp.push_back (*__first);
|
|
|
|
// insert into *this using a more efficient algorithm optimized
|
|
// for BidirectionalIterator (and better)
|
|
__self->insert (__it, __tmp.begin (), __tmp.end ());
|
|
|
|
#endif // _RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE
|
|
|
|
}
|
|
|
|
|
|
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
template <class _TypeT, class _Allocator>
|
|
template <class _FwdIter>
|
|
void vector<_TypeT, _Allocator>::
|
|
_C_insert_range (iterator __it, _FwdIter __first, _FwdIter __last,
|
|
forward_iterator_tag)
|
|
{
|
|
vector* const __self = this;
|
|
|
|
#else // if defined (_RWSTD_NO_MEMBER_TEMPLATES)
|
|
|
|
template <class _TypeT, class _Allocator, class _VectorIter, class _FwdIter>
|
|
void
|
|
__rw_insert_range (vector<_TypeT, _Allocator> *__self, _VectorIter __it,
|
|
_FwdIter __first, _FwdIter __last,
|
|
forward_iterator_tag)
|
|
{
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::value_type value_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::allocator_type
|
|
allocator_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::_C_value_alloc_type
|
|
_C_value_alloc_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::size_type size_type;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::pointer pointer;
|
|
typedef _TYPENAME vector<_TypeT, _Allocator>::iterator iterator;
|
|
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
_RWSTD_ASSERT_RANGE (__it, end ());
|
|
_RWSTD_ASSERT_RANGE (__first, __last);
|
|
|
|
// 23.2.4.2, p5: calls to insert() must not reallocate storage
|
|
// unless the new size of the container would exceed its capacity
|
|
|
|
// compute the sizes of the ranges of elements to be copied
|
|
const size_type __size1 = _DISTANCE (__self->begin (), __it, size_type);
|
|
const size_type __size2 = _DISTANCE (__first, __last, size_type);
|
|
|
|
if (!__size2)
|
|
return;
|
|
|
|
#ifndef _RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE
|
|
const bool __insert_in_place =
|
|
__self->size () + __size2 <= __self->capacity ();
|
|
#else // if defined (_RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE)
|
|
const bool __insert_in_place = false;
|
|
#endif // _RWSTD_NO_EXT_VECTOR_INSERT_IN_PLACE
|
|
|
|
if (__insert_in_place) {
|
|
|
|
// compute the beginning an end of the range of elements
|
|
// in the sequence controlled by *this that need to be moved
|
|
// (copy contructed past the end of the end of the sequence
|
|
// or assigned over existing elements)
|
|
const pointer __movbeg = __self->_C_begin + __size1;
|
|
const pointer __movend = __movbeg + __size2;
|
|
|
|
_RWSTD_ASSERT (__self->_C_make_iter (__movbeg) == __it);
|
|
|
|
const pointer __end = __self->_C_end;
|
|
|
|
if (__movend <= __end) {
|
|
// compute the beginning of the range of elements whose copies
|
|
// will be copy-constructed in the uninitialized space just past
|
|
// the current end of the sequence
|
|
const pointer __ucpbeg = __end - __size2;
|
|
|
|
// construct copies of elements that will be moved beyond
|
|
// the current end of the sequence controlled by *this
|
|
for (pointer __p = __ucpbeg; !(__p == __end); ++__p)
|
|
__self->_C_push_back (*__p);
|
|
|
|
// over the range of elements moved above
|
|
for (pointer __q = __end; __movend < __q; ) {
|
|
--__q;
|
|
*__q = *(__q - __size2);
|
|
}
|
|
}
|
|
else {
|
|
// compute the length of the initial subsequence of the range
|
|
// of elements being inserted that overlaps the end of the
|
|
// sequence being inserted into
|
|
const size_type __size2a = __self->size () - __size1;
|
|
_FwdIter __mid = __first;
|
|
_STD::advance (__mid, __size2a);
|
|
|
|
// construct copies of the trailing subsequence of the range
|
|
// of elements being inserted, as if by a call to
|
|
// std::uninitialized_copy (__mid, __last, _C_end);
|
|
|
|
for (_FwdIter __m = __mid ; !(__m == __last); ++__m)
|
|
__self->_C_push_back (*__m);
|
|
|
|
// construct copies of the range of elements [pos, end)
|
|
// past the end of the range of elements inserted above,
|
|
// as if by a call to
|
|
// std::uninitialized_copy (__movbeg, __end, _C_end);
|
|
|
|
for (pointer __p = __movbeg; !(__p == __end); ++__p)
|
|
__self->_C_push_back (*__p);
|
|
|
|
__last = __mid;
|
|
}
|
|
|
|
_STD::copy (__first, __last, __movbeg);
|
|
}
|
|
else {
|
|
// 23.2.4.3, p1: If an exception is thrown other than by the copy
|
|
// constructor or assignment operator of T there are no effects.
|
|
|
|
// create a temporary vector and reserve sufficient space
|
|
vector<value_type, allocator_type> __tmp (__self->get_allocator ());
|
|
|
|
__tmp.reserve (__self->size () + __size2);
|
|
|
|
// avoid using the name __i or __it below so as not to trigger
|
|
// a (bogus) gcc 2.95.2 -Wshadow warning: declaration of `__i'
|
|
// shadows previous local
|
|
iterator __ix;
|
|
|
|
// copy the initial subsequence of *this, [begin, it), into
|
|
// the temporary one element at a time, as if by calling
|
|
// std::unitialized_copy(), growing the temporary at each
|
|
// iteration so that an exception thrown by the copy ctor
|
|
// will cause the destruction of all already constructed
|
|
// elements (by invoking the temporary's dtor)
|
|
for (__ix = __self->begin (); __ix != __it; ++__ix) {
|
|
__tmp._C_push_back (*__ix);
|
|
}
|
|
|
|
// append the sequence [first, last) to the temporary,
|
|
// carefully increasing the size of tmp before performing
|
|
// any operations on `first' and `last' in case they throw
|
|
for (; !(__first == __last); ++__first) {
|
|
__tmp._C_push_back (*__first);
|
|
}
|
|
|
|
// copy the remaining elements from *this
|
|
for ( ; __ix != __self->end (); ++__ix) {
|
|
__tmp._C_push_back (*__ix);
|
|
}
|
|
|
|
// swap *this with the temporary, having its dtor clean up
|
|
__self->swap (__tmp);
|
|
}
|
|
}
|
|
|
|
/***************************************************************************/
|
|
|
|
#ifndef _RWSTD_NO_VECTOR_BOOL
|
|
|
|
#ifndef _RWSTD_NO_BOOL
|
|
|
|
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
|
|
// The body of this function is duplicated in src/vecbool.cpp and
|
|
// further down in this file as well.
|
|
#if !defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)
|
|
template <class _Allocator>
|
|
template<class _InputIter>
|
|
void vector<bool, _Allocator >::insert
|
|
#else
|
|
template<class _InputIter>
|
|
void vector<bool, allocator<bool> >::insert
|
|
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC
|
|
(iterator __it, _InputIter __first, _InputIter __last)
|
|
|
|
{
|
|
if (__first == __last) return;
|
|
size_type __n = _DISTANCE (__first, __last, size_type);
|
|
if (capacity() - size() >= __n)
|
|
{
|
|
copy_backward(__it, end(), _C_end + __n);
|
|
copy(__first, __last, __it);
|
|
_C_end += __n;
|
|
}
|
|
else
|
|
{
|
|
size_type __len = size() + (max)(size(), __n);
|
|
|
|
unsigned int* __q = _C_bit_alloc(__len);
|
|
iterator __i = copy(begin(), __it, iterator(__q, 0));
|
|
__i = copy(__first, __last, __i);
|
|
_C_end = copy(__it, end(), __i);
|
|
_C_value_alloc_type (*this).
|
|
deallocate((pointer)_C_begin._C_p,_C_bufend - _C_begin._C_p);
|
|
_C_bufend = __q + (__len + _RWSTD_WORD_BIT - 1)/_RWSTD_WORD_BIT;
|
|
_C_begin = iterator(__q, 0);
|
|
}
|
|
}
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
|
|
|
|
// Duplicates of the following functions exist in src/stl/vecbool.cpp.
|
|
// Which set is used depends on the availability of partial specialization.
|
|
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::flip ()
|
|
{
|
|
for (iterator __i = begin(); !(__i == end()); __i++)
|
|
*__i = !(*__i);
|
|
}
|
|
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::swap (reference __x, reference __y)
|
|
{
|
|
bool __tmp = __x; __x = __y; __y = __tmp;
|
|
}
|
|
|
|
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::
|
|
_C_insert (iterator __it, bool __x)
|
|
{
|
|
_RWSTD_ASSERT_RANGE (begin (), __it);
|
|
|
|
if (size () < capacity ()) {
|
|
|
|
const iterator __end = _C_end;
|
|
|
|
// move elements in the range [it, end) before the insert
|
|
// one slot toward the end
|
|
// i.e., copy [it, end) over [end - (end - it), end)
|
|
// or, given N = distance(it, end) before the insert,
|
|
// copy [it, end) over [end - N, end)
|
|
_STD::copy_backward (__it, __end, ++_C_end);
|
|
|
|
// overwrite the element at the given position
|
|
*__it = __x;
|
|
}
|
|
else
|
|
{
|
|
size_type __len = size() ? 2 * size() : _RWSTD_WORD_BIT;
|
|
unsigned int* __q = _C_bit_alloc(__len);
|
|
iterator __i = _C_copy(begin(), __it, iterator(__q, 0));
|
|
*__i++ = __x;
|
|
_C_end = _C_copy(__it, end(), __i);
|
|
_C_value_alloc_type (*this).
|
|
deallocate((pointer)_C_begin._C_p,_C_bufend - _C_begin._C_p);
|
|
_C_bufend = __q + (__len + _RWSTD_WORD_BIT - 1)/_RWSTD_WORD_BIT;
|
|
_C_begin = iterator(__q, 0);
|
|
}
|
|
}
|
|
|
|
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::insert (iterator __it, size_type __n,
|
|
const bool& __x)
|
|
{
|
|
if (__n == 0) return;
|
|
if (capacity() - size() >= __n)
|
|
{
|
|
_C_copy_backward(__it, end(), _C_end + __n);
|
|
_C_fill(__it, __it + __n, __x);
|
|
_C_end += __n;
|
|
}
|
|
else
|
|
{
|
|
size_type __len = size() + (max)(size(), __n);
|
|
unsigned int* __q = _C_bit_alloc(__len);
|
|
iterator __i = _C_copy(begin(), __it, iterator(__q, 0));
|
|
_C_fill_n(__i, __n, __x);
|
|
_C_end = _C_copy(__it, end(), __i + __n);
|
|
_C_value_alloc_type (*this).
|
|
deallocate((pointer)_C_begin._C_p,_C_bufend - _C_begin._C_p);
|
|
_C_bufend = __q + (__len + _RWSTD_WORD_BIT - 1)/_RWSTD_WORD_BIT;
|
|
_C_begin = iterator(__q, 0);
|
|
}
|
|
}
|
|
|
|
|
|
#ifdef _RWSTD_NO_MEMBER_TEMPLATES
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::insert (iterator __it,
|
|
const_iterator __first,
|
|
const_iterator __last)
|
|
{
|
|
if (__first == __last) return;
|
|
size_type __n = _DISTANCE(__first, __last, size_type);
|
|
if (capacity() - size() >= __n)
|
|
{
|
|
_C_copy_backward(__it, end(), _C_end + __n);
|
|
_C_copy(__first, __last, __it);
|
|
_C_end += __n;
|
|
}
|
|
else
|
|
{
|
|
size_type __len = size() + (max)(size(), __n);
|
|
unsigned int* __q = _C_bit_alloc(__len);
|
|
iterator __i = _C_copy(begin(), __it, iterator(__q, 0));
|
|
__i = _C_copy(__first, __last, __i);
|
|
_C_end = _C_copy(__it, end(), __i);
|
|
_C_value_alloc_type (*this).
|
|
deallocate((pointer)_C_begin._C_p,_C_bufend - _C_begin._C_p);
|
|
_C_bufend = __q + (__len + _RWSTD_WORD_BIT - 1)/_RWSTD_WORD_BIT;
|
|
_C_begin = iterator(__q, 0);
|
|
}
|
|
}
|
|
#endif // _RWSTD_NO_MEMBER_TEMPLATES
|
|
|
|
template <class _Allocator>
|
|
void vector<bool,_Allocator >::resize (size_type __new_size, bool __c)
|
|
{
|
|
if (__new_size > size())
|
|
insert(end(), __new_size - size(), __c);
|
|
else if (__new_size < size())
|
|
erase(begin() + __new_size, end());
|
|
}
|
|
|
|
#endif // _RWSTD_NO_CLASS_PARTIAL_SPEC
|
|
|
|
#endif // _RWSTD_NO_BOOL
|
|
|
|
#endif // _RWSTD_NO_VECTOR_BOOL
|
|
|
|
} // namespace std
|