ycpp_unordered_set.hpp

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

    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();
        }
    }

    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()
    {
        youngc::ylib_fp_copy_t cp = init_copy_adapter<value_type>;
        youngc::ylib_fp_oper_t dsty = destroy_adapter<value_type>;

        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   property_traits<value_type>::trivial_copy ? NULL : cp,
                   property_traits<value_type>::trivial_destructor ? NULL : dsty,
                   NULL, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

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



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

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

template< typename Key,
#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<Key> >
class unordered_multiset
{
public:
    typedef  unordered_multiset<Key, HashKey, EqualKey, Allocator>  self;

    typedef  Key            key_type;
    typedef  Key            value_type;
    typedef  EqualKey       key_equal;
    typedef  EqualKey       value_equal;
    typedef  Allocator      allocator_type;

    typedef  size_t         size_type;
    typedef  ptrdiff_t      difference_type;
    typedef  const Key&     reference;
    typedef  const Key&     const_reference;
    typedef  const Key*     pointer;
    typedef  const Key*     const_pointer;

    typedef  uoset_iterator<Key, HashKey, EqualKey, Allocator>  iterator;
    typedef  uoset_iterator<Key, HashKey, EqualKey, Allocator>  const_iterator;

    typedef  uoset_local_iterator<Key, HashKey, EqualKey, Allocator>
             local_iterator;
    typedef  uoset_local_iterator<Key, HashKey, EqualKey, Allocator>
             const_local_iterator;

    explicit unordered_multiset( size_type n = 100 )
    {
        init();
        if( !hstb_rehash( &m_ht, n ) )
            throw std::bad_alloc();
    }

    template< typename InputIterator >
    unordered_multiset( InputIterator first, InputIterator last,
                        size_type n = 100 )
    {
        init();
        if( !hstb_rehash( &m_ht, n ) )
            throw std::bad_alloc();
        try {  insert( first, last );  }
        catch(...) {  hstb_destroy( &m_ht );  throw;  }
    }

    unordered_multiset( 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_multiset()  {  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() const  {  return hstb_begin( &m_ht );  }
    iterator end() const    {  return hstb_end( &m_ht );  }

    local_iterator begin( size_type index ) const
        {  return hstb_local_begin( &m_ht, index );  }
    local_iterator end( size_type index ) const
        {  return 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 ) const
        {  return hstb_find( &m_ht, &k );  }

    std::pair<iterator, iterator> equal_range( const key_type& k ) const
    {
        youngc::hstb_pair_iterator pr = hstb_equal_range( &m_ht, &k );
        return std::pair<iterator, 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()
    {
        youngc::ylib_fp_copy_t cp = init_copy_adapter<value_type>;
        youngc::ylib_fp_oper_t dsty = destroy_adapter<value_type>;

        hstb_init( &m_ht, 1.0, sizeof(value_type),
                   property_traits<value_type>::trivial_copy ? NULL : cp,
                   property_traits<value_type>::trivial_destructor ? NULL : dsty,
                   NULL, eq_adapter<Key, EqualKey>, hash_adapter,
                   alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

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



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

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