ycpp_deque.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_DEQUE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_DEQUE_HEADER_FILE__
//------------------------------------------------------------------------------
#include <memory>
#include <iterator>
#include <stdexcept>
#include <algorithm>
#include "../youngc/yc_chkarray.h"
#include "ycpp_memory.hpp"
//------------------------------------------------------------------------------
namespace youngcpp {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T, typename A >
class deque;

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

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



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

    friend class deque<T, Alloc>;
    friend class deque_iterator<T, ccRef, ccPtr, Alloc>;

    mutable youngc::chkarr_iterator itr;

public:
    typedef  std::random_access_iterator_tag    iterator_category;
    typedef  ptrdiff_t                          difference_type;
    typedef  T                                  value_type;
    typedef  Ref                                reference;
    typedef  Ptr                                pointer;

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

    deque_iterator()
        {  std::memset( &itr, 0, sizeof(youngc::chkarr_iterator) );  }
    deque_iterator( const iterator& src ) : itr(src.itr)  {}
    deque_iterator( const youngc::chkarr_iterator& src ) : itr(src)  {}

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

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

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

    self& operator+=( difference_type n )
        {  chkarr_itr_inc_n(&itr, n);  return *this;  }
    self& operator-=( difference_type n )
        {  chkarr_itr_dec_n(&itr, n);  return *this;  }

    difference_type operator-( const self& rhs ) const
        {  return chkarr_itr_diff( &itr, &(rhs.itr) );  }
};

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

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

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

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline bool operator>( const deque_iterator<T, Ref, Ptr, Alloc>& lhs,
                       const deque_iterator<T, Ref, Ptr, Alloc>& rhs )
{
    return rhs < lhs;
}

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline bool operator<=( const deque_iterator<T, Ref, Ptr, Alloc>& lhs,
                        const deque_iterator<T, Ref, Ptr, Alloc>& rhs )
{
    return !( rhs < lhs );
}

template< typename T, typename Ref, typename Ptr, typename Alloc >
inline bool operator>=( const deque_iterator<T, Ref, Ptr, Alloc>& lhs,
                        const deque_iterator<T, Ref, Ptr, Alloc>& rhs )
{
    return !( lhs < rhs );
}

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

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

    typedef  deque_iterator<T, T&, T*, Allocator>               iterator;
    typedef  deque_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;

    deque()
    {
        typedef  typename property_traits<T>::is_POD  POD;
        init( POD() );
    }

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

    template< typename InputIterator >
    deque( InputIterator first, InputIterator last )
    {
        typedef  typename property_traits<T>::is_POD  POD;
        init( POD() );
        try
        {
            insert( end(), first, last );
        }
        catch( ... )
        {
            chkarr_destroy( &m_chks );
            throw std::bad_alloc();
        }
    }

    deque( const self& src )
    {
        if( chkarr_init_copy( &m_chks, &(src.m_chks) ) == 0 )
        {
            chkarr_destroy( &m_chks );
            throw std::bad_alloc();
        }
    }

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

    ~deque()  {  chkarr_destroy( &m_chks );  }

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

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

    iterator begin()
        {  return iterator( chkarr_begin(&m_chks) );  }
    iterator end()
        {  return iterator( chkarr_end(&m_chks) );  }
    const_iterator begin() const
        {  return const_iterator( chkarr_begin(&m_chks) );  }
    const_iterator end() const
        {  return const_iterator( chkarr_end(&m_chks) );  }

    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)chkarr_front(&m_chks));  }
    reference back()
        {  return *((pointer)chkarr_back(&m_chks));  }
    const_reference front() const
        {  return *((const_pointer)chkarr_front(&m_chks));  }
    const_reference back() const
        {  return *((const_pointer)chkarr_back(&m_chks));  }

    bool empty() const          {  return chkarr_empty(&m_chks);  }
    size_type size() const      {  return chkarr_size(&m_chks);  }
    size_type max_size() const  {  return youngc::chkarr_max_size();  }

    reference operator[]( size_type index )
        {  return *((pointer)chkarr_index(&m_chks, index));  }
    const_reference operator[]( size_type index ) const
        {  return *((const_pointer)chkarr_index(&m_chks, index));  }

    reference at( size_type index )
    {
        pointer p = (pointer)chkarr_at(&m_chks, index);
        if( !p )
            throw std::out_of_range( "young::deque::at out of range!" );
        return *p;
    }