#include <userver/utils/slot_map.hpp>

Detailed Description

template<typename T, template< typename... > typename Container = std::deque>
class utils::SlotMap< T, Container >

A minimalistic slot-map container adaptor.

Each slot holds either a live value of type T or a free-list node. Erased slots are recycled so that emplace reuses them before allocating new storage.

Guarantees:

operator[](std::size_t) is O(1);
emplace and insert are amortized O(1) (assuming that Container provides this guarantee);
erase is O(1);
size() and empty() are O(1);
iterators returned by AliveItems() ARE invalidated by emplace, insert, insert_range, and erase, regardless of the underlying Container.

If Container is std::deque or another reference-stable container, then inserted elements have reference stability; otherwise elements may move around on emplace and insert*, and T should be movable.

Container template is instantiated with an internal value type; the resulting type must:

be a std::ranges::forward_range and std::ranges::sized_range;
support operator[](std::size_t) with computational complexity O(1);
support emplace_back, forwarding arbitrary Args&&... to the value;
support std::ranges::size with computational complexity O(1).

For example, std::deque, std::vector, boost::small_vector satisfy those requirements.

Note: Not thread-safe.

Definition at line 81 of file slot_map.hpp.

Classes
struct	InsertionResult
	Result of an `emplace` or `insert` call. More...

Public Member Functions
	SlotMap ()=default
	Constructs an empty SlotMap.

template<std::input_iterator It, std::sentinel_for< It > Sentinel>
	SlotMap (It first, Sentinel last)
	Constructs a SlotMap from the elements in `[first, last)`.

	SlotMap (const SlotMap &)=default

SlotMap &	operator= (const SlotMap &)=default

	SlotMap (SlotMap &&) noexcept=default

SlotMap &	operator= (SlotMap &&) noexcept=default

template<typename... Args>
InsertionResult	emplace (Args &&... args)
	Constructs a new element in-place and returns a reference to it and its stable index.

InsertionResult	insert (const T &value)
	Inserts a copy of value and returns a reference to it and its stable index.

InsertionResult	insert (T &&value)
	Inserts value by move and returns a reference to it and its stable index.

template<std::ranges::input_range Range>
void	insert_range (Range &&range)
	Inserts all elements from range.

std::size_t	size () const noexcept
	Returns the number of live elements.

bool	empty () const noexcept
	Returns true if there are no live elements.

std::size_t	capacity () const noexcept
	Returns the total number of allocated slots (live + free).

void	reserve (std::size_t capacity)
	Calls `reserve` on the underlying container.

T &	operator[] (std::size_t index) noexcept
	Returns a reference to the live element at index.

const T &	operator[] (std::size_t index) const noexcept
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

std::size_t	erase (std::size_t index)
	Destroys the element at index and recycles the slot.

std::ranges::forward_range auto	AliveItems () noexcept
	Returns a view over live (non-erased) elements, yielding `T&` references.

std::ranges::forward_range auto	AliveItems () const noexcept
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Constructor & Destructor Documentation

◆ SlotMap()

template<typename T, template< typename... > typename Container = std::deque>

template<std::input_iterator It, std::sentinel_for< It > Sentinel>

utils::SlotMap< T, Container >::SlotMap	(	It	first,
		Sentinel	last )

inline

Constructs a SlotMap from the elements in [first, last).

Definition at line 102 of file slot_map.hpp.

Member Function Documentation

◆ AliveItems() [1/2]

template<typename T, template< typename... > typename Container = std::deque>

std::ranges::forward_range auto utils::SlotMap< T, Container >::AliveItems ( ) const

inlinenodiscardnoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 236 of file slot_map.hpp.

◆ AliveItems() [2/2]

template<typename T, template< typename... > typename Container = std::deque>

std::ranges::forward_range auto utils::SlotMap< T, Container >::AliveItems ( )

inlinenodiscardnoexcept

Returns a view over live (non-erased) elements, yielding T& references.

Warning: Iterators of the returned view are invalidated by emplace, insert, insert_range, and erase. References to elements remain valid.

Definition at line 231 of file slot_map.hpp.

◆ capacity()

template<typename T, template< typename... > typename Container = std::deque>

std::size_t utils::SlotMap< T, Container >::capacity ( ) const

inlinenodiscardnoexcept

Returns the total number of allocated slots (live + free).

This is the size of the backing storage. It never shrinks.

Definition at line 175 of file slot_map.hpp.

◆ emplace()

template<typename T, template< typename... > typename Container = std::deque>

template<typename... Args>

InsertionResult utils::SlotMap< T, Container >::emplace ( Args &&... args )

inline

Constructs a new element in-place and returns a reference to it and its stable index.

If there are free (erased) slots, one is reused; otherwise new storage is allocated.

Note: Invalidates all iterators returned by AliveItems(). Does not invalidate references to existing elements if the underlying container supports it, e.g. std::deque.

Definition at line 121 of file slot_map.hpp.

◆ empty()

template<typename T, template< typename... > typename Container = std::deque>

bool utils::SlotMap< T, Container >::empty ( ) const

inlinenodiscardnoexcept

Returns true if there are no live elements.

Definition at line 170 of file slot_map.hpp.

◆ erase()

template<typename T, template< typename... > typename Container = std::deque>

std::size_t utils::SlotMap< T, Container >::erase ( std::size_t index )

inline

Destroys the element at index and recycles the slot.

If the slot at index is already free (was previously erased), this is a no-op.

Returns: the number of erased elements: 1 if a live element was erased, 0 if the slot was already free.

Note: Invalidates all iterators returned by AliveItems(). Does NOT invalidate references to other live elements.

Definition at line 217 of file slot_map.hpp.

◆ insert() [1/2]

template<typename T, template< typename... > typename Container = std::deque>

InsertionResult utils::SlotMap< T, Container >::insert ( const T & value )

inline

Inserts a copy of value and returns a reference to it and its stable index.

Note: Invalidates all iterators returned by AliveItems(). Does not invalidate references to existing elements if the underlying container supports it, e.g. std::deque.

Definition at line 143 of file slot_map.hpp.

◆ insert() [2/2]

template<typename T, template< typename... > typename Container = std::deque>

InsertionResult utils::SlotMap< T, Container >::insert ( T && value )

inline

Inserts value by move and returns a reference to it and its stable index.

Note: Invalidates all iterators returned by AliveItems(). Does not invalidate references to existing elements if the underlying container supports it, e.g. std::deque.

Definition at line 149 of file slot_map.hpp.

◆ insert_range()

template<typename T, template< typename... > typename Container = std::deque>

template<std::ranges::input_range Range>

void utils::SlotMap< T, Container >::insert_range ( Range && range )

inline

Inserts all elements from range.

Provides a basic exception guarantee: if an element's constructor throws, all previously inserted elements remain valid and the map is left in a consistent state.

Note: Invalidates all iterators returned by AliveItems(). Does not invalidate references to existing elements if the underlying container supports it, e.g. std::deque.

Definition at line 160 of file slot_map.hpp.

◆ operator[]() [1/2]

template<typename T, template< typename... > typename Container = std::deque>

const T & utils::SlotMap< T, Container >::operator[] ( std::size_t index ) const

inlinenoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 201 of file slot_map.hpp.

◆ operator[]() [2/2]

template<typename T, template< typename... > typename Container = std::deque>

T & utils::SlotMap< T, Container >::operator[] ( std::size_t index )

inlinenoexcept

Returns a reference to the live element at index.

Precondition: the slot at index holds a live element (was not erased).

Definition at line 193 of file slot_map.hpp.

◆ reserve()

template<typename T, template< typename... > typename Container = std::deque>

void utils::SlotMap< T, Container >::reserve ( std::size_t capacity )

inline

Calls reserve on the underlying container.

Definition at line 184 of file slot_map.hpp.

◆ size()

template<typename T, template< typename... > typename Container = std::deque>

std::size_t utils::SlotMap< T, Container >::size ( ) const

inlinenodiscardnoexcept

Returns the number of live elements.

Definition at line 167 of file slot_map.hpp.

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

userver/utils/slot_map.hpp

Detailed Description

Classes

Public Member Functions

Constructor & Destructor Documentation

◆ SlotMap()

Member Function Documentation

◆ AliveItems() [1/2]

◆ AliveItems() [2/2]

◆ capacity()

◆ emplace()

◆ empty()

◆ erase()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_range()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ reserve()

◆ size()