ycpp_list.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software 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.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_LIST_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_LIST_HEADER_FILE__
//------------------------------------------------------------------------------
#include <memory>
#include <iterator>
#include <stdexcept>
#include "../youngc/yc_dblnklst.h"
#include "../youngc/yc_memory.h"
#include "ycpp_memory.hpp"
#include "ycpp_function.hpp"
#include "ycpp_algorithm.hpp"
//------------------------------------------------------------------------------
namespace youngcpp {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T, typename A >
class list;

template< typename T, typename Ref, typename Ptr, typename A >
class list_iterator;

template< typename T, typename A >
struct move_traits< list<T, A> >
{
    typedef  true_type  move_ability;
};



template< typename T, typename Ref, typename Ptr, typename Alloc >
class list_iterator
{
private:
    typedef  typename primal_traits<Ref>::contrary_const_ref  ccRef;
    typedef  typename primal_traits<Ptr>::contrary_const_ptr  ccPtr;

    friend class list<T, Alloc>;
    friend class list_iterator<T, ccRef, ccPtr, Alloc>;

    youngc::dblnklst_iterator itr;

public:
    typedef  std::bidirectional_iterator_tag    iterator_category;
    typedef  size_t                             size_type;
    typedef  ptrdiff_t                          difference_type;
    typedef  T                                  value_type;
    typedef  Ref                                reference;
    typedef  Ptr                                pointer;

    typedef  list_iterator<T, Ref, Ptr, Alloc>            self;
    typedef  list_iterator<T, T&, T*, Alloc>              iterator;
    typedef  list_iterator<T, const T&, const T*, Alloc>  const_iterator;

    list_iterator() : itr(0)  {}
    list_iterator( const iterator& src ) : itr(src.itr)  {}
    list_iterator( const youngc::dblnklst_iterator src ) : itr(src)  {}

    bool operator==( const self& rhs )  {  return rhs.itr == itr;  }
    bool operator!=( const self& rhs )  {  return rhs.itr != itr;  }

    pointer operator->() const   {  return (pointer)dblnklst_itr_deref(itr);  }
    reference operator*() const  {  return *((pointer)dblnklst_itr_deref(itr));  }

    self& operator++()
        {  dblnklst_itr_inc(&itr);  return *this;  }
    self& operator--()
        {  dblnklst_itr_dec(&itr);  return *this;  }
    self operator++(int)
        {  self old = *this;  dblnklst_itr_inc(&itr);  return old;  }
    self operator--(int)
        {  self old = *this;  dblnklst_itr_dec(&itr);  return old;  }

    self& operator+=( difference_type n )
    {
        n > 0 ? dblnklst_itr_inc_n( &itr, n ) : dblnklst_itr_dec_n( &itr, -n );
        return *this;
    }

    self& operator-=( difference_type n )
    {
        n > 0 ? dblnklst_itr_dec_n( &itr, n ) : dblnklst_itr_inc_n( &itr, -n );
        return *this;
    }
};

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr, Alloc>
operator+( const list_iterator<T, Ref, Ptr, Alloc>& lhs, ptrdiff_t n )
{
    list_iterator<T, Ref, Ptr,Alloc> temp( lhs );
    return ( temp += n );
}

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr,Alloc>
operator+( ptrdiff_t n, const list_iterator<T, Ref, Ptr, Alloc>& rhs )
{
    list_iterator<T, Ref, Ptr, Alloc> temp( rhs );
    return ( temp += n );
}

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr, Alloc>
operator-( const list_iterator<T, Ref, Ptr, Alloc>& lhs, ptrdiff_t n )
{
    list_iterator<T, Ref, Ptr, Alloc> temp( lhs );
    return ( temp -= n );
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T, typename Allocator = std::allocator<T> >
class list
{
public:
    typedef  list<T, Allocator>     self;
    typedef  Allocator              allocator_type;
    typedef  size_t                 size_type;
    typedef  ptrdiff_t              difference_type;
    typedef  T                      value_type;
    typedef  value_type&            reference;
    typedef  const value_type&      const_reference;
    typedef  value_type*            pointer;
    typedef  const value_type*      const_pointer;

    typedef  list_iterator<T, T&, T*, Allocator>              iterator;
    typedef  list_iterator<T, const T&, const T*, Allocator>  const_iterator;

    typedef  std::reverse_iterator<iterator>        reverse_iterator;
    typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;

    list()  {  init();  }

    explicit list( size_type n, const T& value = T() )
        {  init_fill( n, value );  }
    explicit list( int n, const T& value = T() )
        {  init_fill( static_cast<size_type>(n), value );  }
    explicit list( long n, const T& value = T() )
        {  init_fill( static_cast<size_type>(n), value );  }

    template< typename InputIterator >
    list( InputIterator first, InputIterator last )
    {
        init();
        youngc::dblnklst_iterator end = dblnklst_end( &m_dli );
        for( ; first != last; ++first )
        {
            if( !dblnklst_insert_node( &m_dli, end, &(*first) ) )
            {
                dblnklst_destroy( &m_dli );
                throw std::bad_alloc();
            }
        }
    }

    list( const self& rhs )
    {
        if( dblnklst_init_copy( &m_dli, &(rhs.m_dli) ) == 0 )
            throw std::bad_alloc();
    }

    self& operator=( const self& rhs )
    {
        if( dblnklst_assign_copy( &m_dli, &(rhs.m_dli) ) == 0 )
            throw std::bad_alloc();
        return *this;
    }

    ~list()  {  dblnklst_destroy( &m_dli );  }

    static void init_move( void* uninit_dst, void* src )
    {
        dblnklst_init_move( &( static_cast<self*>(uninit_dst)->m_dli ),
                            &( static_cast<self*>(src)->m_dli ) );
    }

    static void assign_move( void* dst, void* src )
    {
        dblnklst_assign_move( &( static_cast<self*>(dst)->m_dli ),
                              &( static_cast<self*>(src)->m_dli ) );
    }

    iterator begin()
        {  return iterator( dblnklst_begin(&m_dli) );  }
    iterator end()
        {  return iterator( dblnklst_end(&m_dli) );  }
    const_iterator begin() const
        {  return const_iterator( dblnklst_begin(&m_dli) );  }
    const_iterator end() const
        {  return const_iterator( dblnklst_end(&m_dli) );  }

    reverse_iterator rbegin()
        {  return reverse_iterator( end() );  }
    reverse_iterator rend()
        {  return reverse_iterator( begin() );  }
    const_reverse_iterator rbegin() const
        {  return const_reverse_iterator( end() );  }
    const_reverse_iterator rend() const
        {  return const_reverse_iterator( begin() );  }

    reference front()
        {  return *((pointer)dblnklst_front(&m_dli));  }
    reference back()
        {  return *((pointer)dblnklst_back(&m_dli));  }
    const_reference front() const
        {  return *((const_pointer)dblnklst_front(&m_dli));  }
    const_reference back() const
        {  return *((const_pointer)dblnklst_back(&m_dli));  }

    void reverse()              {  dblnklst_reverse(&m_dli);  }
    bool empty() const          {  return dblnklst_empty(&m_dli);  }
    size_type size() const      {  return dblnklst_size(&m_dli);  }
    size_type max_size() const  {  return youngc::dblnklst_max_size();  }