mstl_hash_map.hpp

来自「一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面」· HPP 代码 · 共 432 行 · 第 1/2 页

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

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.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation 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.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_HASH_MAP_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_HASH_MAP_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_pair.hpp"
#include "mstl_functional.hpp"
#include "hash/mstl_hash_function.hpp"
#include "hash/mstl_hash_table.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun = hash<Key>,
          typename EqualKey = equal_to<Key>,
          typename Allocator = allocator<Value> >
class hash_map
{
private:
    typedef  pair<const Key, Value>    value_t;
    typedef  hash_table_node<value_t>  node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  hash_table<Key, value_t, HashFun, select1st<value_t>,
             EqualKey, node_alloc>  hash_table;
//    typedef  hash_table<Key, value_t, HashFun, select1st<value_t>,
//             EqualKey>  hash_table;

    hash_table ht;

public:
    typedef  hash_map<Key, Value, HashFun, EqualKey, Allocator>  self;

    typedef  Value                            mapped_type;
    typedef  typename hash_table::key_type    key_type;
    typedef  typename hash_table::value_type  value_type;
    typedef  typename hash_table::hasher      hasher;
    typedef  typename hash_table::key_equal   key_equal;

    typedef  typename hash_table::size_type        size_type;
    typedef  typename hash_table::difference_type  difference_type;
    typedef  typename hash_table::reference        reference;
    typedef  typename hash_table::const_reference  const_reference;
    typedef  typename hash_table::pointer          pointer;
    typedef  typename hash_table::const_pointer    const_pointer;
    typedef  typename hash_table::iterator         iterator;
    typedef  typename hash_table::const_iterator   const_iterator;

    struct value_compare : public binary_function<value_type, value_type, bool>
    {
    	bool operator()( const value_type& lhs, const value_type& rhs ) const
    	{
    	    return ( lhs.first < rhs.first );
        }
    };



    hash_map() : ht(0)  {}

    explicit hash_map( size_type n, const hasher& hf = hasher(),
                       const key_equal& eq = key_equal() ) : ht(n, hf, eq)  {}

    template< typename InputIterator >
    hash_map( InputIterator first, InputIterator last,
              size_type n = 0, const hasher& hf = hasher(),
              const key_equal& eq = key_equal() ) : ht(n, hf, eq)
    {
        ht.insert_unique( first, last );
    }

    hasher hash_fun() const   {  return ht.hash_fun();  }
    key_equal key_eq() const  {  return ht.key_eq();  }

    double get_hash_factor() const         {  return ht.get_hash_factor();  }
    void set_hash_factor( double factor )  {  ht.set_hash_factor(factor);  }

    size_type size() const      {  return ht.size();  }
    size_type max_size() const  {  return ht.max_size();  }
    bool empty() const          {  return ht.empty();  }
    void swap( self& rhs )      {  ht.swap( rhs.ht );  }
    void clear()                {  ht.clear();  }

    void resize( size_type n )          {  ht.resize( n );  }
    size_type bucket_count() const      {  return ht.bucket_count();  }
    size_type max_bucket_count() const  {  return ht.max_bucket_count();  }

    size_type elems_in_bucket( size_type n ) const
        {  return ht.elements_in_bucket( n );  }

    size_type count( const key_type& k ) const
        {  return ht.count( k );  }

    iterator begin()              {  return ht.begin();  }
    iterator end()                {  return ht.end();  }
    const_iterator begin() const  {  return ht.begin();  }
    const_iterator end() const    {  return ht.end();  }

    iterator find( const key_type& k )
        {  return ht.find( k );  }
    const_iterator find( const key_type& k ) const
        {  return ht.find( k );  }

    pair<iterator, iterator> equal_range( const key_type& k )
        {  return ht.equal_range( k );  }
    pair<const_iterator, const_iterator> equal_range( const key_type& k ) const
        {  return ht.equal_range( k );  }

    size_type erase( const key_type& k )         {  return ht.erase( k );  }
    void erase( iterator pos )                   {  ht.erase( pos );  }
    void erase( iterator first, iterator last )  {  ht.erase( first, last );  }

    iterator modify_key( const key_type& k, const key_type& new_key )
        {  return ht.modify_key_unique( k, new_key );  }
    bool modify_key( iterator position, const key_type& new_key )
        {  return ht.modify_key_unique( position, new_key );  }

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

    pair<iterator, bool> insert( const key_type& k, const mapped_type& d )
        {  return ht.insert_unique( value_type(k, d) );  }
    pair<iterator, bool> insert( const value_type& v )
        {  return ht.insert_unique( v );  }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  ht.insert_unique( first, last );  }

};



template< typename Key, typename Value, typename HashFun, typename EqualKey,
          typename Allocator >
inline void swap( hash_map<Key, Value, HashFun, EqualKey, Allocator>& lhs,
                  hash_map<Key, Value, HashFun, EqualKey, Allocator>& rhs )
{
    lhs.swap( rhs );
}

template< typename Key, typename Value, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator==( const hash_map<Key, Value, HashFun, EqualKey, Allocator>& lhs,
                 const hash_map<Key, Value, HashFun, EqualKey, Allocator>& rhs )
{
    if( lhs.size() != rhs.size() || lhs.bucket_count() != rhs.bucket_count() )
        return false;
    return equal( lhs.begin(), lhs.end(), rhs.begin() );
}

template< typename Key, typename Value, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator!=( const hash_map<Key, Value, HashFun, EqualKey, Allocator>& lhs,
                 const hash_map<Key, Value, HashFun, EqualKey, Allocator>& rhs )
{
    return !( lhs == rhs );
}

template< typename Key, typename Value, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator<( const hash_map<Key, Value, HashFun, EqualKey, Allocator>& lhs,
                const hash_map<Key, Value, HashFun, EqualKey, Allocator>& rhs )
{
    typedef  typename hash_map<Key, Value, HashFun, EqualKey, Allocator>::
             value_compare  v_comp;

    if( lhs.size() > rhs.size() || lhs.bucket_count() > rhs.bucket_count() )
        return false;
    return lexicographical_compare( lhs.begin(), lhs.end(),
                                    rhs.begin(), rhs.end(), v_comp() );
}

template< typename Key, typename Value, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator>( const hash_map<Key, Value, HashFun, EqualKey, Allocator>& lhs,
                const hash_map<Key, Value, HashFun, EqualKey, Allocator>& rhs )
{
    return ( rhs < lhs );
}