ycpp_unordered_map.hpp

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

    }
    std::pair<iterator, bool> insert( const value_type& v )
    {
        size_type old_size = size();
        iterator itr = hstb_insert_unique( &m_ht, &v );
        if( end() == itr )
            throw std::bad_alloc();
        return size() == old_size ? std::pair<iterator, bool>( itr, false )
                                  : std::pair<iterator, bool>( itr, true );
    }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
    {
        youngc::hstb_iterator end = hstb_end( &m_ht );
        for( ; first != last; ++first )
        {
            if( hstb_itr_equal( hstb_insert_unique(&m_ht, &(*first)), end ) )
                throw std::bad_alloc();
        }
    }

    mapped_type& operator[]( const key_type& k )
    {
        return insert( value_type(k, mapped_type()) ).first->second;
    }

    bool replace_key( iterator pos, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        return hstb_replace_key_unique_pos( &m_ht, pos.itr, &new_key,
                                            assign_copy_adapter<key_type> );
    }
    iterator replace_key( const key_type& old_key, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        return hstb_replace_key_unique( &m_ht, &old_key, &new_key,
                                        assign_copy_adapter<key_type> );
    }

private:
    mutable youngc::hashtable m_ht;

    void init( true_type, true_type )
    {
        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   NULL, NULL, get_key, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    template< typename T1, typename T2 >
    void init( T1, T2 )
    {
        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   init_copy_adapter<value_type>, destroy_adapter<value_type>,
                   get_key, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    static const void* get_key( const void* value )
    {
        return &( ((value_type*)value)->first );
    }

    static size_t hash_adapter( const void* key )
    {
        static HashKey hash;
        return hash( *((key_type*)key) );
    }
};



template< typename K, typename V, typename HK, typename EK, typename A >
inline void swap( unordered_map<K, V, HK, EK, A>& lhs,
                  unordered_map<K, V, HK, EK, A>& rhs )
{
    lhs.swap( rhs );
}

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

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_multimap
{
public:
    typedef  unordered_multimap<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_multimap( 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_multimap( 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_multimap( 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_multimap()  {  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_equal_pos( &m_ht, pos.itr, &v );
        if( end() == itr )
            throw std::bad_alloc();
        return itr;
    }
    iterator insert( const value_type& v )
    {
        iterator itr = hstb_insert_equal( &m_ht, &v );
        if( end() == itr )
            throw std::bad_alloc();
        return itr;
    }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
    {
        youngc::hstb_iterator end = hstb_end( &m_ht );
        for( ; first != last; ++first )
        {
            if( hstb_itr_equal( hstb_insert_equal(&m_ht, &(*first)), end ) )
                throw std::bad_alloc();
        }
    }

    void replace_key( iterator pos, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        hstb_replace_key_equal_pos( &m_ht, pos.itr, &new_key,
                                    assign_copy_adapter<key_type> );
    }
    void replace_key( const key_type& old_key, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        hstb_replace_key_equal( &m_ht, &old_key, &new_key,
                                assign_copy_adapter<key_type> );
    }

private:
    mutable youngc::hashtable m_ht;

    void init( true_type, true_type )
    {
        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   NULL, NULL, get_key, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    template< typename T1, typename T2 >
    void init( T1, T2 )
    {
        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   init_copy_adapter<value_type>, destroy_adapter<value_type>,
                   get_key, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    static const void* get_key( const void* value )
    {
        return &( ((value_type*)value)->first );
    }

    static size_t hash_adapter( const void* key )
    {
        static HashKey hash;
        return hash( *((key_type*)key) );
    }
};



template< typename K, typename V, typename HK, typename EK, typename A >
inline void swap( unordered_multimap<K, V, HK, EK, A>& lhs,
                  unordered_multimap<K, V, HK, EK, A>& rhs )
{
    lhs.swap( rhs );
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
}  //end namespace
#endif
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------