Flat ordered multimap implemented as a sorted contiguous container. More...

#include <jh/core/flat_multimap.h>

Public Types
using	value_type = std::pair<K, V>
	Value type stored in the container (`std::pair<K, V>`).
using	allocator_type
	Allocator type rebound to `value_type`.
using	container_type = std::vector<value_type, allocator_type>
	Underlying contiguous storage type.
using	iterator = typename container_type::iterator
	Iterator type for the container.
using	const_iterator = typename container_type::const_iterator
	Const iterator type for the container.

Public Member Functions
	flat_multimap ()=default
	Default-construct an empty multimap.
	flat_multimap (const container_type &cont)
	Construct from an existing container.
	flat_multimap (container_type &&cont)
	Move-construct from an existing container.
	flat_multimap (const allocator_type &alloc)
	Construct an empty multimap with a specific allocator.
	flat_multimap (const container_type &cont, const allocator_type &alloc)
	Construct from a container and allocator.
	flat_multimap (container_type &&cont, const allocator_type &alloc)
	Move-construct from a container using a specific allocator.
	flat_multimap (const flat_multimap &)=default
	Copy-construct from another flat_multimap, using a rebound default allocator.
	flat_multimap (const flat_multimap &other, const allocator_type &alloc)
	Copy-construct from another flat_multimap, using a user-supplied allocator.
	flat_multimap (flat_multimap &&) noexcept=default
	Move-construct from another flat_multimap, using a rebound default allocator.
	flat_multimap (flat_multimap &&other, const allocator_type &alloc)
	Move-construct from another flat_multimap, using a user-supplied allocator.
flat_multimap &	operator= (const flat_multimap &)=default
	Copy assignment.
flat_multimap &	operator= (flat_multimap &&) noexcept=default
	Move assignment.
std::pair< iterator, iterator >	equal_range (const K &k)
	Return the range of elements equivalent to the given key.
std::pair< const_iterator, const_iterator >	equal_range (const K &k) const
	Return the range of elements equivalent to the given key (const overload).
iterator	find (const K &k)
	Locate the first element with the specified key.
const_iterator	find (const K &k) const
	Locate the first element with the specified key (const overload).
template<typename... Args>
iterator	emplace (Args &&... args)
	Insert a key-value pair by constructing it from arbitrary arguments.
template<typename P>
iterator	insert (P &&p)
	Insert a key-value pair into the map.
iterator	erase (iterator pos)
	Erase the element referenced by the given iterator.
iterator	erase (const_iterator pos)
	Erase the element referenced by the given const iterator.
iterator	erase (iterator first, iterator last)
	Erase a range of elements.
iterator	erase (const_iterator first, const_iterator last)
	Erase a range of elements.
size_t	erase (const K &k)
	Erase all elements whose key compares equal to the given key.
std::size_t	count (const K &key) const
	Count the number of elements with the specified key.
iterator	begin ()
	Return iterator to the first element.
iterator	end ()
	Return iterator past the last element.
const_iterator	begin () const
	Return const iterator to the first element.
const_iterator	end () const
	Return const iterator past the last element.
size_t	size () const
	Return the number of elements stored.
bool	empty () const
	Check whether the container is empty.
void	clear () noexcept
	Remove all elements from the container.
void	reserve (std::size_t n) noexcept(noexcept(storage_.reserve(n)))
	Reserve space for at least n elements.
void	shrink_to_fit () noexcept(noexcept(storage_.shrink_to_fit()))
	Request that the container reduce its capacity.
template<typename It>
void	bulk_insert (It first, It last)
	Insert a range of elements and restore ordering.

Detailed Description

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>
requires ( (requires(const K &a, const K &b) { { a < b } -> std::convertible_to<bool>; }) && jh::concepts::is_contiguous_reallocable<K> && jh::concepts::is_contiguous_reallocable<V>)
class jh::flat_multimap< K, V, Alloc >

Flat ordered multimap implemented as a sorted contiguous container.

Template Parameters

K	Key type. Must be strictly ordered via `operator<`.
V	Mapped value type.
Alloc	Allocator type used for underlying storage.

flat_multimap implements ordered multimap semantics by storing std::pair<K, V> elements in a contiguous container (std::vector) that is kept sorted by key.

Duplicate keys are permitted and are stored contiguously. Lookup and range queries are implemented using binary search (lower_bound, upper_bound), while insertion and erasure are expressed in terms of vector operations.

This container is optimized for:

range-oriented multimap semantics (equal_range, erase(key))
cache-friendly traversal and lookup
bulk insertion and reconstruction

Note: All insertions and erasures may invalidate iterators.
Unlike tree-based ordered containers, no node identity or pointer stability is preserved; elements may be relocated freely within the underlying storage.

Member Typedef Documentation

◆ allocator_type

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

using jh::flat_multimap< K, V, Alloc >::allocator_type

Initial value:

typename std::allocator_traits<Alloc>

::template rebind_alloc<value_type>

Allocator type rebound to value_type.

Constructor & Destructor Documentation

◆ flat_multimap() [1/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap ( const container_type & cont )

inlineexplicit

Construct from an existing container.

The contents of cont are copied into the internal storage and stably sorted by key. If the input is already sorted, the cost is near-linear.

Parameters

cont	Source container.

◆ flat_multimap() [2/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap ( container_type && cont )

inlineexplicit

Move-construct from an existing container.

The container is taken by move and then stably sorted by key.

Parameters

cont	Source container.

◆ flat_multimap() [3/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap ( const allocator_type & alloc )

inlineexplicit

Construct an empty multimap with a specific allocator.

Parameters

alloc Allocator used for underlying storage.

◆ flat_multimap() [4/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap	(	const container_type &	cont,
		const allocator_type &	alloc )

inline

Construct from a container and allocator.

The container is copied and then stably sorted by key.

Parameters

cont	Source container.
alloc	Allocator to use.

◆ flat_multimap() [5/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap	(	container_type &&	cont,
		const allocator_type &	alloc )

inline

Move-construct from a container using a specific allocator.

Parameters

cont	Source container.
alloc	Allocator to use.

◆ flat_multimap() [6/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap	(	const flat_multimap< K, V, Alloc > &	other,
		const allocator_type &	alloc )

inline

Copy-construct from another flat_multimap, using a user-supplied allocator.

Parameters

other	The source tree to copy from.
alloc	Allocator to be used for the new tree.

◆ flat_multimap() [7/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap ( flat_multimap< K, V, Alloc > && )

defaultnoexcept

Move-construct from another flat_multimap, using a rebound default allocator.

Note: The source flat_multimap is left in a valid but unspecified state afterwards, consistent with standard container move semantics. Callers must clear or overwrite the source if reuse is desired.

◆ flat_multimap() [8/8]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

jh::flat_multimap< K, V, Alloc >::flat_multimap	(	flat_multimap< K, V, Alloc > &&	other,
		const allocator_type &	alloc )

inline

Move-construct from another flat_multimap, using a user-supplied allocator.

Parameters

other	The source flat_multimap to move from.
alloc	Allocator to be used for this flat_multimap.

The source flat_multimap is left in a valid but unspecified state afterwards, consistent with standard container move semantics. Callers must clear or overwrite other if reuse is desired.

Member Function Documentation

◆ bulk_insert()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

template<typename It>

void jh::flat_multimap< K, V, Alloc >::bulk_insert	(	It	first,
		It	last )

inline

Insert a range of elements and restore ordering.

The elements in the range [first, last) are appended to the underlying storage, after which the entire container is stably sorted by key.

Template Parameters

It	Input iterator type.

Parameters

first	Iterator to the first element.
last	Iterator past the last element.

Note: All iterators are invalidated.

◆ clear()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

void jh::flat_multimap< K, V, Alloc >::clear ( )

inlinenoexcept

Remove all elements from the container.

Resets the container to an empty state by clearing the underlying storage. The operation is equivalent to clearing a vector:

The size becomes zero, but the capacity is preserved.
No reallocation occurs.
Under polymorphic allocators (PMR), no element-by-element destruction or resource release takes place; the buffer is simply marked empty.

This gives clear an effectively constant-time cost. Unlike pointer-based tree structures such as those used by the standard multimap, there is no need to traverse and destroy individual nodes; the entire storage is discarded in one step.

Note: All iterators are invalidated.

◆ count()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

std::size_t jh::flat_multimap< K, V, Alloc >::count ( const K & key ) const

inlinenodiscard

Count the number of elements with the specified key.

Parameters

key	Key to count.

Returns: Number of elements equivalent to key.

◆ emplace()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

template<typename... Args>

iterator jh::flat_multimap< K, V, Alloc >::emplace ( Args &&... args )

inline

Insert a key-value pair by constructing it from arbitrary arguments.

This function preserves the usual emplace semantics: the arguments are forwarded into a temporary std::pair<K, V>. The key and mapped value constructed in this temporary object are then forwarded into the internal insertion logic.

If the key already exists in the map, the new element is inserted after all existing equivalents.

Parameters

args	Arguments used to construct a temporary `std::pair<K, V>`.

Returns: Iterator to the inserted element.

Note: All iterators are invalidated except the returned one.

◆ equal_range() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

std::pair< iterator, iterator > jh::flat_multimap< K, V, Alloc >::equal_range ( const K & k )

inline

Return the range of elements equivalent to the given key.

Provides the canonical equal_range semantics for associative containers with multiple equivalent keys:

If an element with the given key exists, returns a pair {lower_bound(key), upper_bound(key)}.
If no such element exists, both iterators in the returned pair equal end().
The returned range is half-open: the first iterator refers to the first element with the key (if present), and the second refers to the element that follows the last element with the key.
Does not modify the container.

Parameters

k	The key to search for.

Returns: A pair of iterators defining the range of matching elements.

◆ equal_range() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

std::pair< const_iterator, const_iterator > jh::flat_multimap< K, V, Alloc >::equal_range ( const K & k ) const

inlinenodiscard

Return the range of elements equivalent to the given key (const overload).

Behaves identically to the non-const version but returns a pair of const_iterator.

Parameters

k	The key to search for.

Returns: A pair of const iterators defining the range of matching elements.

◆ erase() [1/5]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

size_t jh::flat_multimap< K, V, Alloc >::erase ( const K & k )

inline

Erase all elements whose key compares equal to the given key.

Searches for all elements with key equivalent to k and removes them from the container.

If at least one matching key exists, all such elements are removed, and the number of removed elements is returned. All iterators are invalidated.
If no matching key exists, the container is left unmodified and no iterators are invalidated.

Parameters

k	The key of the element to remove.

Returns: The number of elements removed.

◆ erase() [2/5]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

iterator jh::flat_multimap< K, V, Alloc >::erase	(	const_iterator	first,
		const_iterator	last )

inline

Erase a range of elements.

Removes all elements in the half-open range [first, last) by delegating to the non-const overload erase(iterator, iterator). The behavior, iterator invalidation rules, and returned iterator semantics exactly match those of the non-const overload.

Parameters

first	Const iterator referring to the first element to erase.
last	Const iterator referring to one past the last element to erase.

Returns: An iterator referring to the logical successor of the last erased element, or end() if no such element exists.

Exceptions

std::logic_error If last precedes first.

◆ erase() [3/5]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

iterator jh::flat_multimap< K, V, Alloc >::erase ( const_iterator pos )

inline

Erase the element referenced by the given const iterator.

Removes the element pointed to by pos by delegating to the non-const overload erase(iterator). The behavior, iterator invalidation rules, and returned iterator semantics exactly match those of erase(iterator).

If pos equals end(), no removal occurs and pos is returned unchanged.

Parameters

pos	Const iterator referring to the element to erase.

Returns: An iterator as the logical successor of the erased element, or end() if no successor exists.

◆ erase() [4/5]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

iterator jh::flat_multimap< K, V, Alloc >::erase	(	iterator	first,
		iterator	last )

inline

Erase a range of elements.

Removes all elements in the half-open range [first, last) and returns an iterator to the logical successor of the last erased element.
The range [first, last) must be valid. In particular, last must not precede first. If this condition is violated, a std::logic_error is thrown.
If first == last, no elements are removed and first is returned.
If first == end(), no removal is performed and end() is returned. This is only considered valid when last == end().

Parameters

first	Iterator referring to the first element to erase.
last	Iterator referring to one past the last element to erase.

Returns: An iterator referring to the logical successor of the last erased element, or end() if no such element exists.

Exceptions

std::logic_error If last precedes first.

◆ erase() [5/5]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

iterator jh::flat_multimap< K, V, Alloc >::erase ( iterator pos )

inline

Erase the element referenced by the given iterator.

Removes the element pointed to by pos and returns an iterator to its logical successor. If pos refers to end(), no action is performed and pos is returned unchanged.

Parameters

pos	Iterator referring to the element to erase.

Returns: An iterator as the logical successor of the erased element, or end() if no successor exists.

◆ find() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

iterator jh::flat_multimap< K, V, Alloc >::find ( const K & k )

inline

Locate the first element with the specified key.

If multiple elements with the same key exist, returns an iterator to the first such element. If no element exists, returns end().

Parameters

k	The key to search for.

Returns: Iterator to the matching element, or end() if not found.

◆ find() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

const_iterator jh::flat_multimap< K, V, Alloc >::find ( const K & k ) const

inline

Locate the first element with the specified key (const overload).

Behaves identically to the non-const version but returns a const_iterator.

Parameters

k	The key to search for.

Returns: Const iterator to the matching element, or end() if not found.

◆ insert()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

template<typename P>

iterator jh::flat_multimap< K, V, Alloc >::insert ( P && p )

inline

Insert a key-value pair into the map.

This overload generalizes the traditional std::pair<K, V>-based insertion interface. Instead of requiring a value_type object, any 2-element tuple-like value is accepted as long as:

get<0>(p) has type K (after remove_cvref)
get<1>(p) has type V (after remove_cvref)

This reflects the actual insertion semantics: the container consumes the key and mapped value directly. Any tuple-like pair (including std::pair, std::tuple, proxy references, and structured-binding-compatible types) is therefore permitted if its element types match exactly.
If the key already exists in the map, the new element is inserted after all existing equivalents.

Template Parameters

P	The tuple-like type providing key and mapped value.

Parameters

p	A tuple-like value providing key and mapped value.

Returns: Iterator to the inserted element.

Note: All iterators are invalidated except the returned one.

◆ reserve()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

void jh::flat_multimap< K, V, Alloc >::reserve ( std::size_t n )

inlinenoexcept

Reserve space for at least n elements.

Requests that the underlying storage grow its capacity to at least n elements. This operation does not change the size of the container or alter any existing node indices.

Calling reserve with a value smaller than the current size is no-op, according to ISO C++11+ standards for standard containers.

With polymorphic allocators (PMR), reserve typically has minimal overhead, as the resource may enlarge the buffer without a full reallocation.

Parameters

n	Minimum capacity to reserve.

Note: This operation may invalidate all iterators if reallocation occurs.

◆ shrink_to_fit()

template<typename K, typename V, typename Alloc = std::allocator<std::pair<K, V>>>

void jh::flat_multimap< K, V, Alloc >::shrink_to_fit ( )

inlinenoexcept

Request that the container reduce its capacity.

Issues a non-binding request to the underlying storage to reduce its capacity. The behavior matches that of std::vector::shrink_to_fit:

The operation may reduce capacity, but is not required to do so.
There is no guarantee that the resulting capacity equals the size.
Under polymorphic allocators (PMR), the resource may keep the existing buffer unchanged.
Because iterators reference elements by index, not pointer, this operation never invalidates iterators.

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

include/jh/core/flat_multimap.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ allocator_type

Constructor & Destructor Documentation

◆ flat_multimap() [1/8]

◆ flat_multimap() [2/8]

◆ flat_multimap() [3/8]

◆ flat_multimap() [4/8]

◆ flat_multimap() [5/8]

◆ flat_multimap() [6/8]

◆ flat_multimap() [7/8]

◆ flat_multimap() [8/8]

Member Function Documentation

◆ bulk_insert()

◆ clear()

◆ count()

◆ emplace()

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/5]

◆ erase() [2/5]

◆ erase() [3/5]

◆ erase() [4/5]

◆ erase() [5/5]

◆ find() [1/2]

◆ find() [2/2]

◆ insert()

◆ reserve()

◆ shrink_to_fit()