The FlatMultiSet class is a container whose elements are always sorted. More...

#include <qx/core/qx-flatmultiset.h>

Public Types
using	const_iterator = typename Container::const_iterator

using	const_pointer = typename Container::const_pointer

using	const_reference = typename Container::const_reference

using	const_reverse_iterator = typename Container::const_reverse_iterator

using	ConstIterator = const_iterator

using	ConstReverseIterator = const_reverse_iterator

using	difference_type = typename Container::difference_type

using	iterator = const_iterator

using	Iterator = iterator

using	key_type = typename Container::value_type

using	pointer = typename Container::pointer

using	reference = typename Container::reference

using	reverse_iterator = const_reverse_iterator

using	ReverseIterator = reverse_iterator

using	size_type = typename Container::size_type

using	value_type = typename Container::value_type

Public Member Functions
	FlatMultiSet ()=default

template<std::input_iterator InputIterator>
	FlatMultiSet (InputIterator first, InputIterator last)

	FlatMultiSet (std::initializer_list< T > list)

iterator	begin () const

qsizetype	capacity () const

const_iterator	cbegin () const

const_iterator	cend () const

void	clear ()

const_iterator	constBegin () const

const_iterator	constEnd () const

const_iterator	constFind (const T &value) const

const T &	constFirst () const

const T &	constLast () const

const_reverse_iterator	constReverseBegin () const

const_reverse_iterator	constReverseEnd () const

bool	contains (const FlatMultiSet &other) const

bool	contains (const T &value) const

qsizetype	count () const

const_reverse_iterator	crbegin () const

const_reverse_iterator	crend () const

template<typename ... Args>
iterator	emplace (Args &&... args)

template<typename ... Args>
iterator	emplace (const_iterator pos, Args &&... args)

bool	empty () const

iterator	end () const

std::pair< const_iterator, const_iterator >	equal_range (const T &value) const

iterator	erase (const_iterator pos)

const_iterator	find (const T &value) const

const T &	first () const

iterator	insert (const T &value)

iterator	insert (const_iterator pos, const T &value)

bool	isEmpty () const

const T &	last () const

const_iterator	lowerBound (const T &value) const

bool	operator== (const FlatMultiSet &other) const =default

reverse_iterator	rbegin () const

qsizetype	remove (const T &value)

template<typename Predicate > requires flatmultiset_predicate<T, Predicate>
qsizetype	removeIf (Predicate pred)

iterator	rend () const

void	reserve (qsizetype size)

qsizetype	size () const

void	squeeze ()

void	swap (FlatMultiSet &other)

const_iterator	upperBound (const T &value) const

QList< T >	values () const

Detailed Description

template<typename T, typename Compare>
requires std::predicate<Compare, T, T>
class Qx::FlatMultiSet< T, Compare >

Essentially a more Qt aligned version of C++23's std::flat_multiset, backed by a QList.

iterator is an alias for const_iterator since modifying an element in-place could affect ordering.

Iterator invalidation rules are the same as for QList.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::const_iterator = typename Container::const_iterator

The container's regular iterator type, an alias for QList<T>::const_iterator.

◆ const_pointer

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::const_pointer = typename Container::const_pointer

Provided for STL compatibility.

◆ const_reference

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::const_reference = typename Container::const_reference

Provided for STL compatibility.

◆ const_reverse_iterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::const_reverse_iterator = typename Container::const_reverse_iterator

The container's reverse iterator type, an alias for QList<T>::const_reverse_iterator.

◆ ConstIterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::ConstIterator = const_iterator

Qt-style synonym for FlatMultiSet::const_iterator.

◆ ConstReverseIterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::ConstReverseIterator = const_reverse_iterator

Qt-style synonym for const_reverse_iterator.

◆ difference_type

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::difference_type = typename Container::difference_type

Provided for STL compatibility.

◆ iterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::iterator = const_iterator

Typedef for const_iterator.

◆ Iterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::Iterator = iterator

Qt-style synonym for FlatMultiSet::iterator.

◆ key_type

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::key_type = typename Container::value_type

Typedef for T.

◆ pointer

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::pointer = typename Container::pointer

Provided for STL compatibility.

◆ reference

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::reference = typename Container::reference

Provided for STL compatibility.

◆ reverse_iterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::reverse_iterator = const_reverse_iterator

Typedef for const_reverse_iterator.

◆ ReverseIterator

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::ReverseIterator = reverse_iterator

Qt-style synonym for reverse_iterator.

◆ size_type

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::size_type = typename Container::size_type

Typedef for the container's size_type, usually std::size_t.

◆ value_type

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::value_type = typename Container::value_type

Typedef for T.

Constructor & Destructor Documentation

◆ FlatMultiSet() [1/3]

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::FlatMultiSet ( )

default

Creates an empty flat-multiset.

See also: clear().

◆ FlatMultiSet() [2/3]

template<typename T , typename Compare >

Qx::FlatMultiSet< T, Compare >::FlatMultiSet ( std::initializer_list< T > list )

inline

Creates a FlatMultiSet with a copy of each of the elements in the initializer list list.

◆ FlatMultiSet() [3/3]

template<typename T , typename Compare >

template<std::input_iterator InputIterator>

Qx::FlatMultiSet< T, Compare >::FlatMultiSet	(	InputIterator	first,
		InputIterator	last )

inline

Creates a FlatMultiSet with a copy of each of the elements between [first, last).

Member Function Documentation

◆ begin()

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::begin ( ) const

inline

Same as constBegin().

◆ capacity()

template<typename T , typename Compare >

qsizetype Qx::FlatMultiSet< T, Compare >::capacity ( ) const

inline

Returns the maximum number of items that can be stored in the flat-multiset without forcing a reallocation.

The sole purpose of this function is to provide a means of fine tuning FlatMultiSet's memory usage. In general, you will rarely ever need to call this function. If you want to know how many items are in the flat-multiset, call size().

Note: a statically allocated flat-multiset will report a capacity of 0, even if it's not empty.

See also: reserve() and squeeze().

◆ cbegin()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::cbegin ( ) const

inline

Same as constBegin().

◆ cend()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::cend ( ) const

inline

Same as constEnd().

◆ clear()

template<typename T , typename Compare >

void Qx::FlatMultiSet< T, Compare >::clear ( )

inline

Removes all items from the FlatMultiSet.

See also: remove().

◆ constBegin()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::constBegin ( ) const

inline

Returns an STL-style iterator pointing to the first item in the FlatMultiSet.

See also: constEnd().

◆ constEnd()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::constEnd ( ) const

inline

Returns an STL-style iterator pointing to the imaginary item after the last item in the FlatMultiSet.

See also: constBegin().

◆ constFind()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::constFind ( const T & value ) const

inline

Returns an iterator positioned at the item value in the set. If the set contains multiple items of value, it is unspecified to which the iterator points.

If the set contains no item value, the function returns constEnd().

◆ constFirst()

template<typename T , typename Compare >

const T & Qx::FlatMultiSet< T, Compare >::constFirst ( ) const

inline

Returns a reference to the first item in the set. This function assumes that the set isn't empty.

See also: last() and isEmpty().

◆ constLast()

template<typename T , typename Compare >

const T & Qx::FlatMultiSet< T, Compare >::constLast ( ) const

inline

Returns a reference to the last item in the set. This function assumes that the set isn't empty.

See also: first() and isEmpty().

◆ constReverseBegin()

template<typename T , typename Compare >

const_reverse_iterator Qx::FlatMultiSet< T, Compare >::constReverseBegin ( ) const

inline

Returns an STL-style iterator pointing to the last item in the FlatMultiSet.

See also: constReverseEnd().

◆ constReverseEnd()

template<typename T , typename Compare >

const_reverse_iterator Qx::FlatMultiSet< T, Compare >::constReverseEnd ( ) const

inline

Returns an STL-style iterator pointing to the imaginary item after the first item in the FlatMultiSet.

See also: constReverseBegin().

◆ contains() [1/2]

template<typename T , typename Compare >

bool Qx::FlatMultiSet< T, Compare >::contains ( const FlatMultiSet< T, Compare > & other ) const

inline

Returns true if the FlatMultiSet contains all of the items in other; otherwise, returns false.

See also: count().

◆ contains() [2/2]

template<typename T , typename Compare >

bool Qx::FlatMultiSet< T, Compare >::contains ( const T & value ) const

inline

Returns true if the FlatMultiSet contains value; otherwise, returns false.

See also: count().

◆ count()

template<typename T , typename Compare >

qsizetype Qx::FlatMultiSet< T, Compare >::count ( ) const

inline

Same as size().

◆ crbegin()

template<typename T , typename Compare >

const_reverse_iterator Qx::FlatMultiSet< T, Compare >::crbegin ( ) const

inline

Same as constReverseBegin().

◆ crend()

template<typename T , typename Compare >

const_reverse_iterator Qx::FlatMultiSet< T, Compare >::crend ( ) const

inline

Same as constReverseEnd().

◆ emplace() [1/2]

template<typename T , typename Compare >

template<typename ... Args>

iterator Qx::FlatMultiSet< T, Compare >::emplace ( Args &&... args )

inline

Inserts an item, constructed in-place using the arguments args, into the FlatMultiSet.

If the container has items with the same value, inserts at the upper bound of that range.

Returns an iterator pointing to the new item.

◆ emplace() [2/2]

template<typename T , typename Compare >

template<typename ... Args>

iterator Qx::FlatMultiSet< T, Compare >::emplace	(	const_iterator	pos,
		Args &&...	args )

inline

Inserts an item, constructed in-place using the arguments args, into the FlatMultiSet, using pos as a hint as to where the item should be inserted. If the hint is correct, the item is inserted directly to that position; otherwise, this function is equivalent to insert(const T& value), which first has to search for the correct position.

Returns an iterator pointing to the new element.

◆ empty()

template<typename T , typename Compare >

bool Qx::FlatMultiSet< T, Compare >::empty ( ) const

inline

Same as isEmpty().

◆ end()

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::end ( ) const

inline

Same as constEnd().

◆ equal_range()

template<typename T , typename Compare >

std::pair< const_iterator, const_iterator > Qx::FlatMultiSet< T, Compare >::equal_range ( const T & value ) const

inline

Returns a pair of iterators delimiting the range of values [first, second), that are stored with value.

◆ erase()

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::erase ( const_iterator pos )

inline

Removes the item pointed to by the iterator pos from the FlatMultiSet, and returns an iterator to the next item in the set.

Note: The iterator pos must be valid and dereferenceable.

See also: remove().

◆ find()

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::find ( const T & value ) const

inline

Same as constFind().

◆ first()

template<typename T , typename Compare >

const T & Qx::FlatMultiSet< T, Compare >::first ( ) const

inline

Same as constFirst().

◆ insert() [1/2]

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::insert ( const T & value )

inline

Inserts an item with the value value into the FlatMultiSet.

If the container has items with the same value, inserts at the upper bound of that range.

Returns an iterator pointing to the new item.

◆ insert() [2/2]

template<typename T , typename Compare >

iterator Qx::FlatMultiSet< T, Compare >::insert	(	const_iterator	pos,
		const T &	value )

inline

Inserts an item with the value value into the FlatMultiSet, using pos as a hint as to where the item should be inserted. If the hint is correct, the item is inserted directly to that position; otherwise, this function is equivalent to insert(const T& value), which first has to search for the correct position.

Returns an iterator pointing to the new element.

◆ isEmpty()

template<typename T , typename Compare >

bool Qx::FlatMultiSet< T, Compare >::isEmpty ( ) const

inline

Returns true if the FlatMultiSet contains no items; otherwise, returns false.

See also: size().

◆ last()

template<typename T , typename Compare >

const T & Qx::FlatMultiSet< T, Compare >::last ( ) const

inline

Same as constLast().

◆ lowerBound()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::lowerBound ( const T & value ) const

inline

Returns an iterator pointing to the first item with value value in the FlatMultiSet. If the set contains no item with value value, the function returns an iterator to the nearest item with a greater value, or constEnd() if there is none.

See also: upperBound() and find().

◆ operator==()

template<typename T , typename Compare >

bool Qx::FlatMultiSet< T, Compare >::operator== ( const FlatMultiSet< T, Compare > & other ) const

inlinedefault

Returns true if other is equal to this FlatMultiSet; otherwise, returns false.

Two FlatMultiSet's are considered equal if they contain the same items, and only the same items.

This function requires T to implement operator==().

◆ rbegin()

template<typename T , typename Compare >

reverse_iterator Qx::FlatMultiSet< T, Compare >::rbegin ( ) const

inline

Same as constReverseBegin().

◆ remove()

template<typename T , typename Compare >

size_type Qx::FlatMultiSet< T, Compare >::remove ( const T & value )

inline

Removes all items with the value value from the FlatMultiSet and returns the number of items removed, if any.

See also: clear().

◆ removeIf()

template<typename T , typename Compare >

template<typename Predicate >
requires flatmultiset_predicate<T, Predicate>

qsizetype Qx::FlatMultiSet< T, Compare >::removeIf ( Predicate pred )

inline

Removes all items for which the predicate pred returns true from the FlatMultiSet.

Returns the number of elements removed, if any.

See also: clear() and.

◆ rend()

template<typename T , typename Compare >

reverse_iterator Qx::FlatMultiSet< T, Compare >::rend ( ) const

inline

Same as constReverseEnd().

◆ reserve()

template<typename T , typename Compare >

void Qx::FlatMultiSet< T, Compare >::reserve ( qsizetype size )

inline

Attempts to allocate memory for at least size elements.

If you know in advance how large the flat-multiset will be, you should call this function to prevent reallocations and memory fragmentation. If you resize the flat-multiset often, you are also likely to get better performance.

If in doubt about how much space shall be needed, it is usually better to use an upper bound as size, or a high estimate of the most likely size, if a strict upper bound would be much bigger than this. If size is an underestimate, the flat-multiset will grow as needed once the reserved size is exceeded, which may lead to a larger allocation than your best overestimate would have and will slow the operation that triggers it.

Warning: reserve() reserves memory but does not change the size of the flat-multiset. Accessing data beyond the current end of the flat-multiset is undefined behavior.

See also: capacity() and squeeze().

◆ size()

template<typename T , typename Compare >

qsizetype Qx::FlatMultiSet< T, Compare >::size ( ) const

inline

Returns the number of items in the FlatMultiSet.

See also: isEmpty() and count().

◆ squeeze()

template<typename T , typename Compare >

void Qx::FlatMultiSet< T, Compare >::squeeze ( )

inline

Releases any memory not required to store the items.

The sole purpose of this function is to provide a means of fine tuning FlatMultiSet's memory usage. In general, you will rarely ever need to call this function.

See also: reserve() and capacity().

◆ swap()

template<typename T , typename Compare >

void Qx::FlatMultiSet< T, Compare >::swap ( FlatMultiSet< T, Compare > & other )

inline

Swaps FlatMultiSet other with this FlatMultiSet. This operation is very fast and never fails.

◆ upperBound()

template<typename T , typename Compare >

const_iterator Qx::FlatMultiSet< T, Compare >::upperBound ( const T & value ) const

inline

Returns an iterator pointing to the item that immediately follows the last item with value value in the FlatMultiSet. If the set contains no item with value value, the function returns an iterator to the nearest item with a greater value, or constEnd() if there is none.

See also: lowerBound() and find().

◆ values()

template<typename T , typename Compare >

QList< T > Qx::FlatMultiSet< T, Compare >::values ( ) const

inline

Returns a list containing all of the values in the FlatMultiSet in order.

This function creates a new list, in linear time. The time and memory use that entails can be avoided by iterating from begin() to end().

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

qx-flatmultiset.h
qx-flatmultiset.dox

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ ConstIterator

◆ ConstReverseIterator

◆ difference_type

◆ iterator

◆ Iterator

◆ key_type

◆ pointer

◆ reference

◆ reverse_iterator

◆ ReverseIterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ FlatMultiSet() [1/3]

◆ FlatMultiSet() [2/3]

◆ FlatMultiSet() [3/3]

Member Function Documentation

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ constBegin()

◆ constEnd()

◆ constFind()

◆ constFirst()

◆ constLast()

◆ constReverseBegin()

◆ constReverseEnd()

◆ contains() [1/2]

◆ contains() [2/2]

◆ count()

◆ crbegin()

◆ crend()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ empty()

◆ end()

◆ equal_range()

◆ erase()

◆ find()

◆ first()

◆ insert() [1/2]

◆ insert() [2/2]

◆ isEmpty()

◆ last()

◆ lowerBound()

◆ operator==()

◆ rbegin()

◆ remove()

◆ removeIf()

◆ rend()

◆ reserve()

◆ size()

◆ squeeze()

◆ swap()

◆ upperBound()

◆ values()