pw::IntrusiveSet< T > Class Template Reference

#include <intrusive_set.h>

Classes
class	const_iterator
class	iterator

Public Types
using	Item = typename Tree::Item
	IntrusiveSet items must derive from Item.
using	key_type = T
using	value_type = T
using	size_type = std::size_t
using	difference_type = std::ptrdiff_t
using	key_compare = Compare
using	value_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	IntrusiveSet ()
	Constructs an empty set of items.
template<typename Comparator >
constexpr	IntrusiveSet (Comparator &&compare)
template<typename Iterator , typename... Functors>
	IntrusiveSet (Iterator first, Iterator last, Functors &&... functors)
template<typename... Functors>
	IntrusiveSet (std::initializer_list< T * > items, Functors &&... functors)
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 set has zero items or not.
size_t	size () const
	Returns the number of items in the set.
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 (iterator pos)
iterator	erase (iterator first, iterator last)
size_t	erase (const T &item)
void	swap (IntrusiveSet< T > &other)
	Exchanges this set's items with the other set's items.
template<typename MapType >
void	merge (MapType &other)
size_t	count (const T &item) const
iterator	find (const T &item)
const_iterator	find (const T &item) const
std::pair< iterator, iterator >	equal_range (const T &item)
std::pair< const_iterator, const_iterator >	equal_range (const T &item) const
iterator	lower_bound (const T &item)
const_iterator	lower_bound (const T &item) const
iterator	upper_bound (const T &item)
const_iterator	upper_bound (const T &item) const

Friends
template<typename >
class	IntrusiveMultiSet

Detailed Description

template<typename T>
class pw::IntrusiveSet< T >

A std::set<Key, Compare>-like class that uses intrusive items as keys.

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

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

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

Template Parameters

T	Type of data stored in the set.

Constructor & Destructor Documentation

IntrusiveSet() [1/3]

template<typename T >

template<typename Comparator >

constexpr pw::IntrusiveSet< T >::IntrusiveSet ( Comparator &&  compare )

inlineexplicitconstexpr

Constructs an empty set 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(T, T) that is used to order items.

IntrusiveSet() [2/3]

template<typename T >

template<typename Iterator , typename... Functors>

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

inline

Constructs an IntrusiveSet 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*>).

IntrusiveSet() [3/3]

template<typename T >

template<typename... Functors>

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

inline

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

Member Function Documentation

clear()

template<typename T >

void pw::IntrusiveSet< T >::clear ( )

inline

Removes all items from the set and leaves it empty.

The items themselves are not destructed.

count()

template<typename T >

size_t pw::IntrusiveSet< T >::count ( const T &  item ) const

inline

Returns the number of equivalent items in the set.

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

equal_range()

template<typename T >

std::pair< iterator, iterator > pw::IntrusiveSet< T >::equal_range ( const T &  item )

inline

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

erase()

template<typename T >

iterator pw::IntrusiveSet< T >::erase ( iterator  pos )

inline

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

The items themselves are not destructed.

find()

template<typename T >

iterator pw::IntrusiveSet< T >::find ( const T &  item )

inline

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

insert()

template<typename T >

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

inline

Attempts to add the given item to the set.

The item will be added if the set does not already contain an equivalent item.

Returns

A pointer to the inserted item and true, or a pointer to the equivalent item and false.

lower_bound()

template<typename T >

iterator pw::IntrusiveSet< T >::lower_bound ( const T &  item )

inline

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

max_size()

template<typename T >

constexpr size_t pw::IntrusiveSet< T >::max_size ( ) const

inlineconstexprnoexcept

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

merge()

template<typename T >

template<typename MapType >

void pw::IntrusiveSet< T >::merge ( MapType &  other )

inline

Splices items from the other set into this one.

The receiving set's Compare function is used when inserting items.

upper_bound()

template<typename T >

iterator pw::IntrusiveSet< T >::upper_bound ( const T &  item )

inline

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

---

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

• pw_containers/public/pw_containers/intrusive_set.h