CGAL 6.1 - Profiling tools, Hash Map, Union-find, Modifiers

Loading...
Searching...
No Matches
List of all members
CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator > Class Template Reference
Reference Manual

`#include <CGAL/Unique_hash_map.h>`

## Definition

template<typename Key, typename Data, typename UniqueHashFunction, typename Allocator>
class CGAL::Unique_hash_map< Key, Data, UniqueHashFunction, Allocator >

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)`.

## 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`.
void | reserve (std::size_t table_size)
| sets the table size.
void | clear ()
| resets `*this` to the injective function from `Key` to the set of unused variables of type `Data`.
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)`.
const Data & | operator[] (const Key &key) const
| returns a const reference to the variable `*this(key)`.
Data | insert (Key first1, Key beyond1, Data first2)
| inserts all keys from the range `[first1,beyond1)`.

## 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 initialized 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`.