std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator > Template-Klassenreferenz

#include <hash_map.hpp>

Öffentliche Typen
using	value_type = std::pair< TKey, TValue >
using	key_type = TKey
using	mapped_type = TValue
using	allocator_type = TAllocator
using	iterator = node_iterator< node *, value_type *, value_type & >
using	const_iterator = node_iterator< const node *, const value_type *, const value_type & >
using	size_type = int

Öffentliche Methoden
	hash_map ()
	hash_map (const allocator_type &allocator)
	hash_map (size_type initial_bucket_count, const allocator_type &allocator=allocator_type())
	hash_map (size_type initial_bucket_count, const THashFunc &hashFunc, const allocator_type &allocator=allocator_type())
	hash_map (const hash_map &rhs, const allocator_type &allocator=allocator_type())
	hash_map (e_noinitialize)
	~hash_map ()
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
mapped_type &	operator[] (const key_type &key)
hash_map &	operator= (const hash_map &rhs)
void	swap (hash_map &rhs)
std::pair< iterator, bool >	insert (const value_type &v)
size_type	erase (const key_type &key)
void	erase (iterator it)
void	erase (iterator from, iterator to)
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
void	clear ()
void	reserve (size_type min_size)
size_type	bucket_count () const
size_type	size () const
size_type	empty () const
size_type	nonempty_bucket_count () const
size_type	used_memory () const
const allocator_type &	get_allocator () const
void	set_allocator (const allocator_type &allocator)

Statische öffentliche Attribute
static const size_type	kNodeSize = sizeof(node)
static const size_type	kInitialCapacity = 64

Ausführliche Beschreibung

template<typename TKey, typename TValue, class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>
class std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >

Dokumentation der benutzerdefinierten Datentypen

allocator_type

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::allocator_type = TAllocator

const_iterator

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::const_iterator = node_iterator<const node*, const value_type*, const value_type&>

iterator

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::iterator = node_iterator<node*, value_type*, value_type&>

key_type

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::key_type = TKey

mapped_type

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::mapped_type = TValue

size_type

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::size_type = int

value_type

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

using std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::value_type = std::pair<TKey, TValue>

Beschreibung der Konstruktoren und Destruktoren

hash_map() [1/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( )

inline

                       :  m_nodes(&ms_emptyNode), m_size(0), m_capacity(0), m_capacityMask(0), m_numUsed(0)
            {
                    assert((kInitialCapacity & (kInitialCapacity - 1)) == 0);   // Must be power-of-two
            }

hash_map() [2/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( const allocator_type &  allocator )

inlineexplicit

                    : m_nodes(&ms_emptyNode), m_size(0), m_capacity(0), m_capacityMask(0), m_numUsed(0), m_allocator(allocator)
            {
            }

hash_map() [3/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( size_type  initial_bucket_count, const allocator_type &  allocator = allocator_type()  )

inlineexplicit

                    : m_nodes(&ms_emptyNode), m_size(0), m_capacity(0), m_capacityMask(0), m_numUsed(0), m_allocator(allocator)
            {
                    reserve(initial_bucket_count);
            }

hash_map() [4/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( size_type  initial_bucket_count, const THashFunc &  hashFunc, const allocator_type &  allocator = allocator_type()  )

inline

                    : m_nodes(&ms_emptyNode), m_size(0), m_capacity(0), m_capacityMask(0), m_numUsed(0), m_hashFunc(hashFunc), m_allocator(allocator)
            {
                    reserve(initial_bucket_count);
            }

hash_map() [5/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( const hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator > &  rhs, const allocator_type &  allocator = allocator_type()  )

inline

                    : m_nodes(&ms_emptyNode), m_size(0), m_capacity(0), m_capacityMask(0), m_numUsed(0), m_allocator(allocator)
            {
                    *this = rhs;
            }

hash_map() [6/6]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::hash_map ( e_noinitialize  )

inlineexplicit

            {
                    
            }

~hash_map()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::~hash_map ( )

inline

            {
                    delete_nodes();
            }

Dokumentation der Elementfunktionen

begin() [1/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::begin ( )

inline

            {
                iterator it(m_nodes, this);
                it.move_to_next_occupied_node();
                return it;
            }

begin() [2/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const_iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::begin ( ) const

inline

            {
                const_iterator it(m_nodes, this);
                it.move_to_next_occupied_node();
                return it;
            }

bucket_count()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::bucket_count ( ) const

inline

        { 
            return m_capacity; 
        }

clear()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::clear ( )

inline

        {
            node* endNode = m_nodes + m_capacity;
            for (node* iter = m_nodes; iter != endNode; ++iter)
            {
                if( iter )
                {
                    if (iter->is_occupied())
                    {
                        std::destruct(&iter->data);
                    }
                    iter->hash = node::kUnusedHash;
                }
            }
            m_size = 0;
            m_numUsed = 0;
        }

empty()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::empty ( ) const

inline

        { 
            return size() == 0; 
        }

end() [1/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::end ( )

inline

            { 
                    return iterator(m_nodes + m_capacity, this); 
            }

end() [2/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const_iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::end ( ) const

inline

            { 
                    return const_iterator(m_nodes + m_capacity, this); 
            }

erase() [1/3]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::erase ( const key_type &  key )

inline

            {
                    node* n = lookup(key);
                    if (n != (m_nodes + m_capacity) && n->is_occupied())
                    {
                            erase_node(n);
                    return 1;
                }
                    return 0;
            }

erase() [2/3]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::erase ( iterator  it )

inline

        {
            assert(it.get_map() == this);
            if (it != end())
            {
                assert(!empty());
                erase_node(it.node());
            }
        }

erase() [3/3]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::erase ( iterator  from, iterator  to  )

inline

        {
            for (; from != to; ++from)
            {
                node* n = from.node();
                if (n->is_occupied())
                    erase_node(n);
            }
        }

find() [1/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::find ( const key_type &  key )

inline

        {
            node* n = lookup(key);
            return iterator(n, this);
        }

find() [2/2]

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const_iterator std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::find ( const key_type &  key ) const

inline

        {
            const node* n = lookup(key);
            return const_iterator(n, this);
        }

get_allocator()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const allocator_type& std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::get_allocator ( ) const

inline

        { 
            return m_allocator; 
        }

insert()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

std::pair<iterator, bool> std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::insert ( const value_type &  v )

inline

            {
                            typedef std::pair<iterator, bool> ret_type_t;
                            assert(invariant());
                            if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
                                    grow();

                            hash_value_t hash;
                            node* n = find_for_insert(v.first, &hash);
                            if (n->is_occupied())
                            {
                            assert(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
                            return ret_type_t(iterator(n, this), false);
                            }
                            if (n->is_unused())
                                    ++m_numUsed;

                            std::copy_construct(&n->data, v);
                            n->hash = hash;
                            ++m_size;
                            assert(invariant());
                            return ret_type_t(iterator(n, this), true);
            }

nonempty_bucket_count()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::nonempty_bucket_count ( ) const

inline

        { 
            return m_numUsed; 
        }

operator=()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

hash_map& std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::operator= ( const hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator > &  rhs )

inline

            {
                assert(invariant());
                if (&rhs != this)
                {
                    clear();
                    if (m_capacity < rhs.bucket_count())
                    {
                        delete_nodes();
                        m_nodes = allocate_nodes(rhs.bucket_count());
                        m_capacity = rhs.bucket_count();
                        m_capacityMask = m_capacity - 1;
                    }
                    rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes, false);
                    m_size = rhs.size();
                    m_numUsed = rhs.m_numUsed;
                }
                assert(invariant());
                return *this;
            }

operator[]()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

mapped_type& std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::operator[] ( const key_type &  key )

inline

            {
                hash_value_t hash;
                node* n = find_for_insert(key, &hash);
                if (n == 0 || !n->is_occupied())
                {
                        return insert_at(value_type(key, TValue()), n, hash).first->second;
                }
                return n->data.second;
            }

reserve()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::reserve ( size_type  min_size )

inline

        {
            size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
            while (newCapacity < min_size)
                    newCapacity *= 2;
            if (newCapacity > m_capacity)
                    grow(newCapacity);
        }

set_allocator()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::set_allocator ( const allocator_type &  allocator )

inline

        {
            m_allocator = allocator;
        }

size()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::size ( ) const

inline

        { 
            return m_size; 
        }

swap()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

void std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::swap ( hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator > &  rhs )

inline

            {
                if (&rhs != this)
                {
                    assert(invariant());
                    assert(m_allocator == rhs.m_allocator);
                    std::swap(m_nodes, rhs.m_nodes);
                    std::swap(m_size, rhs.m_size);
                    std::swap(m_capacity, rhs.m_capacity);
                    std::swap(m_capacityMask, rhs.m_capacityMask);
                    std::swap(m_numUsed, rhs.m_numUsed);
                    std::swap(m_hashFunc, rhs.m_hashFunc);
                    std::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
                    assert(invariant());
                }
            }

used_memory()

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::used_memory ( ) const

inline

        {
            return bucket_count() * kNodeSize;
        }

Dokumentation der Datenelemente

kInitialCapacity

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::kInitialCapacity = 64

static

kNodeSize

template<typename TKey , typename TValue , class THashFunc = std::hash<TKey>, int TLoadFactor4 = 6, class TKeyEqualFunc = std::equal_to<TKey>, class TAllocator = std::allocator>

const size_type std::hash_map< TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator >::kNodeSize = sizeof(node)

static

---

Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Datei:

• include/hash_map.hpp