list

realview22.rar

        return const_reverse_iterator (begin ());
    }

    bool empty () const {
        return 0 == size ();
    }

    size_type size () const {
        return _C_length;
    }

    size_type max_size () const {
        return _C_node_alloc_type (*this).max_size ();
    }

    void resize (size_type, value_type);

    void resize (size_type __n) {
        resize (__n, value_type ());
    }

    reference front () {
        _RWSTD_ASSERT (!empty ());
        return *begin ();
    }

    const_reference front () const {
        _RWSTD_ASSERT (!empty ());
        return *begin ();
    }

    reference back () {
        _RWSTD_ASSERT (!empty ());
        return *--end ();
    }

    const_reference back () const {
        _RWSTD_ASSERT (!empty ());
        return *--end ();
    }

    void push_front (const_reference __x) {
        insert (begin (), __x);
        _RWSTD_ASSERT (!empty ());
    }

    void push_back  (const_reference __x) {
        insert (end (), __x);
        _RWSTD_ASSERT (!empty ());
    }
    
    void pop_front () {
        _RWSTD_ASSERT (!empty ());
        erase (begin ());
    }

    void pop_back () {
        _RWSTD_ASSERT (!empty ());
        erase (--end ());
    }

    iterator insert (iterator __it, const_reference __x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    // handles bidirectional iterators
    template <class _InputIterator>
    void _C_insert (const iterator &__it,
                    _InputIterator __first, _InputIterator __last, 
                    bidirectional_iterator_tag) {
        _RWSTD_ASSERT_RANGE (begin (), __it);
        _RWSTD_ASSERT_RANGE (__first, __last);

        for ( ;__first != __last; ++__first)
            insert (__it, *__first); 
    }

    // handles input iterators
    template <class _InputIterator>
    void _C_insert (iterator __it,
                    _InputIterator __first, _InputIterator __last, 
                    input_iterator_tag) {
        _RWSTD_ASSERT_RANGE (begin (), __it);
        _RWSTD_ASSERT_RANGE (__first, __last);

        for ( ;__first != __last; ++__first, ++__it)
            __it = insert (__it, *__first); 
    }
 
    // handles nonintegral types
    template<class _InputIterator>
    void _C_insert (const iterator &__it,
                    _InputIterator  __first, _InputIterator __last, 
                    _RWSTD_DISPATCH_INT (false)) {
        typedef _TYPENAME iterator_traits <_InputIterator>::iterator_category
            _IterCat;

        _C_insert (__it, __first, __last, _IterCat ());
    }

    // handles integral types
    template<class _InputIterator>
    void _C_insert (const iterator &__it, 
                    _InputIterator  __first, _InputIterator __last, 
                    _RWSTD_DISPATCH_INT (true)) {
        _C_insert (__it, __first, __last);
    }

    template<class _InputIterator>
    void insert (iterator __it, 
                 _InputIterator __first, _InputIterator __last ) {

        _RWSTD_ASSERT_RANGE (begin (), __it);
        _RWSTD_ASSERT_RANGE (__first, __last);

        // calling insert on a list specialized on an integral type
        // may lead to ambiguities if the actual function arguments do not
        // exactly match those of the non-templatized function (below)
        // the dispatch mechanism determines whether the arguments
        // really are iterators or whether they are just integral types
        // and calls the appropriate implementation function
        _C_insert  (__it, __first, __last, _RWSTD_DISPATCH (_InputIterator));
    }

    void insert (iterator __it, size_type __n, const_reference __val) {
        _RWSTD_ASSERT_RANGE (begin (), __it);

        _C_insert (__it, __n, __val);
    }

#else   // if defined (_RWSTD_NO_MEMBER_TEMPLATES)

    void insert (iterator __it, size_type __n, const_reference __x) {
        _RWSTD_ASSERT_RANGE (begin (), __it);

        _C_insert (__it, __n, __x);
    }

    void insert (iterator __it, const_pointer __first, const_pointer __last) {
        _RWSTD_ASSERT_RANGE (begin (), __it);
        _RWSTD_ASSERT_RANGE (__first, __last);

        for (; __first != __last; ++__first)
            insert (__it, *__first);
    }

    void insert (iterator __it,
                 const_iterator __first, const_iterator __last) {
        _RWSTD_ASSERT_RANGE (begin (), __it);
        _RWSTD_ASSERT_RANGE (__first, __last);

        for (; __first != __last; ++__first)
            insert (__it, *__first);
    }

#endif   // _RWSTD_NO_MEMBER_TEMPLATES

    iterator erase (iterator);

    iterator erase (iterator, iterator);

    void swap (list&);

    void clear () {
        erase (begin (), end ());
    }

protected:
    
    void _C_transfer (iterator, iterator, iterator, list&);

    void _C_advance (iterator &__it, difference_type __n,
                     const iterator &__end) {
        while (__n-- && __it != __end)
            ++__it;
    }
      
    // uses transfer_node to merge in list by transfering nodes to list
    void _C_adjacent_merge (iterator, iterator, iterator);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    // uses transfer_node to merge in list by transfering nodes to list
    template<class _Compare>
    void _C_adjacent_merge (iterator, iterator, iterator, _Compare);

#else   // if defined (_RWSTD_NO_MEMBER_TEMPLATES)

    void _C_adjacent_merge (iterator, iterator, iterator,
                           bool (*)(const_reference, const_reference));

#endif   // _RWSTD_NO_MEMBER_TEMPLATES
      
    void _C_insert (iterator __it, size_type __n, const_reference __x) {
        _RWSTD_ASSERT_RANGE (begin (), __it);

        while (__n--)
            insert (__it, __x);
    }

public:

    void splice (iterator __it, list& __x) {
        _RWSTD_ASSERT (&__x != this);
        _RWSTD_ASSERT_RANGE (begin (), __it);
        
        if (!__x.empty ())
            _C_transfer (__it, __x.begin (), __x.end (), __x);
    }

    void splice (iterator __pos, list& __x, iterator __it) { 
        _RWSTD_ASSERT_RANGE (__it, __x.end ());
        _RWSTD_ASSERT_DEREF (__it);

        iterator __tmp = __it;
        if (__tmp != __pos && ++__tmp != __pos)
            _C_transfer (__pos, __it, __tmp, __x);
    }

    void splice (iterator __it, list& __x, iterator __first, iterator __last) {
        _RWSTD_ASSERT_IN_RANGE (__x.begin (), __first, __last);
         
        if (__first != __last)
            _C_transfer (__it, __first, __last, __x);
    }

    void remove (const_reference);

    void unique ();

    void merge (list&);

    void reverse ();

    void sort ();

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    template<class _Predicate>
    void remove_if (_Predicate);

    template<class _BinaryPredicate>
    void unique (_BinaryPredicate);

    template<class _Compare>
    void merge (list &__x, _Compare);

    template<class _Compare>
    void sort (_Compare);

#else   // if defined (_RWSTD_NO_MEMBER_TEMPLATES)

    void remove_if (bool (*)(const_reference));

    void unique (bool (*)(const_reference, const_reference));

    void merge (list &__x, bool (*)(const_reference, const_reference));

    void sort (bool (*)(const_reference, const_reference));

#endif // _RWSTD_NO_MEMBER_TEMPLATES

};


template <class _TypeT, class _Allocator>
inline bool
operator== (const list<_TypeT, _Allocator>& __x, 
            const list<_TypeT, _Allocator>& __y)
{
    return    __x.size () == __y.size ()
           && equal (__x.begin (), __x.end (), __y.begin ());
}


template <class _TypeT, class _Allocator>
inline bool
operator< (const list<_TypeT, _Allocator>& __x, 
           const list<_TypeT, _Allocator>& __y)
{
    return lexicographical_compare (__x.begin (), __x.end (), 
                                    __y.begin (), __y.end ());
}


template <class _TypeT, class _Allocator>
inline bool
operator!= (const list<_TypeT, _Allocator>& __x, 
            const list<_TypeT, _Allocator>& __y)
{
    return !(__x == __y);
}


template <class _TypeT, class _Allocator>
inline bool
operator<= (const list<_TypeT, _Allocator>& __x, 
            const list<_TypeT, _Allocator>& __y)
{
    return !(__y < __x);
}


template <class _TypeT, class _Allocator>
inline bool
operator> (const list<_TypeT, _Allocator>& __x, 
            const list<_TypeT, _Allocator>& __y)
{
    return __y < __x;
}


template <class _TypeT, class _Allocator>
inline bool
operator>= (const list<_TypeT, _Allocator>& __x, 
            const list<_TypeT, _Allocator>& __y)
{
    return !(__x < __y);
}


#ifndef _RWSTD_NO_PART_SPEC_OVERLOAD
template <class _TypeT, class _Allocator>
inline void swap (list<_TypeT, _Allocator>& __x, 
                  list<_TypeT, _Allocator>& __y)
{
    __x.swap (__y);
}
#endif


template <class _TypeT, class _Allocator>
inline _TYPENAME list<_TypeT, _Allocator>::iterator 
list<_TypeT, _Allocator>::erase (iterator __first, iterator __last)
{
    _RWSTD_ASSERT_RANGE (begin (), __first);
    _RWSTD_ASSERT_RANGE (__first, __last);
      
    while (__first != __last) {
        __first = erase (__first);
    }
      
    return __first;
}


template <class _TypeT, class _Allocator>
inline _TYPENAME list<_TypeT, _Allocator>::iterator 
list<_TypeT, _Allocator>::insert (iterator __it, const_reference __x)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);

    // create temporary allocator for non-conforming compilers
    //  which need to use allocator_interface
    _C_link_type __tmp = _C_get_node ();

    _TRY {
        _RWSTD_VALUE_ALLOC (_C_value_alloc_type,
                            construct (_RWSTD_VALUE_ALLOC
                                       (_C_value_alloc_type,
                                        address ((*__tmp)._C_data)), __x));
    }
    _CATCH (...) {
        _C_put_node (__tmp);
        _RETHROW;
    }

    (*__tmp)._C_next = _ITER_NODE (__it);
    (*__tmp)._C_prev = (*_ITER_NODE (__it))._C_prev;

    (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next = __tmp;

    (*_ITER_NODE (__it))._C_prev = __tmp;

    ++_C_length;

    return _C_make_iter (__tmp);
}


template <class _TypeT, class _Allocator>
inline _TYPENAME list<_TypeT, _Allocator>::iterator 
list<_TypeT, _Allocator>::erase (iterator __it)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);

    if (__it == end ())
        return end ();

    iterator __tmp =
        _C_make_iter (_C_link_type ((*_ITER_NODE (__it))._C_next));

    (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next =
        (*_ITER_NODE (__it))._C_next;
    (*(_C_link_type ((*_ITER_NODE (__it))._C_next)))._C_prev =
        (*_ITER_NODE (__it))._C_prev;

    --_C_length;

    _RWSTD_VALUE_ALLOC (_C_value_alloc_type,
                        destroy (_RWSTD_VALUE_ALLOC (_C_value_alloc_type,
                            address ((*_ITER_NODE (__it))._C_data))));
    _C_put_node (_ITER_NODE (__it));

    return __tmp;
}


template <class _TypeT, class _Allocator>
inline void
list<_TypeT, _Allocator>::swap (list &__x)
{
    if (get_allocator () == __x.get_allocator ()) {
        _STD::swap (_C_node, __x._C_node); 
        _STD::swap (_C_length, __x._C_length);
        _STD::swap (_C_buflist, __x._C_buflist);
        _STD::swap (_C_free_list, __x._C_free_list);
        _STD::swap (_C_next_avail, __x._C_next_avail);
        _STD::swap (_C_last, __x._C_last);
    }
    else {
        list &__tmp = *this;
        *this = __x;
        __x = __tmp;
    }
}


template <class _TypeT, class _Allocator>
inline void list<_TypeT, _Allocator>::
_C_adjacent_merge (iterator __first1, iterator __last1, iterator __last2)
{
    difference_type __n = _DISTANCE (__first1, __last1, difference_type);

    for (iterator __first2 = __last1; __n >= 0 && __first2 != __last2; ) {
        if (*__first2 < *__first1) {
            iterator __next = __first2;
            _C_transfer (__first1, __first2, ++__next, *this);
            __first2 = __next;
        }
        else {
            ++__first1;
            --__n;
        }
    }
}


#ifndef _RWSTD_NO_MEMBER_TEMPLATES

template <class _TypeT, class _Allocator>
template<class _Compare>
inline void list<_TypeT, _Allocator>::
_C_adjacent_merge (iterator __first1, iterator __last1, iterator __last2,
                   _Compare __cmp)

#else   // if defined (_RWSTD_NO_MEMBER_TEMPLATES)

template <class _TypeT, class _Allocator>
inline void list<_TypeT, _Allocator>::
_C_adjacent_merge (iterator __first1, iterator __last1, iterator __last2,
                   bool (*__cmp)(const_reference, const_reference))

#endif   // _RWSTD_NO_MEMBER_TEMPLATES
{
    difference_type __n = _DISTANCE (__first1, __last1, difference_type);

    for (iterator __first2 = __last1; __n >= 0 && __first2 != __last2; ) {
        if (__cmp (*__first2, *__first1)) {
            iterator __next = __first2;
            _C_transfer (__first1, __first2, ++__next, *this);
            __first2 = __next;
        }
        else {
            ++__first1;
            --__n;
        }
    }
}


_RWSTD_NAMESPACE_END   // std

#undef _ITER_NODE

#ifdef _RWSTD_COMPILE_INSTANTIATE
#  include <list.cc>
#endif


#ifndef _RWSTD_NO_STL_SPECIALIZATION
#  include "list_spec.h"
#endif   // _RWSTD_NO_STL_SPECIALIZATION


#endif   //_RWSTD_LIST_INCLUDED