High-performance hash set using open addressing with Robin Hood hashing. More...

#include <NCollection_FlatMap.hxx>

Data Structures
class	Iterator
	Forward iterator for NCollection_FlatMap. More...

Public Types
using	key_type = TheKeyType
	STL-compliant type alias for key type.

Public Member Functions
	NCollection_FlatMap ()
	Default constructor.

	NCollection_FlatMap (const size_t theNbBuckets)
	Constructor with initial capacity hint.

	NCollection_FlatMap (const Hasher &theHasher, const size_t theNbBuckets=0)
	Constructor with custom hasher (copy).

	NCollection_FlatMap (Hasher &&theHasher, const size_t theNbBuckets=0)
	Constructor with custom hasher (move).

	NCollection_FlatMap (const NCollection_FlatMap &theOther)
	Copy constructor.

	NCollection_FlatMap (NCollection_FlatMap &&theOther) noexcept
	Move constructor.

	~NCollection_FlatMap ()
	Destructor.

NCollection_FlatMap &	operator= (const NCollection_FlatMap &theOther)
	Copy assignment.

NCollection_FlatMap &	operator= (NCollection_FlatMap &&theOther) noexcept
	Move assignment.

size_t	Size () const noexcept
	Returns number of elements.

bool	IsEmpty () const noexcept
	Returns true if map is empty.

size_t	Capacity () const noexcept
	Returns current capacity.

bool	Contains (const TheKeyType &theKey) const
	Check if key exists.

std::optional< std::reference_wrapper< const TheKeyType > >	Contained (const TheKeyType &theKey) const
	Contained returns optional const reference to the key in the map. Returns std::nullopt if the key is not found.

const TheKeyType *	Seek (const TheKeyType &theKey) const
	Seek returns pointer to key in map. Returns NULL if not found.

TheKeyType *	ChangeSeek (const TheKeyType &theKey)
	ChangeSeek returns modifiable pointer to key in map. Returns NULL if not found.

bool	Add (const TheKeyType &theKey)
	Add key to set.

bool	Add (TheKeyType &&theKey)
	Add key to set (move semantics)

const TheKeyType &	Added (const TheKeyType &theKey)
	Added: add a new key if not yet in the map, and return reference to either newly added or previously existing key.

const TheKeyType &	Added (TheKeyType &&theKey)
	Added: add a new key if not yet in the map, and return reference to either newly added or previously existing key.

template<typename... Args>
bool	Emplace (Args &&... theArgs)
	Emplace constructs key in-place; if key exists, overwrites.

template<typename... Args>
const TheKeyType &	Emplaced (Args &&... theArgs)
	Emplaced constructs key in-place; if key exists, overwrites.

template<typename... Args>
bool	TryEmplace (Args &&... theArgs)
	TryEmplace constructs key in-place only if not already present.

template<typename... Args>
const TheKeyType &	TryEmplaced (Args &&... theArgs)
	TryEmplaced constructs key in-place only if not already present.

bool	Remove (const TheKeyType &theKey)
	Remove key from set.

void	Clear (bool doReleaseMemory=false)
	Clear all elements.

void	Exchange (NCollection_FlatMap &theOther) noexcept
	Exchange content with another map.

const Hasher &	GetHasher () const noexcept
	Returns const reference to the hasher.

void	reserve (size_t theN)
	Reserve capacity for at least theN elements.

Iterator	begin () const noexcept

Iterator	end () const noexcept

Iterator	cbegin () const noexcept

Iterator	cend () const noexcept

Detailed Description

template<class TheKeyType, class Hasher = NCollection_DefaultHasher<TheKeyType>>
class NCollection_FlatMap< TheKeyType, Hasher >

High-performance hash set using open addressing with Robin Hood hashing.

NCollection_FlatMap is an alternative to NCollection_Map that provides better cache locality and reduced memory allocation overhead by storing all keys inline in a contiguous array.

Key features:

Open addressing with linear probing (better cache locality)
Robin Hood hashing (reduces probe sequence variance)
Power-of-2 sizing for fast modulo operations
No per-element allocations

Typical faster usage patterns:

POD or small key types
Performance-critical code paths
Lookup-heavy workloads (Contains()/Seek())
Full traversal / iteration-heavy workloads
Stable-size maps with Reserve() called once before bulk insert

Container-specific implementation notes:

Remove() keeps probe clusters consistent using backward-shift compaction.

Relative to NCollection_Map:

Add()/Remove() can be faster in many workloads thanks to contiguous storage and no per-element node allocation.
Iteration is often faster due to contiguous slot scanning and reduced pointer chasing.

Limitations:

Keys must be movable
Higher memory usage at low load factors
Iteration order is not insertion order
Probe distance grows with collisions (bounded by table capacity)

Note: This class is NOT thread-safe. External synchronization is required for concurrent access from multiple threads.

Template Parameters

TheKeyType	Type of keys
Hasher	Hash and equality functor (default: NCollection_DefaultHasher)

Member Typedef Documentation

◆ key_type

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

using NCollection_FlatMap< TheKeyType, Hasher >::key_type = TheKeyType

STL-compliant type alias for key type.

Constructor & Destructor Documentation

◆ NCollection_FlatMap() [1/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap ( )

inline

Default constructor.

◆ NCollection_FlatMap() [2/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap ( const size_t theNbBuckets )

inlineexplicit

Constructor with initial capacity hint.

◆ NCollection_FlatMap() [3/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap	(	const Hasher &	theHasher,
		const size_t	theNbBuckets = 0 )

inlineexplicit

Constructor with custom hasher (copy).

Parameters

theHasher	custom hasher instance
theNbBuckets	initial capacity hint

◆ NCollection_FlatMap() [4/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap	(	Hasher &&	theHasher,
		const size_t	theNbBuckets = 0 )

inlineexplicit

Constructor with custom hasher (move).

Parameters

theHasher	custom hasher instance (moved)
theNbBuckets	initial capacity hint

◆ NCollection_FlatMap() [5/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap ( const NCollection_FlatMap< TheKeyType, Hasher > & theOther )

inline

Copy constructor.

◆ NCollection_FlatMap() [6/6]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::NCollection_FlatMap ( NCollection_FlatMap< TheKeyType, Hasher > && theOther )

inlinenoexcept

Move constructor.

◆ ~NCollection_FlatMap()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap< TheKeyType, Hasher >::~NCollection_FlatMap ( )

inline

Destructor.

Member Function Documentation

◆ Add() [1/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

bool NCollection_FlatMap< TheKeyType, Hasher >::Add ( const TheKeyType & theKey )

inline

Add key to set.

Returns: true if key was newly added, false if already present

◆ Add() [2/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

bool NCollection_FlatMap< TheKeyType, Hasher >::Add ( TheKeyType && theKey )

inline

Add key to set (move semantics)

◆ Added() [1/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

const TheKeyType & NCollection_FlatMap< TheKeyType, Hasher >::Added ( const TheKeyType & theKey )

inline

Added: add a new key if not yet in the map, and return reference to either newly added or previously existing key.

Parameters

theKey key to add

Returns: const reference to the key in the map

◆ Added() [2/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

const TheKeyType & NCollection_FlatMap< TheKeyType, Hasher >::Added ( TheKeyType && theKey )

inline

Added: add a new key if not yet in the map, and return reference to either newly added or previously existing key.

Parameters

theKey key to add

Returns: const reference to the key in the map

◆ begin()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

Iterator NCollection_FlatMap< TheKeyType, Hasher >::begin ( ) const

inlinenoexcept

◆ Capacity()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

size_t NCollection_FlatMap< TheKeyType, Hasher >::Capacity ( ) const

inlinenoexcept

Returns current capacity.

◆ cbegin()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

Iterator NCollection_FlatMap< TheKeyType, Hasher >::cbegin ( ) const

inlinenoexcept

◆ cend()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

Iterator NCollection_FlatMap< TheKeyType, Hasher >::cend ( ) const

inlinenoexcept

◆ ChangeSeek()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

TheKeyType * NCollection_FlatMap< TheKeyType, Hasher >::ChangeSeek ( const TheKeyType & theKey )

inline

ChangeSeek returns modifiable pointer to key in map. Returns NULL if not found.

◆ Clear()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

void NCollection_FlatMap< TheKeyType, Hasher >::Clear ( bool doReleaseMemory = false )

inline

Clear all elements.

◆ Contained()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

std::optional< std::reference_wrapper< const TheKeyType > > NCollection_FlatMap< TheKeyType, Hasher >::Contained ( const TheKeyType & theKey ) const

inline

Contained returns optional const reference to the key in the map. Returns std::nullopt if the key is not found.

◆ Contains()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

bool NCollection_FlatMap< TheKeyType, Hasher >::Contains ( const TheKeyType & theKey ) const

inline

Check if key exists.

◆ Emplace()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

template<typename... Args>

bool NCollection_FlatMap< TheKeyType, Hasher >::Emplace ( Args &&... theArgs )

inline

Emplace constructs key in-place; if key exists, overwrites.

Parameters

theArgs arguments forwarded to key constructor

Returns: true if key was newly added, false if key already existed

◆ Emplaced()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

template<typename... Args>

const TheKeyType & NCollection_FlatMap< TheKeyType, Hasher >::Emplaced ( Args &&... theArgs )

inline

Emplaced constructs key in-place; if key exists, overwrites.

Parameters

theArgs arguments forwarded to key constructor

Returns: const reference to the key in the map

◆ end()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

Iterator NCollection_FlatMap< TheKeyType, Hasher >::end ( ) const

inlinenoexcept

◆ Exchange()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

void NCollection_FlatMap< TheKeyType, Hasher >::Exchange ( NCollection_FlatMap< TheKeyType, Hasher > & theOther )

inlinenoexcept

Exchange content with another map.

◆ GetHasher()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

const Hasher & NCollection_FlatMap< TheKeyType, Hasher >::GetHasher ( ) const

inlinenoexcept

Returns const reference to the hasher.

◆ IsEmpty()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

bool NCollection_FlatMap< TheKeyType, Hasher >::IsEmpty ( ) const

inlinenoexcept

Returns true if map is empty.

◆ operator=() [1/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap & NCollection_FlatMap< TheKeyType, Hasher >::operator= ( const NCollection_FlatMap< TheKeyType, Hasher > & theOther )

inline

Copy assignment.

◆ operator=() [2/2]

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

NCollection_FlatMap & NCollection_FlatMap< TheKeyType, Hasher >::operator= ( NCollection_FlatMap< TheKeyType, Hasher > && theOther )

inlinenoexcept

Move assignment.

◆ Remove()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

bool NCollection_FlatMap< TheKeyType, Hasher >::Remove ( const TheKeyType & theKey )

inline

Remove key from set.

Returns: true if key was found and removed

◆ reserve()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

void NCollection_FlatMap< TheKeyType, Hasher >::reserve ( size_t theN )

inline

Reserve capacity for at least theN elements.

◆ Seek()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

const TheKeyType * NCollection_FlatMap< TheKeyType, Hasher >::Seek ( const TheKeyType & theKey ) const

inline

Seek returns pointer to key in map. Returns NULL if not found.

◆ Size()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

size_t NCollection_FlatMap< TheKeyType, Hasher >::Size ( ) const

inlinenoexcept

Returns number of elements.

◆ TryEmplace()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

template<typename... Args>

bool NCollection_FlatMap< TheKeyType, Hasher >::TryEmplace ( Args &&... theArgs )

inline

TryEmplace constructs key in-place only if not already present.

Parameters

theArgs arguments forwarded to key constructor

Returns: true if key was newly added, false if key already existed

◆ TryEmplaced()

template<class TheKeyType , class Hasher = NCollection_DefaultHasher<TheKeyType>>

template<typename... Args>

const TheKeyType & NCollection_FlatMap< TheKeyType, Hasher >::TryEmplaced ( Args &&... theArgs )

inline

TryEmplaced constructs key in-place only if not already present.

Parameters

theArgs arguments forwarded to key constructor

Returns: const reference to the key (existing or newly added)

The documentation for this class was generated from the following file:

NCollection_FlatMap.hxx

Data Structures

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ key_type

Constructor & Destructor Documentation

◆ NCollection_FlatMap() [1/6]

◆ NCollection_FlatMap() [2/6]

◆ NCollection_FlatMap() [3/6]

◆ NCollection_FlatMap() [4/6]

◆ NCollection_FlatMap() [5/6]

◆ NCollection_FlatMap() [6/6]

◆ ~NCollection_FlatMap()

Member Function Documentation

◆ Add() [1/2]

◆ Add() [2/2]

◆ Added() [1/2]

◆ Added() [2/2]

◆ begin()

◆ Capacity()

◆ cbegin()

◆ cend()

◆ ChangeSeek()

◆ Clear()

◆ Contained()

◆ Contains()

◆ Emplace()

◆ Emplaced()

◆ end()

◆ Exchange()

◆ GetHasher()

◆ IsEmpty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ Remove()

◆ reserve()

◆ Seek()

◆ Size()

◆ TryEmplace()

◆ TryEmplaced()