mstl_hash_set.hpp

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

/*
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_SET_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_HASH_SET_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 HashFun = hash<Key>,
          typename EqualKey = equal_to<Key>,
          typename Allocator = allocator<Key> >
class hash_set
{
private:
    typedef  hash_table_node<Key>  node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  hash_table<Key, Key, HashFun, identity<Key>, EqualKey,
             node_alloc>  hash_table;
//    typedef  hash_table<Key, Key, HashFun, identity<Key>, EqualKey>
//             hash_table;
    typedef  typename hash_table::iterator  ht_iterator;

    hash_table ht;

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

    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::const_reference  reference;
    typedef  typename hash_table::const_reference  const_reference;
    typedef  typename hash_table::const_pointer    pointer;
    typedef  typename hash_table::const_pointer    const_pointer;
    typedef  typename hash_table::const_iterator   iterator;
    typedef  typename hash_table::const_iterator   const_iterator;



    hash_set() : ht(0)  {}

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

    template< typename InputIterator >
    hash_set( 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() const  {  return ht.begin();  }
    iterator end() const    {  return ht.end();  }

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

    pair<iterator, 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( const_iter_cast(pos) );  }
    void erase( iterator first, iterator last )
        {  ht.erase( const_iter_cast(first), const_iter_cast(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( const_iter_cast(position), new_key );  }

    pair<iterator, bool> insert( const value_type& v )
    {
        pair<ht_iterator, bool> pItr = ht.insert_unique( v );
        return pair<iterator, bool>( pItr.first, pItr.second );
    }

    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
    {
        ht.insert_unique( first, last );
    }

};



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

template< typename Key, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator==( const hash_set<Key, HashFun, EqualKey, Allocator>& lhs,
                 const hash_set<Key, 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 HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator!=( const hash_set<Key, HashFun, EqualKey, Allocator>& lhs,
                 const hash_set<Key, HashFun, EqualKey, Allocator>& rhs )
{
    return !( lhs == rhs );
}

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

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

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

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

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

template< typename Key, typename HashFun = hash<Key>,
          typename EqualKey = equal_to<Key>,
          typename Allocator = allocator<Key> >
class hash_multiset
{
private:
    typedef  hash_table_node<Key>  node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  hash_table<Key, Key, HashFun, identity<Key>, EqualKey,
             node_alloc>  hash_table;
//    typedef  hash_table<Key, Key, HashFun, identity<Key>, EqualKey>
//             hash_table;
    typedef  typename hash_table::iterator  ht_iterator;

    hash_table ht;

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

    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::const_reference  reference;
    typedef  typename hash_table::const_reference  const_reference;
    typedef  typename hash_table::const_pointer    pointer;
    typedef  typename hash_table::const_pointer    const_pointer;
    typedef  typename hash_table::const_iterator   iterator;
    typedef  typename hash_table::const_iterator   const_iterator;



    hash_multiset() : ht(0)  {}

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

    template< typename InputIterator >
    hash_multiset( InputIterator first, InputIterator last,
                   size_type n = 0, const hasher& hf = hasher(),
                   const key_equal& eq = key_equal() ) : ht(n, hf, eq)
    {
        ht.insert_equal( 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() const  {  return ht.begin();  }
    iterator end() const    {  return ht.end();  }

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

    pair<iterator, 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( const_iter_cast(pos) );  }
    void erase( iterator first, iterator last )
        {  ht.erase( const_iter_cast(first), const_iter_cast(last) );  }

    void modify_key( const key_type& k, const key_type& new_key )
        {  ht.modify_key_equal( k, new_key );  }
    void modify_key( iterator position, const key_type& new_key )
        {  ht.modify_key_equal( const_iter_cast(position), new_key );  }

    iterator insert( const value_type& v )
        {  return ht.insert_equal( v );  }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  ht.insert_equal( first, last );  }

};



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

template< typename Key, typename HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator==( const hash_multiset<Key, HashFun, EqualKey, Allocator>& lhs,
                 const hash_multiset<Key, 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 HashFun, typename EqualKey,
          typename Allocator >
inline
bool operator!=( const hash_multiset<Key, HashFun, EqualKey, Allocator>& lhs,
                 const hash_multiset<Key, HashFun, EqualKey, Allocator>& rhs )
{
    return !( lhs == rhs );
}

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

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

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

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

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------