ycpp_unordered_map.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_UNORDERED_MAP_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_UNORDERED_MAP_HEADER_FILE__
//------------------------------------------------------------------------------
#include <memory>
#include <utility>
#include <iterator>
#include <functional>
#include "../youngc/yc_hashtable.h"
#include "../youngc/yc_memory.h"
#include "ycpp_memory.hpp"
#include "ycpp_function.hpp"
#include "ycpp_functional.hpp"
//------------------------------------------------------------------------------
namespace youngcpp {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename K, typename V, typename HK, typename EK, typename A >
class unordered_map;

template< typename K, typename V, typename HK, typename EK, typename A >
class unordered_multimap;

template< typename T, typename R, typename P, typename K, typename M,
          typename HK, typename EK, typename A >
class uomap_iterator;

template< typename T, typename R, typename P, typename K, typename M,
          typename HK, typename EK, typename A >
class uomap_local_iterator;



template< typename K, typename V, typename HK, typename EK, typename A >
struct move_traits< unordered_map<K, V, HK, EK, A> >
{
    typedef  true_type  move_ability;
};

template< typename K, typename V, typename HK, typename EK, typename A >
struct move_traits< unordered_multimap<K, V, HK, EK, A> >
{
    typedef  true_type  move_ability;
};

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

template< typename T, typename Ref, typename Ptr, typename Key, typename Mapped,
          typename HashKey, typename EqualKey, typename Allocator >
class uomap_iterator
{
private:
    typedef  typename primal_traits<Ref>::contrary_const_ref  ccRef;
    typedef  typename primal_traits<Ptr>::contrary_const_ptr  ccPtr;

    friend class unordered_map<Key, Mapped, HashKey, EqualKey, Allocator>;
    friend class unordered_multimap<Key, Mapped, HashKey, EqualKey, Allocator>;
    friend class uomap_local_iterator<T, Ref, Ptr, Key, Mapped, HashKey,
                                      EqualKey, Allocator>;
    friend class uomap_iterator<T, ccRef, ccPtr, Key, Mapped, HashKey, EqualKey,
                                Allocator>;

    youngc::hstb_iterator itr;

public:
    typedef  std::forward_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  uomap_iterator<T, Ref, Ptr, Key, Mapped, HashKey, EqualKey,
                            Allocator>  self;
    typedef  uomap_iterator<T, T&, T*, Key, Mapped, HashKey, EqualKey,
                            Allocator>  iterator;

    uomap_iterator()  {  itr.node = 0;  itr.table = 0;  }
    uomap_iterator( const iterator& src ) : itr(src.itr)  {}
    uomap_iterator( const youngc::hstb_iterator& src ) : itr(src)  {}

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

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

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



template< typename T, typename Ref, typename Ptr, typename Key, typename Mapped,
          typename HashKey, typename EqualKey, typename Allocator >
class uomap_local_iterator
{
private:
    typedef  typename primal_traits<Ref>::contrary_const_ref  ccRef;
    typedef  typename primal_traits<Ptr>::contrary_const_ptr  ccPtr;

    friend class unordered_map<Key, Mapped, HashKey, EqualKey, Allocator>;
    friend class unordered_multimap<Key, Mapped, HashKey, EqualKey, Allocator>;
    friend class uomap_local_iterator<T, ccRef, ccPtr, Key, Mapped, HashKey,
                                      EqualKey, Allocator>;

    youngc::hstb_local_iterator lcitr;

public:
    typedef  std::forward_iterator_tag      iterator_category;
    typedef  size_t                         size_type;
    typedef  ptrdiff_t                      difference_type;
    typedef  Key                            value_type;
    typedef  const Key&                     reference;
    typedef  const Key*                     pointer;

    typedef  uomap_iterator<T, Ref, Ptr, Key, Mapped, HashKey, EqualKey,
                            Allocator>          iterator;
    typedef  uomap_local_iterator<T, T&, T*, Key, Mapped, HashKey, EqualKey,
                                  Allocator>    local_iterator;
    typedef  uomap_local_iterator<T, Ref, Ptr, Key, Mapped, HashKey, EqualKey,
                                  Allocator>    self;

    uomap_local_iterator() : lcitr(0)  {}
    uomap_local_iterator( const iterator& src ) : lcitr(src.itr.node)  {}
    uomap_local_iterator( const local_iterator& src ) : lcitr(src.lcitr)  {}
    uomap_local_iterator( const youngc::hstb_iterator src ) : lcitr(src.node)  {}
    uomap_local_iterator( const youngc::hstb_local_iterator src ) : lcitr(src)  {}

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

    reference operator*() const
        {  return *( (pointer)hstb_lc_itr_deref(lcitr) );  }
    pointer operator->() const
        {  return (pointer)hstb_lc_itr_deref(lcitr);  }

    self& operator++()
        {  hstb_lc_itr_inc(&lcitr);  return *this;  }
    self operator++(int)
        {  self old = *this;  hstb_lc_itr_inc(&lcitr);  return old;  }
};

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

template< typename Key, typename Value,
#ifdef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_COMPILER_SUPPORT_STANDARD_HASH_FUNCTION_OBJECT__
          typename HashKey = std::tr1::hash<T>,
#else
          typename HashKey = hash<Key>,
#endif
          typename EqualKey = std::equal_to<Key>,
          typename Allocator = std::allocator< std::pair<const Key, Value> > >
class unordered_map
{
public:
    typedef  unordered_map<Key, Value, HashKey, EqualKey, Allocator>  self;

    typedef  Key                            key_type;
    typedef  Value                          mapped_type;
    typedef  std::pair<const Key, Value>    value_type;
    typedef  HashKey                        hasher;
    typedef  EqualKey                       key_equal;
    typedef  Allocator                      allocator_type;

    typedef  size_t                         size_type;
    typedef  ptrdiff_t                      difference_type;
    typedef  value_type&                    reference;
    typedef  const value_type&              const_reference;
    typedef  value_type*                    pointer;
    typedef  const value_type*              cons_pointer;

    typedef  uomap_iterator<value_type, reference, pointer, Key, mapped_type,
                            HashKey, EqualKey, Allocator>
             iterator;
    typedef  uomap_iterator<value_type, const_reference, cons_pointer, Key,
                            mapped_type, HashKey, EqualKey, Allocator>
             const_iterator;

    typedef  uomap_local_iterator<value_type, reference, pointer, Key,
                                  mapped_type, HashKey, EqualKey, Allocator>
             local_iterator;
    typedef  uomap_local_iterator<value_type, const_reference, cons_pointer,
                                  Key, mapped_type, HashKey, EqualKey, Allocator>
             const_local_iterator;

    explicit unordered_map( size_type n = 100 )
    {
        typedef  typename property_traits<key_type>::is_POD     kPOD;
        typedef  typename property_traits<mapped_type>::is_POD  vPOD;
        init( kPOD(), vPOD() );
        if( !hstb_rehash( &m_ht, n ) )
            throw std::bad_alloc();
    }

    template< typename InputIterator >
    unordered_map( InputIterator first, InputIterator last, size_type n = 100 )
    {
        typedef  typename property_traits<key_type>::is_POD     kPOD;
        typedef  typename property_traits<mapped_type>::is_POD  vPOD;
        init( kPOD(), vPOD() );
        if( !hstb_rehash( &m_ht, n ) )
            throw std::bad_alloc();
        try {  insert( first, last );  }
        catch(...) {  hstb_destroy( &m_ht );  throw;  }
    }

    unordered_map( const self& rhs )
    {
        if( hstb_init_copy( &m_ht, &(rhs.m_ht) ) == 0 )
            throw std::bad_alloc();
    }

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

    ~unordered_map()  {  hstb_destroy( &m_ht );  }

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

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

    iterator begin()
        {  return iterator( hstb_begin(&m_ht) );  }
    iterator end()
        {  return iterator( hstb_end(&m_ht) );  }
    const_iterator begin() const
        {  return const_iterator( hstb_begin(&m_ht) );  }
    const_iterator end() const
        {  return const_iterator( hstb_end(&m_ht) );  }

    local_iterator begin( size_type index )
        {  return local_iterator( hstb_local_begin(&m_ht, index) );  }
    local_iterator end( size_type index )
        {  return local_iterator( youngc::hstb_local_end() );  }
    const_local_iterator begin( size_type index ) const
        {  return const_local_iterator( hstb_local_begin(&m_ht, index) );  }
    const_local_iterator end( size_type index ) const
        {  return const_local_iterator( youngc::hstb_local_end() );  }

    size_type size() const      {  return hstb_size( &m_ht );  }
    size_type max_size() const  {  return youngc::hstb_max_size();  }
    bool empty() const          {  return size() == 0;  }

    void swap( self& rhs )
    {
        youngc::hashtable tmp = m_ht;
        m_ht = rhs.m_ht;
        rhs.m_ht = tmp;
    }

    size_type bucket_count() const
        {  return hstb_chain_count( &m_ht );  }
    size_type max_bucket_count() const
        {  return youngc::hstb_max_chain_count();  }
    size_type bucket_size( size_type index ) const
        {  return hstb_chain_size( &m_ht, index );  }
    size_type bucket( const key_type& k ) const
        {  return hstb_key_chain( &m_ht, &k );  }

    float load_factor() const       {  return hstb_load_factor( &m_ht );  }
    float max_load_factor() const   {  return hstb_get_max_load_factor( &m_ht );  }
    void max_load_factor( float f ) {  hstb_set_max_load_factor( &m_ht, f );  }

    void clear()
        {  hstb_erase_range( &m_ht, hstb_begin(&m_ht), hstb_end(&m_ht) );  }

    void rehash( size_type n )
    {
        if( !hstb_rehash( &m_ht, n ) )
            throw std::bad_alloc();
    }

    size_type count( const key_type& k ) const
        {  return hstb_count( &m_ht, &k );  }

    iterator find( const key_type& k )
        {  return hstb_find( &m_ht, &k );  }
    const_iterator find( const key_type& k ) const
        {  return hstb_find( &m_ht, &k );  }

    std::pair<iterator, iterator> equal_range( const key_type& k )
    {
        youngc::hstb_pair_iterator pr = hstb_equal_range( &m_ht, &k );
        return std::pair<iterator, iterator>( pr.first, pr.second );
    }
    std::pair<const_iterator, const_iterator> equal_range( const key_type& k ) const
    {
        youngc::hstb_pair_iterator pr = hstb_equal_range( &m_ht, &k );
        return std::pair<const_iterator, const_iterator>( pr.first, pr.second );
    }

    size_type erase( const key_type& k )
        {  return hstb_erase_key( &m_ht, &k );  }
    void erase( iterator pos )
        {  hstb_erase_pos( &m_ht, pos.itr );  }
    void erase( iterator first, iterator last )
        {  hstb_erase_range( &m_ht, first.itr, last.itr );  }

    iterator insert( iterator pos, const value_type& v )
    {
        iterator itr = hstb_insert_unique_pos( &m_ht, pos.itr, &v );
        if( end() == itr )
            throw std::bad_alloc();
        return itr;