bdlc_flathashtable

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Load Factor and Resizing
  • Requirements on KEY, ENTRY, ENTRY_UTIL, HASH, and EQUAL
  • Iterator, Pointer, and Reference Invalidation
  • Exception Safety
  • Move Semantics in C++03
  • Usage

Purpose

Provide an open-addressed hash table like Abseil flat_hash_map.

Classes

• bdlc::FlatHashTable: open-addressed hash table like Abseil flat_hash_map

See also

bdlc_flathashmap, bdlc_flathashset

Description

This component provides the class template bdlc::FlatHashTable, which forms the underlying implementation of bdlc::FlatHashMap and bdlc::FlatHashSet. It is based on the Abseil implementation of flat_hash_map. The data structure is an open-addressed hash table. (In "open addressing", entries are kept in an array, the hash value of an entry points to its possible initial location, and searches for an entry proceed by stepping to other positions in the table. This differs from "separate chaining", in which the hash value is used to locate a "bucket" of entries that all have the same hash value.)

This version differs from typical open-addressing schemes in that it uses an array of bytes parallel to the array of entries to hold hashlets (for this implementation, the seven lowest-order bits of the hash) of used entries or indicators of unused (empty or erased) entries. This hashlet array permits use of platform-specific instructions to optimize various methods (e.g., through use of SSE instructions).

The implemented data structure is inspired by Google's flat_hash_map CppCon presentations (available on YouTube). The implementation draws from Google's open source raw_hash_set.h file at: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal.

Load Factor and Resizing

An invariant of bdlc::FlatHashTable is that 0 <= load_factor() <= max_load_factor() <= 1.0. Any operation that would result in load_factor() > max_load_factor() for a bdlc::FlatHashTable instance causes the capacity to increase. This resizing allocates new memory, copies or moves all elements to the new memory, and reclaims the original memory. The transfer of elements involves rehashing the element to determine its new location. As such, all iterators, pointers, and references to elements of the bdlc::FlatHashTable are invalidated.

Note that the value returned by max_load_factor is implementation dependent and cannot be changed by the user.

Requirements on KEY, ENTRY, ENTRY_UTIL, HASH, and EQUAL

The template parameter type ENTRY must be copy or move constructible. The template parameter types HASH and EQUAL must be default and copy constructible function objects.

ENTRY_UTIL must support static methods constructFromKey, construct, and key compatible with the following statements for objects entry of type ENTRY, key of type KEY, and allocator of type bslma::Allocator:

ENTRY_UTIL::constructFromKey(&entry, &allocator, key);
ENTRY_UTIL::construct(&entry, &allocator, args...);
const KEY& keyOfEntry = ENTRY_UTIL::key(entry);

HASH must support a function call operator compatible with the following statements for an object key of type KEY:

HASH        hash;
bsl::size_t result = hash(key);

EQUAL must support a function call operator compatible with the following statements for objects key1 and key2 of type KEY:

EQUAL equal;
bool  result = equal(key1, key2);

where the definition of the called function defines an equivalence relationship on keys that is both reflexive and transitive.

HASH and EQUAL function-objects are further constrained; if the comparator claims that two values are equal, the hasher must produce the same hash value for each.

If support for operator== is required, the type ENTRY must be equality-comparable.

Iterator, Pointer, and Reference Invalidation

Any change in capacity of a bdlc::FlatHashTable invalidates all pointers, references, and iterators. A bdlc::FlatHashTable manipulator that erases an element invalidates all pointers, references, and iterators to the erased elements.

Exception Safety

A bdlc::FlatHashTable is exception neutral, and all of the methods of bdlc::FlatHashTable provide the basic exception safety guarantee (see {bsldoc_glossary |Basic Guarantee}).

Move Semantics in C++03

Move-only types are supported by bdlc::FlatHashTable on C++11, and later, platforms only (where BSLMF_MOVABLEREF_USES_RVALUE_REFERENCES is defined), and are not supported on C++03 platforms. Unfortunately, in C++03, there are user types where a bslmf::MovableRef will not safely degrade to a lvalue reference when a move constructor is not available (types providing a constructor template taking any type), so bslmf::MovableRefUtil::move cannot be used directly on a user supplied template type. See internal bug report 99039150 for more information.

Usage

There is no usage example for this component since it is not meant for direct client use.