deque.cc

Go to the documentation of this file.

 
_RWSTD_NAMESPACE (std) { 
 
 
template <class _TypeT, class _Allocator>
deque<_TypeT, _Allocator>&
deque<_TypeT, _Allocator>::
operator= (const deque &__rhs)
{
    _RWSTD_ASSERT (_C_is_valid ());
    _RWSTD_ASSERT (__rhs._C_is_valid ());
 
    const size_type __size = size ();
 
    if (__size < __rhs.size ()) {
        const const_iterator __mid = __rhs.begin () + __size;
 
        _STD::copy (__mid, __rhs.end (),
                    _STD::inserter (*this, _STD::copy (__rhs.begin (), __mid,
                                                       begin ())));
    }
    else
        erase (_STD::copy (__rhs.begin (), __rhs.end (), begin ()), end ());
 
    return *this;
}
 
 
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator 
deque<_TypeT, _Allocator>::
insert (iterator __it, const_reference __x)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);
    _RWSTD_ASSERT (_C_is_valid ());
 
    if (__it == begin ()) {
        push_front (__x);
        return begin ();
    }
 
    if (__it == end ()) {
        push_back (__x);
        __it = end () - 1;
        return __it;
    }
 
    const size_type __inx = _DISTANCE (begin (), __it, size_type);
 
    _RWSTD_ASSERT (__inx < size ());
 
    if (__inx < size () - __inx) {
        push_front (front ());
        _STD::copy (begin () + 2, begin () + (__inx + 1), begin () + 1);
    }
    else {
        push_back (back ());
 
        _STD::copy_backward (begin () + __inx, end () - 2, end () - 1);
    }
 
    __it = begin () + __inx;
 
    *__it = __x;
 
    return __it;
}
 
 
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator 
deque<_TypeT, _Allocator>::
erase (iterator __it)
{
    // `it' must be a dereferenceable iterator into `*this'
 
    _RWSTD_ASSERT_RANGE (begin (), __it);
    _RWSTD_ASSERT (!(__it == end ()));
    _RWSTD_ASSERT (_C_is_valid (0 /* valid and non-empty */));
 
    const iterator __next = ++iterator (__it);
 
    if (__it - begin () < end () - __it) {
 
        _STD::copy_backward (begin (), __it, __next);
 
        pop_front ();
 
        return empty () ? end () : __next;
    }
 
    _STD::copy (__next, end (), __it);
 
    pop_back ();
 
    return __it;
}
    
 
template <class _TypeT, class _Allocator>
typename deque<_TypeT, _Allocator>::iterator 
deque<_TypeT, _Allocator>::
erase (iterator __first, iterator __last)
{
    // (`first', `last'] must be a valid range into `*this'
 
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT_RANGE (begin (), __first);
    _RWSTD_ASSERT (_C_is_valid ());
 
    size_type __n = _DISTANCE (__first, __last, size_type);
 
    _RWSTD_ASSERT (__n <= size ());
 
    if (__first - begin () < end () - __last) {
 
        _STD::copy_backward (begin (), __first, __last);
 
        while (__n-- != 0)
            pop_front ();
 
        return __last;
    }
 
    _STD::copy (__last, end (), __first);
 
    while (__n-- != 0)
        pop_back ();
 
    return __first;
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
swap (deque<_TypeT, _Allocator> &__rhs)
{
    _RWSTD_ASSERT (_C_is_valid ());
    _RWSTD_ASSERT (__rhs._C_is_valid ());
 
    if (get_allocator () == __rhs.get_allocator ()) {
 
        _STD::swap (_C_beg,       __rhs._C_beg);
        _STD::swap (_C_end,       __rhs._C_end);
        _STD::swap (_C_nodes,     __rhs._C_nodes);
        _STD::swap (_C_node_size, __rhs._C_node_size);
 
        if (pointer() == _C_beg._C_cur) {
            _RWSTD_ASSERT (pointer() == _C_end._C_cur);
            _RWSTD_ASSERT (   _C_beg._C_node == &__rhs._C_end._C_cur
                           && _C_end._C_node == &__rhs._C_end._C_cur);
 
            _C_beg._C_node =
            _C_end._C_node = &_C_end._C_cur;
        }
        else {
            _RWSTD_ASSERT (pointer() != _C_end._C_cur);
        }
 
        if (pointer() == __rhs._C_beg._C_cur) {
            _RWSTD_ASSERT (pointer() == __rhs._C_end._C_cur);
            _RWSTD_ASSERT (   __rhs._C_beg._C_node == &_C_end._C_cur
                           && __rhs._C_end._C_node == &_C_end._C_cur);
 
            __rhs._C_beg._C_node =
            __rhs._C_end._C_node = &__rhs._C_end._C_cur;
        }
        else {
            _RWSTD_ASSERT (pointer() != __rhs._C_end._C_cur);
        }
    }
    else {
        deque __tmp (*this);
        *this = __rhs;
        __rhs = __tmp;
    }
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_push (bool __at_back, const_reference __x)
{
    _RWSTD_ASSERT (_C_is_valid ());
 
    const size_type __bufsize = _C_bufsize ();
 
    _C_value_alloc_type __alloc (*this);
 
    // allocate a new buffer to store elements in
    const pointer __buf = __alloc.allocate (__bufsize, pointer ());
 
    const bool __empty = empty ();
 
    if (   __empty
        || (__at_back && _C_end._C_node == _C_nodes + _C_node_size - 1)
        || (!__at_back && _C_beg._C_node == _C_nodes)) {
 
        _C_node_alloc_type __node_alloc (*this);
 
        _RWSTD_ASSERT (_C_beg._C_node <= _C_end._C_node);
 
        // compute the current number of used nodes
        // and the new number of nodes
 
        const _C_node_pointer __end = _C_end._C_node + !__empty;
 
        const size_type __nodes = size_type (__end - _C_beg._C_node);
 
        // obtain the next greater number of nodes for the new vector
        const size_type __nvecsize = _C_vecsize (__nodes);
 
        _RWSTD_ASSERT (__nvecsize > __nodes);
 
        // compute the beginning of the old (current) vector
        const _C_node_pointer __ovec = _C_nodes - !__empty;
        _C_node_pointer __nvec;
 
        _TRY {
            // allocate enough for two extra unused nodes
            __nvec = __node_alloc.allocate (__nvecsize + 2, __ovec);
 
            _RWSTD_ASSERT (!(_C_node_pointer () == __nvec));
 
            const pointer __where = __buf
                + (  __empty ? __bufsize / 2 - !__at_back
                   : __at_back ? 0 : __bufsize - 1);
 
            _TRY {
                __alloc.construct (__where, __x);
            }
            _CATCH (...) {
                __node_alloc.deallocate (__nvec, __nvecsize + 2);
                _RETHROW;
            }
 
            // reserve the first and last nodes (must always be 0)
            ++__nvec;
        }
        _CATCH (...) {
            // deallocate buffer and rethrow
            __alloc.deallocate (__buf, __bufsize);
            _RETHROW;
        }
 
        // compute the new indices into the newly allocated vector
        // of the first and last occuppied node, respectively
        const size_type __beg_inx = __nvecsize / (__empty ? 2 : 4);
        const size_type __end_inx = __beg_inx + __nodes;
 
        // copy existing nodes into the new buffer
        _STD::copy (_C_beg._C_node, __end, __nvec + (__beg_inx + !__at_back));
 
        // deallocate the current buffer only when non-0 to satisfy
        // the requirement that deallocate() argument be non-zero
        if (!(__ovec == _C_node_pointer ()))
            __node_alloc.deallocate (__ovec, _C_node_size + 2);
 
        // set the pointer and size
        _C_nodes     = __nvec;
        _C_node_size = __nvecsize;
 
        // insert the fixed-size array into the vector of nodes...
        if (__at_back) {
 
            // ...at the end
            _C_nodes [__end_inx] = __buf;
 
            _C_beg._C_node = _C_nodes + __beg_inx;
            _C_end = _C_deque_iter (__buf, _C_nodes + __end_inx);
 
        }
        else {
            // ...at the beginning
            _C_nodes [__beg_inx] = __buf;
 
            _C_beg = _C_deque_iter (__buf + __bufsize, _C_nodes + __beg_inx);
            _C_end._C_node = _C_nodes + __end_inx;
        }
 
        if (__empty) {
            // set the beginning and end pointers both
            // to point at the same (future) element
            _C_beg._C_cur =
            _C_end._C_cur = __buf + __bufsize / 2;
        }
    }
    else {
        _RWSTD_ASSERT (_C_is_valid (0 /* valid and non-empty */));
 
        _TRY {
 
            if (__at_back) {
                __alloc.construct (__buf, __x);
 
                // append the newly allocated buffer to the end of the vector
                // of pointers and increment `end' to point at the first
                // element in it; zero out the following node
                *++_C_end._C_node  = __buf;
                _C_end._C_cur      = __buf;
            }
            else {
                __alloc.construct (__buf + (__bufsize - 1), __x);
 
                // prepend the newly allocated buffer to the beginning of
                // the vector of pointers and decrement `begin' to point
                // at the last element in it; zero out the preceding node
                *--_C_beg._C_node   = __buf;
                _C_beg._C_cur       = __buf + __bufsize;
            }
        }
        _CATCH (...) {
            __alloc.deallocate (__buf, __bufsize);
 
            _RETHROW;
        }
    }
 
    _C_end._C_node [+1] = pointer ();
    _C_beg._C_node [-1] = pointer ();
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_free_at_begin ()
{
    const size_type __bufsize = _C_bufsize ();
 
    _RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this,
                        deallocate (*_C_beg._C_node, __bufsize));
    if (empty ()) {
        _C_node_alloc_type (*this).
            deallocate (_C_nodes - 1, _C_node_size + 2);
        _C_init ();
    }
    else {
        *_C_beg._C_node++ = pointer ();
        _C_beg = _C_deque_iter (*_C_beg._C_node, _C_beg._C_node);
    }
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_free_at_end ()
{
    const size_type __bufsize = _C_bufsize ();
 
    _RWSTD_VALUE_ALLOC (_C_value_alloc_type, *this,
                        deallocate (*_C_end._C_node, __bufsize));
    if (empty ()) {
        _C_node_alloc_type (*this).
            deallocate (_C_nodes - 1, _C_node_size + 2);
        _C_init ();
    }
    else {
        *_C_end._C_node-- = pointer ();
        _C_end = _C_deque_iter (*_C_end._C_node + __bufsize, _C_end._C_node);
    }
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_assign_n (size_type __n, const_reference __x)
{
    _RWSTD_ASSERT (_C_is_valid ());
 
#ifndef _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
 
    // assign over existing elements for better efficiency
    // and exception safety
 
    // complexity: linear in n
    // exception safety:
    // -- nothrow if size() >= n, and value_type's assignment operator
    //    and iterator operations do not throw
    // -- basic otherwise
 
    const iterator __end = end ();
 
    // 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
    for (iterator __ix = begin (); !(__ix == __end); ++__ix, --__n) {
        if (size_type () == __n) {
            erase (__ix, __end);
            return;
        }
        *__ix = __x;
    }
 
    insert (__end, __n, __x);
 
#else   // if defined (_RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE)
 
    // follow the inefficient requirement in 23.2.1.1, p8
 
    // complexity: linear in n
    // exception safety: basic
 
    clear ();
    insert (begin (), __n, __x);
 
#endif   // _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
 
}
 
 
template <class _TypeT, class _Allocator>
void deque<_TypeT, _Allocator>::
_C_insert_n (const iterator &__it, size_type __n, const_reference __x)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);
    _RWSTD_ASSERT (_C_is_valid ());
 
    const size_type __inx = _DISTANCE (begin (), __it, size_type);
    const size_type __rem = size () - __inx;
 
    _RWSTD_ASSERT (__inx <= size ());
 
    if (__inx < __rem) {
 
        // inserting `x' into the first half of the container
 
        if (__inx < __n) {
            
            for (size_type __i = __n - __inx; __i; --__i)
                push_front (__x);
 
            for (size_type __j = __inx; __j; --__j)
                push_front (*(begin () + (__n - 1)));
 
            _STD::fill (begin () + __n, begin () + (__n + __inx), __x);
        }
        else if (__n) {
 
            for (size_type __i = __n; __i; --__i)
                push_front (*(begin () + __n - 1));
 
            const iterator __tmp = begin () + __n;
 
            _STD::copy (__tmp + __n, __tmp + __inx, __tmp);
 
            _STD::fill (begin () + __inx, __tmp + __inx, __x);
        }
    }
    else {
 
        // inserting `x' into the second half of the container
 
        const size_type __size0 = size ();
 
        if (__rem < __n) {
 
            for (size_type __i = __n - __rem; __i; --__i)
                push_back (__x);
 
            for (size_type __j = 0; __j != __rem; ++__j)
                push_back (*(begin () + (__inx + __j)));
 
            _STD::fill (begin () + __inx, begin () + __size0, __x);
        }
        else if (__n) {
 
            for (size_type __i = 0;__i != __n; ++__i)
                push_back (*(begin () + __size0 - __n + __i));
 
            const iterator __tmp = begin () + __inx;
 
            _STD::copy_backward (__tmp, begin () + __size0 - __n, 
                                 begin () + __size0);
 
            _STD::fill (__tmp, __tmp + __n, __x);
        }
    }
}
 
 
template <class _TypeT, class _Allocator>
template <class _InputIter>
void deque<_TypeT, _Allocator>::
_C_assign_range (_InputIter __first, _InputIter __last, input_iterator_tag)
{
    typedef deque _Deque;
 
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT (this->_C_is_valid ());
 
#ifndef _RWSTD_NO_EXT_DEQUE_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
    // -- basic otherwise
 
    const iterator __end = this->end ();
 
    // 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
    for (iterator __ix = this->begin (); !(__ix == __end);
         ++__ix, ++__first) {
        if (__first == __last) {
            this->erase (__ix, __end);
            return;
        }
        *__ix = *__first;
    }
 
    this->insert (__end, __first, __last);
 
#else   // if defined (_RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE)
 
    // follow the inefficient requirement in 23.2.1.1, p7
 
    // complexity: linear in distance(first, last)
    // exception safety: basic
 
    this->clear ();
    this->insert (this->begin (), __first, __last);
 
#endif   // _RWSTD_NO_EXT_DEQUE_ASSIGN_IN_PLACE
 
}
 
 
template<class _TypeT, class _Allocator>
template <class _InputIter>
void deque<_TypeT, _Allocator>::
_C_insert_range (iterator __it,
                 _InputIter __first, _InputIter __last,
                 input_iterator_tag)
{
    typedef deque _Deque;
 
    _RWSTD_ASSERT_RANGE (__it, this->end ());
    _RWSTD_ASSERT_RANGE (__first, __last);
 
#ifndef _RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE
 
    // insert one element at a time to prevent a loss of data
    // from the input sequence in the case of an exception
 
    for ( ; !(__first == __last); ++__it, ++__first)
        __it = this->insert (__it, *__first); 
 
#else   // if defined (_RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE)
 
    // 23.2.1.3, p2: if an exception is thrown other than by the copy
    // constructor or assignment operator of T there are no effects.
 
    _Deque __tmp (this->begin (), __it, this->get_allocator ());
 
    for (; !(__first == __last); ++__first)
        __tmp.push_back (*__first);
 
    __tmp.insert (__tmp.end (), __it, this->end ());
 
    this->swap (__tmp);
    
#endif   // _RWSTD_NO_EXT_DEQUE_INSERT_IN_PLACE
 
}
 
 
// template<class _TypeT, class _Allocator>
// template <class _FwdIter>
// void deque<_TypeT, _Allocator>::
// _C_insert_range (iterator __it,
//                  _FwdIter __first, _FwdIter __last,
//                  forward_iterator_tag)
// {
//     typedef deque _Deque;
 
//     // implemented in terms of the Input Iterator overload
//     _RWSTD_INSERT_RANGE (__it, __first, __last, input_iterator_tag ());
// }
 
 
template <class _TypeT, class _Allocator>
template <class _BidirIter>
void deque<_TypeT, _Allocator>::
_C_insert_range (iterator __it,
                 _BidirIter __first, _BidirIter __last,
                 bidirectional_iterator_tag)
{
    typedef deque _Deque;
 
    _RWSTD_ASSERT_RANGE (this->begin (), __it);
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT (this->_C_is_valid ());
 
    // compute the distance of `it' from the beginning of the container,
    // the distance of `it' to the end of the container, and the number
    // of elements to be inserted
    const size_type __sz0 = this->size ();
    const size_type __inx = _DISTANCE (this->begin (), __it, size_type);
    const size_type __rem = __sz0 - __inx;
    const size_type __n = _DISTANCE (__first, __last, size_type);
 
    _RWSTD_ASSERT (__inx <= __sz0);
 
    if (__inx < __rem) {
 
        // inserting into the first half of the container
 
        if (__inx < __n) {
 
            // the number of elements in the range controlled by *this,
            // [begin, it), is less than the number of elements in the
            // range [first, last)
 
            _BidirIter __from (__last);
 
            _STD::advance (__from, -difference_type (__inx));
 
            const _BidirIter __mid (__from);
 
            while (!(__from == __first))
                this->push_front (*--__from);
 
            for (size_type __i = __inx; __i; --__i)
                this->push_front (*(this->begin () + (__n - 1)));
 
            _STD::copy (__mid, __last, this->begin () + __n);
        }
        else {
 
            // the number of elements in the range to be inserted,
            // [first, last), is less than or equal to the number
            // of elements in the range  [begin, it)
 
            for (size_type __i = __n; __i; --__i)
                this->push_front (*(this->begin () + (__n - 1)));
 
            const iterator __to = this->begin () + __n;
            
            _STD::copy (__to + __n, __to + __inx, __to);
            _STD::copy (__first, __last, this->begin () + __inx);
        }
    }
    else {
        // inserting into the second half of the container
 
        if (__rem < __n) {
 
            _BidirIter __from (__first);
 
            _STD::advance (__from, __rem);
 
            const _BidirIter __to (__from);
 
            for ( ; !(__from == __last); ++__from)
                this->push_back (*__from);
 
            for (size_type __i = 0; __i != __rem; ++__i)
                this->push_back (*(this->begin () + (__inx + __i)));
 
            _STD::copy (__first, __to, this->begin () + __inx);
        }
        else {
            for (size_type __i = 0; __i != __n; ++__i)
                this->push_back (*(this->begin () + (__sz0 - __n + __i)));
 
            const iterator __to       = this->begin () + __sz0;
            const iterator __from     = this->begin () + __inx;
            const iterator __from_end = this->begin () + (__sz0 - __n);
 
            _STD::copy_backward (__from, __from_end, __to);
            _STD::copy (__first, __last, __from);
        }
    }
}
 
 
template<class _TypeT, class _Allocator>
bool deque<_TypeT, _Allocator>::
_C_is_valid (int __emptyfl) const 
{
#ifdef _RWSTDDEBUG
 
    if (__emptyfl < 0 /* don't care */)
        return _C_is_valid (0 + empty ());
 
    // the nodes just prior the first valid node and
    // just past the last valid node must always be 0
    if (_C_node_pointer () != _C_nodes) {
        _RWSTD_ASSERT (pointer () == _C_beg._C_node [-1]);
        _RWSTD_ASSERT (pointer () == _C_end._C_node [+1]);
    }
 
    if (__emptyfl) {
        // container must be empty
        _RWSTD_ASSERT (empty ());
 
        // both `current' pointers must be 0
        _RWSTD_ASSERT (pointer () == _C_beg._C_cur);
        _RWSTD_ASSERT (pointer () == _C_end._C_cur);
 
        // node pointers must be dereferenceable...
        _RWSTD_ASSERT (_C_node_pointer () != _C_beg._C_node);
        _RWSTD_ASSERT (_C_node_pointer () != _C_end._C_node);
 
        // ...and both must dereference the same pointer
        _RWSTD_ASSERT (*_C_beg._C_node == *_C_end._C_node);
 
        return true;
    }
 
    const size_type __bufsize = _C_bufsize ();
 
    // container must be non-empty
    _RWSTD_ASSERT (!empty ());
 
    // current pointers must be non-0
    _RWSTD_ASSERT (pointer () != _C_beg._C_cur);
    _RWSTD_ASSERT (pointer () != _C_end._C_cur);
 
    // `begin' must be less than `end'
    _RWSTD_ASSERT (_C_beg._C_node <= _C_end._C_node);
 
    // `begin' must point into the vector of nodes
    _RWSTD_ASSERT (_C_nodes <= _C_beg._C_node);
    _RWSTD_ASSERT (_C_beg._C_node <= _C_nodes + _C_node_size);
 
    // `begin' must point to a non-empty array of elements
    _RWSTD_ASSERT (pointer () != *_C_beg._C_node);
 
    // `begin' must point into an array of `bufsize' elements
    _RWSTD_ASSERT (_C_beg._C_cur >= *_C_beg._C_node);
    _RWSTD_ASSERT (_C_beg._C_cur <= *_C_beg._C_node + __bufsize);
 
    // `end' must point into the vector of nodes
    _RWSTD_ASSERT (_C_nodes <= _C_end._C_node);
    _RWSTD_ASSERT (_C_end._C_node <= _C_nodes + _C_node_size);
 
    // `end' must point to a non-empty array of elements
    _RWSTD_ASSERT (pointer () != *_C_end._C_node);
 
    // `end' must point into an array of `bufsize' elements
    _RWSTD_ASSERT (_C_end._C_cur >= *_C_end._C_node);
    _RWSTD_ASSERT (_C_end._C_cur <= *_C_end._C_node + __bufsize);
 
#else   // if !defined (_RWSTDDEBUG)
 
    _RWSTD_UNUSED (__emptyfl);
 
#endif   // _RWSTDDEBUG
 
    return true;
}
 
 
}   // namespace std