pw::IntrusiveMap< Key, T > Class Template Reference

#include <intrusive_map.h>

Classes
class	const_iterator
class	iterator

Public Types
using	Item = typename Tree::Item
using	Pair = typename Tree::Pair
using	key_type = Key
using	mapped_type = std::remove_cv_t< T >
using	value_type = Item
using	size_type = std::size_t
using	difference_type = std::ptrdiff_t
using	key_compare = Compare
using	reference = value_type &
using	const_reference = const value_type &
using	pointer = value_type *
using	const_pointer = const value_type *
using	reverse_iterator = std::reverse_iterator< iterator >
using	const_reverse_iterator = std::reverse_iterator< const_iterator >

Public Member Functions
constexpr	IntrusiveMap ()
	Constructs an empty map of items.
template<typename Comparator >
constexpr	IntrusiveMap (Comparator &&compare)
template<typename Comparator , typename KeyRetriever >
constexpr	IntrusiveMap (Comparator &&compare, KeyRetriever &&get_key)
template<typename Iterator , typename... Functors>
	IntrusiveMap (Iterator first, Iterator last, Functors &&... functors)
template<typename... Functors>
	IntrusiveMap (std::initializer_list< T * > items, Functors &&... functors)
T &	at (const key_type &key)
const T &	at (const key_type &key) const
iterator	begin () noexcept
const_iterator	begin () const noexcept
const_iterator	cbegin () const noexcept
iterator	end () noexcept
const_iterator	end () const noexcept
const_iterator	cend () const noexcept
reverse_iterator	rbegin () noexcept
const_reverse_iterator	rbegin () const noexcept
const_reverse_iterator	crbegin () const noexcept
reverse_iterator	rend () noexcept
const_reverse_iterator	rend () const noexcept
const_reverse_iterator	crend () const noexcept
bool	empty () const noexcept
	Returns whether the map has zero items or not.
size_t	size () const
	Returns the number of items in the map.
constexpr size_t	max_size () const noexcept
void	clear ()
std::pair< iterator, bool >	insert (T &item)
iterator	insert (iterator, T &item)
template<class Iterator >
void	insert (Iterator first, Iterator last)
void	insert (std::initializer_list< T * > ilist)
iterator	erase (T &item)
iterator	erase (iterator pos)
iterator	erase (iterator first, iterator last)
size_t	erase (const key_type &key)
void	swap (IntrusiveMap< Key, T > &other)
	Exchanges this map's items with the other map's items.
template<typename MapType >
void	merge (MapType &other)
	Splices items from the other map into this one.
size_t	count (const key_type &key) const
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
std::pair< iterator, iterator >	equal_range (const key_type &key)
std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
iterator	lower_bound (const key_type &key)
const_iterator	lower_bound (const key_type &key) const
iterator	upper_bound (const key_type &key)
const_iterator	upper_bound (const key_type &key) const

Friends
template<typename , typename >
class	IntrusiveMultiMap

Detailed Description

template<typename Key, typename T>
class pw::IntrusiveMap< Key, T >

A std::map<Key, T, Compare>-like class that uses intrusive items.

Since the map structure is stored in the items themselves, each item must outlive any map it is a part of and must be part of at most one map.

This map requires unique keys. Attempting to add an item with same key as an item already in the map will fail.

• Since items are not allocated by this class, the following methods have no analogue:
  • std::map<T>::operator=
  • std::map<T>::operator[]
  • std::map<T>::get_allocator
  • std::map<T>::insert_or_assign
  • std::map<T>::emplace
  • std::map<T>::emplace_hint
  • std::map<T>::try_emplace
• Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:
  • std::map<T>::(constructor)
  • std::map<T>::insert
• There are no overloads corresponding to the following methods that take r-value references.:
  • std::map<T>::insert
  • std::map<T>::merge
• Since modifying the map modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
  • std::map<T>::insert
  • std::map<T>::erase
• An additional overload of erase is provided that takes a direct reference to an item.
• C++23 methods are not (yet) supported.

Template Parameters

Key	Type to sort items on
T	Type of values stored in the map.

Member Typedef Documentation

Item

template<typename Key , typename T >

using pw::IntrusiveMap< Key, T >::Item = typename Tree::Item

IntrusiveMap items must derive from either Item or Pair. Use Pair to automatically provide storage for a Key. Use Item when the derived type has a key() accessor method or when the map provides a custom GetKey function object.

Constructor & Destructor Documentation

IntrusiveMap() [1/4]

template<typename Key , typename T >

template<typename Comparator >

constexpr pw::IntrusiveMap< Key, T >::IntrusiveMap ( Comparator &&  compare )

inlineexplicitconstexpr

Constructs an empty map of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters

compare

Function with the signature bool(Key, Key) that is used to order items.

IntrusiveMap() [2/4]

template<typename Key , typename T >

template<typename Comparator , typename KeyRetriever >

constexpr pw::IntrusiveMap< Key, T >::IntrusiveMap ( Comparator &&  compare, KeyRetriever &&  get_key  )

inlineconstexpr

Constructs an empty map of items.

Parameters

compare	Function with the signature bool(Key, Key) that is used to order items.
get_key	Function with signature Key(const T&) that returns the value that items are sorted on.

IntrusiveMap() [3/4]

template<typename Key , typename T >

template<typename Iterator , typename... Functors>

pw::IntrusiveMap< Key, T >::IntrusiveMap ( Iterator  first, Iterator  last, Functors &&...  functors  )

inline

Constructs an IntrusiveMap from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

IntrusiveMap() [4/4]

template<typename Key , typename T >

template<typename... Functors>

pw::IntrusiveMap< Key, T >::IntrusiveMap ( std::initializer_list< T * >  items, Functors &&...  functors  )

inlineexplicit

Constructs an IntrusiveMap from a std::initializer_list of pointers to items.

Member Function Documentation

at()

template<typename Key , typename T >

T & pw::IntrusiveMap< Key, T >::at ( const key_type &  key )

inline

Returns a reference to the item associated with the given key.

Precondition

The map must contain an item associated with the key.

clear()

template<typename Key , typename T >

void pw::IntrusiveMap< Key, T >::clear ( )

inline

Removes all items from the map and leaves it empty.

The items themselves are not destructed.

count()

template<typename Key , typename T >

size_t pw::IntrusiveMap< Key, T >::count ( const key_type &  key ) const

inline

Returns the number of items in the map with the given key.

Since the map requires unique keys, this is always 0 or 1.

equal_range()

template<typename Key , typename T >

std::pair< iterator, iterator > pw::IntrusiveMap< Key, T >::equal_range ( const key_type &  key )

inline

Returns a pair of iterators where the first points to the item with the smallest key that is not less than the given key, and the second points to the item with the smallest key that is greater than the given key.

erase()

template<typename Key , typename T >

iterator pw::IntrusiveMap< Key, T >::erase ( T &  item )

inline

Removes an item from the map and returns an iterator to the item after the removed item..

The items themselves are not destructed.

find()

template<typename Key , typename T >

iterator pw::IntrusiveMap< Key, T >::find ( const key_type &  key )

inline

Returns a pointer to an item with the given key, or null if the map does not contain such an item.

insert()

template<typename Key , typename T >

std::pair< iterator, bool > pw::IntrusiveMap< Key, T >::insert ( T &  item )

inline

Attempts to add the given item to the map.

The item will be added if the map does not already contain an item with the given item's key.

Returns

A pointer to the inserted item and true, or a pointer to the existing item with same key and false.

lower_bound()

template<typename Key , typename T >

iterator pw::IntrusiveMap< Key, T >::lower_bound ( const key_type &  key )

inline

Returns an iterator to the item in the map with the smallest key that is greater than or equal to the given key, or end() if the map is empty.

max_size()

template<typename Key , typename T >

constexpr size_t pw::IntrusiveMap< Key, T >::max_size ( ) const

inlineconstexprnoexcept

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

upper_bound()

template<typename Key , typename T >

iterator pw::IntrusiveMap< Key, T >::upper_bound ( const key_type &  key )

inline

Returns an iterator to the item in the map with the smallest key that is strictly greater than the given key, or end() if the map is empty.

---

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

• pw_containers/public/pw_containers/intrusive_map.h