\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0 - Profiling tools, Hash Map, Union-find, Modifiers
List of all members
CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator > Class Template Reference
Profiling Tools, Hash Map, Union-find, Modifiers Reference

#include <CGAL/Unique_hash_map.h>

Definition

An instance of the class template Unique_hash_map is an injective mapping from the set of keys of type Key to the set of variables of type Data.

New keys can be inserted at any time, however keys cannot be individually deleted.

An object hash of the type UniqueHashFunction returns a unique integer index hash(key) of type std::size_t for all objects \( key\) stored in map. The template parameter has as default the Handle_hash_function that hashes all types of pointers, handles, iterators, and circulators.

The parameter Allocator has to match the standard allocator requirements, with value type Data. This parameter has the default value CGAL_ALLOCATOR(Data).

All variables are initialized to default_data, a value of type Data specified in the definition of map.

See also
UniqueHashFunction
CGAL::Handle_hash_function

Implementation

Unique_hash_map is implemented via a chained hashing scheme. Access operations map[i] take expected time \( O(1)\). The table_size parameter passed to chained hashing can be used to avoid unnecessary rehashing when set to the number of expected elements in the map. The design is derived from the STL hash_map and the LEDA type map. Its specialization on insertion only and unique hash values allow for a more time- and space-efficient implementation, see also [2], Chapter 5. This implementation makes also use of sentinels that lead to defined keys that have not been inserted.

Types

In compliance with stl, the types key_type, data_type, and hasher are defined as well.

typedef unspecified_type Key
 the Key type.
 
typedef unspecified_type Data
 the Data type.
 
typedef unspecified_type Hash_function
 the unique hash function type.
 

Creation

 Unique_hash_map (const Data &default=Data(), std::size_t table_size=1, const Hash_function &fct=Hash_function())
 creates an injective function from Key to the set of unused variables of type Data, sets default_data to default, passes the table_size as argument to the internal implementation, and initializes the hash function with fct.
 
 Unique_hash_map (Key first1, Key beyond1, Data first2, const Data &default=Data(), std::size_t table_size=1, const Hash_function &fct=Hash_function())
 creates an injective function from Key to the set of unused variables of type Data, sets default_data to default, passes the table_size as argument to the internal implementation, initializes the hash function with fct, and inserts all keys from the range [first1,beyond1). More...
 

Operations

Data default_value () const
 the current default_value.
 
Hash_function hash_function () const
 the current hash function.
 
bool is_defined (const Key &key) const
 returns true if \( key\) is defined in *this. More...
 
void clear ()
 resets *this to the injective function from Key to the set of unused variables of type Data. More...
 
void clear (const Data &default)
 resets *this to the injective function from Key to the set of unused variables of type Data and sets default_data to default.
 
Data & operator[] (const Key &key)
 returns a reference to the variable map(key). More...
 
const Data & operator[] (const Key &key) const
 returns a const reference to the variable *this(key). More...
 
Data insert (Key first1, Key beyond1, Data first2)
 inserts all keys from the range [first1,beyond1). More...
 

Constructor & Destructor Documentation

◆ Unique_hash_map()

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::Unique_hash_map ( Key  first1,
Key  beyond1,
Data  first2,
const Data &  default = Data(),
std::size_t  table_size = 1,
const Hash_function &  fct = Hash_function() 
)

creates an injective function from Key to the set of unused variables of type Data, sets default_data to default, passes the table_size as argument to the internal implementation, initializes the hash function with fct, and inserts all keys from the range [first1,beyond1).

The data variable for each inserted key is initialized with the corresponding value from the range [first2, first2 + (beyond1-first1)).

Precondition
The increment operator must be defined for values of type Key and for values of type Data. beyond1 must be reachable from first1 using increments.

Member Function Documentation

◆ clear()

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
void CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::clear ( )

resets *this to the injective function from Key to the set of unused variables of type Data.

The default_data remains unchanged.

◆ insert()

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
Data CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::insert ( Key  first1,
Key  beyond1,
Data  first2 
)

inserts all keys from the range [first1,beyond1).

The data variable for each inserted key is initilized with the corresponding value from the range [first2, first2 + (beyond1-first1)). Returns first2 + (beyond1-first1).

Precondition
The increment operator must be defined for values of type Key and for values of type Data. beyond1 must be reachable from first1 using increments.

◆ is_defined()

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
bool CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::is_defined ( const Key &  key) const

returns true if \( key\) is defined in *this.

Note that there can be keys defined that have not been inserted explicitly. Their variables are initialized to default_value.

◆ operator[]() [1/2]

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
Data& CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::operator[] ( const Key &  key)

returns a reference to the variable map(key).

If key has not been inserted into map before, key is inserted and initialized with default_value.

◆ operator[]() [2/2]

template<typename Key , typename Data , typename UniqueHashFunction , typename Allocator >
const Data& CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >::operator[] ( const Key &  key) const

returns a const reference to the variable *this(key).

If key has not been inserted into *this before, a const reference to the default_value is returned. However, key is not inserted into *this.