245 lines
7.2 KiB
Plaintext
245 lines
7.2 KiB
Plaintext
|
// hash_map standard header
|
||
|
|
#pragma once
|
||
|
|
#ifndef _HASH_MAP_
|
||
|
|
#define _HASH_MAP_
|
||
|
|
#include <xhash>
|
||
|
|
|
||
|
|
#pragma pack(push,8)
|
||
|
|
#pragma warning(push,3)
|
||
|
|
_STD_BEGIN
|
||
|
|
|
||
|
|
// TEMPLATE CLASS _Hmap_traits
|
||
|
|
template<class _Kty, // key type
|
||
|
|
class _Ty, // mapped type
|
||
|
|
class _Tr, // comparator predicate type
|
||
|
|
class _Alloc, // actual allocator type (should be value allocator)
|
||
|
|
bool _Mfl> // true if multiple equivalent keys are permitted
|
||
|
|
class _Hmap_traits
|
||
|
|
{ // traits required to make _Hash behave like a map
|
||
|
|
public:
|
||
|
|
typedef _Kty key_type;
|
||
|
|
typedef pair<const _Kty, _Ty> value_type;
|
||
|
|
typedef _Tr key_compare;
|
||
|
|
typedef typename _Alloc::_TEMPLATE_MEMBER rebind<value_type>::other
|
||
|
|
allocator_type;
|
||
|
|
|
||
|
|
enum
|
||
|
|
{ // make multi parameter visible as an enum constant
|
||
|
|
_Multi = _Mfl};
|
||
|
|
|
||
|
|
_Hmap_traits()
|
||
|
|
: comp()
|
||
|
|
{ // construct with default comparator
|
||
|
|
}
|
||
|
|
|
||
|
|
_Hmap_traits(const _Tr& _Traits)
|
||
|
|
: comp(_Traits)
|
||
|
|
{ // construct with specified comparator
|
||
|
|
}
|
||
|
|
|
||
|
|
class value_compare
|
||
|
|
: public binary_function<value_type, value_type, bool>
|
||
|
|
{ // functor for comparing two element values
|
||
|
|
friend class _Hmap_traits<_Kty, _Ty, _Tr, _Alloc, _Mfl>;
|
||
|
|
|
||
|
|
public:
|
||
|
|
bool operator()(const value_type& _Left,
|
||
|
|
const value_type& _Right) const
|
||
|
|
{ // test if _Left precedes _Right by comparing just keys
|
||
|
|
return (comp(_Left.first, _Right.first));
|
||
|
|
}
|
||
|
|
|
||
|
|
value_compare(const key_compare& _Traits)
|
||
|
|
: comp(_Traits)
|
||
|
|
{ // construct with specified predicate
|
||
|
|
}
|
||
|
|
|
||
|
|
protected:
|
||
|
|
key_compare comp; // the comparator predicate for keys
|
||
|
|
};
|
||
|
|
|
||
|
|
static const _Kty& _Kfn(const value_type& _Val)
|
||
|
|
{ // extract key from element value
|
||
|
|
return (_Val.first);
|
||
|
|
}
|
||
|
|
|
||
|
|
_Tr comp; // the comparator predicate for keys
|
||
|
|
};
|
||
|
|
|
||
|
|
// TEMPLATE CLASS hash_map
|
||
|
|
template<class _Kty,
|
||
|
|
class _Ty,
|
||
|
|
class _Tr = hash_compare<_Kty, less<_Kty> >,
|
||
|
|
class _Alloc = allocator<pair<const _Kty, _Ty> > >
|
||
|
|
class hash_map
|
||
|
|
: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> >
|
||
|
|
{ // hash table of {key, mapped} values, unique keys
|
||
|
|
public:
|
||
|
|
typedef hash_map<_Kty, _Ty, _Tr, _Alloc> _Myt;
|
||
|
|
typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> > _Mybase;
|
||
|
|
typedef _Kty key_type;
|
||
|
|
typedef _Ty mapped_type;
|
||
|
|
typedef _Ty referent_type;
|
||
|
|
typedef _Tr key_compare;
|
||
|
|
typedef typename _Mybase::value_compare value_compare;
|
||
|
|
typedef typename _Mybase::allocator_type allocator_type;
|
||
|
|
typedef typename _Mybase::size_type size_type;
|
||
|
|
typedef typename _Mybase::difference_type difference_type;
|
||
|
|
typedef typename _Mybase::pointer pointer;
|
||
|
|
typedef typename _Mybase::const_pointer const_pointer;
|
||
|
|
typedef typename _Mybase::reference reference;
|
||
|
|
typedef typename _Mybase::const_reference const_reference;
|
||
|
|
typedef typename _Mybase::iterator iterator;
|
||
|
|
typedef typename _Mybase::const_iterator const_iterator;
|
||
|
|
typedef typename _Mybase::reverse_iterator reverse_iterator;
|
||
|
|
typedef typename _Mybase::const_reverse_iterator
|
||
|
|
const_reverse_iterator;
|
||
|
|
typedef typename _Mybase::value_type value_type;
|
||
|
|
|
||
|
|
hash_map()
|
||
|
|
: _Mybase(key_compare(), allocator_type())
|
||
|
|
{ // construct empty map from defaults
|
||
|
|
}
|
||
|
|
|
||
|
|
explicit hash_map(const key_compare& _Traits)
|
||
|
|
: _Mybase(_Traits, allocator_type())
|
||
|
|
{ // construct empty map from comparator
|
||
|
|
}
|
||
|
|
|
||
|
|
hash_map(const key_compare& _Traits, const allocator_type& _Al)
|
||
|
|
: _Mybase(_Traits, _Al)
|
||
|
|
{ // construct empty map from comparator and allocator
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_map(_Iter _First, _Iter _Last)
|
||
|
|
: _Mybase(key_compare(), allocator_type())
|
||
|
|
{ // construct map from sequence, defaults
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits)
|
||
|
|
: _Mybase(_Traits, allocator_type())
|
||
|
|
{ // construct map from sequence, comparator
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits,
|
||
|
|
const allocator_type& _Al)
|
||
|
|
: _Mybase(_Traits, _Al)
|
||
|
|
{ // construct map from sequence, comparator, and allocator
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
mapped_type& operator[](const key_type& _Keyval)
|
||
|
|
{ // find element matching _Keyval or insert with default mapped
|
||
|
|
iterator _Where =
|
||
|
|
insert(value_type(_Keyval, mapped_type())).first;
|
||
|
|
return ((*_Where).second);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
// TEMPLATE CLASS hash_multimap
|
||
|
|
template<class _Kty,
|
||
|
|
class _Ty,
|
||
|
|
class _Tr = hash_compare<_Kty, less<_Kty> >,
|
||
|
|
class _Alloc = allocator<pair<const _Kty, _Ty> > >
|
||
|
|
class hash_multimap
|
||
|
|
: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> >
|
||
|
|
{ // hash table of {key, mapped} values, non-unique keys
|
||
|
|
public:
|
||
|
|
typedef hash_multimap<_Kty, _Ty, _Tr, _Alloc> _Myt;
|
||
|
|
typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> > _Mybase;
|
||
|
|
typedef _Kty key_type;
|
||
|
|
typedef _Ty mapped_type;
|
||
|
|
typedef _Ty referent_type; // old name, magically gone
|
||
|
|
typedef _Tr key_compare;
|
||
|
|
typedef typename _Mybase::value_compare value_compare;
|
||
|
|
typedef typename _Mybase::allocator_type allocator_type;
|
||
|
|
typedef typename _Mybase::size_type size_type;
|
||
|
|
typedef typename _Mybase::difference_type difference_type;
|
||
|
|
typedef typename _Mybase::pointer pointer;
|
||
|
|
typedef typename _Mybase::const_pointer const_pointer;
|
||
|
|
typedef typename _Mybase::reference reference;
|
||
|
|
typedef typename _Mybase::const_reference const_reference;
|
||
|
|
typedef typename _Mybase::iterator iterator;
|
||
|
|
typedef typename _Mybase::const_iterator const_iterator;
|
||
|
|
typedef typename _Mybase::reverse_iterator reverse_iterator;
|
||
|
|
typedef typename _Mybase::const_reverse_iterator
|
||
|
|
const_reverse_iterator;
|
||
|
|
typedef typename _Mybase::value_type value_type;
|
||
|
|
|
||
|
|
hash_multimap()
|
||
|
|
: _Mybase(key_compare(), allocator_type())
|
||
|
|
{ // construct empty map from defaults
|
||
|
|
}
|
||
|
|
|
||
|
|
explicit hash_multimap(const key_compare& _Traits)
|
||
|
|
: _Mybase(_Traits, allocator_type())
|
||
|
|
{ // construct empty map from comparator
|
||
|
|
}
|
||
|
|
|
||
|
|
hash_multimap(const key_compare& _Traits,
|
||
|
|
const allocator_type& _Al)
|
||
|
|
: _Mybase(_Traits, _Al)
|
||
|
|
{ // construct empty map from comparator and allocator
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_multimap(_Iter _First, _Iter _Last)
|
||
|
|
: _Mybase(key_compare(), allocator_type())
|
||
|
|
{ // construct map from sequence, defaults
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits)
|
||
|
|
: _Mybase(_Traits, allocator_type())
|
||
|
|
{ // construct map from sequence, comparator
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits,
|
||
|
|
const allocator_type& _Al)
|
||
|
|
: _Mybase(_Traits, _Al)
|
||
|
|
{ // construct map from sequence, comparator, and allocator
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
this->insert(*_First);
|
||
|
|
}
|
||
|
|
|
||
|
|
iterator insert(const value_type& _Val)
|
||
|
|
{ // insert a {key, mapped} value
|
||
|
|
return (_Mybase::insert(_Val).first);
|
||
|
|
}
|
||
|
|
|
||
|
|
iterator insert(iterator _Where, const value_type& _Val)
|
||
|
|
{ // insert a {key, mapped} value, with hint
|
||
|
|
return (_Mybase::insert(_Where, _Val));
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Iter>
|
||
|
|
void insert(_Iter _First, _Iter _Last)
|
||
|
|
{ // insert [_First, _Last), arbitrary iterators
|
||
|
|
for (; _First != _Last; ++_First)
|
||
|
|
insert(*_First);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
_STD_END
|
||
|
|
#pragma warning(pop)
|
||
|
|
#pragma pack(pop)
|
||
|
|
|
||
|
|
#endif /* _HASH_MAP_ */
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Copyright (c) 1992-2001 by P.J. Plauger. ALL RIGHTS RESERVED.
|
||
|
|
* Consult your license regarding permissions and restrictions.
|
||
|
|
V3.10:0009 */
|