An instance map of the parameterized data type Unique_hash_map<Key,Data,UniqueHashFunction> 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 stored in map. The template parameter has as default the Handle_hash_function that hashes all types of pointers, handles, iterators, and circulators.
All variables are initialized to default_data, a value of type Data specified in the definition of map.
#include <CGAL/Unique_hash_map.h>
| |
the Key type.
| |
| |
the Data type.
| |
| |
the unique hash function type.
|
In compliance with STL, the types key_type, data_type, and hasher are defined as well.
| |||
creates an injective function map 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.
| |||
| |||
creates an injective function map 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.
|
UniqueHashFunction
CGAL::Handle_hash_function
Unique_hash_map is implemented via a chained hashing scheme. Access operations map[i] take expected time . 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 [MN00, Chapter 5]. This implementation makes also use of sentinels that lead to defined keys that have not been inserted.