An adapter class for std::vector that acts like an ordered set and stores its data in the underlying vector in order. More...

#include <TinySet.h>

Public Types
Types
using	UnderlyingContainer = std::vector< T >
	The type of the underlying container with linear memory.

using	value_type = T
	What types this container stores.

using	reference = T &
	Reference to a value_type.

using	const_reference = const T &
	Const reference to a value type.

using	iterator = typename std::vector< T >::iterator
	Iterator type.

using	const_iterator = typename std::vector< T >::const_iterator
	Const iterator type.

Public Member Functions
Constructors
	TinySet ()
	Default constructor.

	TinySet (std::initializer_list< T > list)
	Initializer-list constructor.

Modification
void	clear ()
	Empties the set.

template<typename It >
void	erase (It a)
	Erases an element marked by a position in the set.

void	reserve (std::size_t size)
	Reserves space in memory.

iterator	find (const T &a)
	Finds an element in the set.

void	insert (T a)
	Inserts an element into the set. More...

template<typename It >
void	insert (It a, const It &b)
	Inserts all elements contained in a range. More...

void	emplace (T a)
	Insert an element. More...

TinySet &	operator= (std::initializer_list< T > init)
	Assign from an initializer list. More...

Information
unsigned	count (T a) const
	Count the number of occurrences of an element.

bool	empty () const
	Returns whether the set is empty.

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

Element access
const_reference	front () const
	Yields a const reference to the first element in the set.

const_reference	back () const
	Yields a const reference to the last element in the set.

const_reference	at (std::size_t position) const
	Yields a const reference to an element in the set.

Iterators
iterator	begin ()
	Yields a begin iterator.

iterator	end ()
	Yields an end iterator.

const_iterator	begin () const
	Yields a begin const iterator.

const_iterator	end () const
	Yields an end const iterator.

const_iterator	cbegin () const
	Yields a begin const iterator.

const_iterator	cend () const
	Yields an end const iterator.

Operators
bool	operator== (const TinySet &other) const
	Lexicographically compare two sets.

bool	operator!= (const TinySet &other) const
	Invertes `operator==`.

Static Public Member Functions
Static functions
static iterator	find (std::vector< T > &set, const T &a)
	Emplaces an element in an ordered vector if the element is not contained. More...

static const_iterator	find (const std::vector< T > &set, const T &a)
	Emplaces an element in an ordered vector if the element is not contained. More...

static void	checked_insert (std::vector< T > &set, T a)
	Emplaces an element in an ordered vector if the element is not contained. More...

template<typename... Args>
static void	checked_emplace (std::vector< T > &set, Args &&...args)
	Emplaces an element in an ordered vector if the element is not contained. More...

static bool	binary_search (const std::vector< T > &set, const T &value)
	Binary search for a value in an ordered set. More...

Data Fields
State
UnderlyingContainer	data
	The owned underlying linear memory container.

Detailed Description

template<typename T>
struct Scine::Molassembler::Temple::TinySet< T >

An adapter class for std::vector that acts like an ordered set and stores its data in the underlying vector in order.

Why? It's a lot simpler / smaller than set and seems to be faster for very small amounts of data. Break-even with an unordered_set for finding a value is at around N = 200 for numeric types, although I certainly do not trust the benchmark much.

Template Parameters

The	set value type

Member Function Documentation

template<typename T >

static bool Scine::Molassembler::Temple::TinySet< T >::binary_search	(	const std::vector< T > &	set,
		const T &	value
	)

inlinestatic

Binary search for a value in an ordered set.

Parameters

set	Set to search
value	Value to look for

Returns: Whether the value was found

template<typename T >

template<typename... Args>

static void Scine::Molassembler::Temple::TinySet< T >::checked_emplace	(	std::vector< T > &	set,
		Args &&...	args
	)

inlinestatic

Emplaces an element in an ordered vector if the element is not contained.

Note: This does inplace-construct the element at the back of the vector, then searches for an equal element in the ordered part of the vector. If the element is found, the newly-constructed element is popped back off. Otherwise, it is rotated to its position. This implies that this function may trigger reallocation of the vector even though the element is already part of the vector.

Parameters

set	An ordered vector to add the element to

Template Parameters

Args	parameter pack to forward to T's constructor

Parameters

args	Arguments to forward to T's constructor

template<typename T >

static void Scine::Molassembler::Temple::TinySet< T >::checked_insert	(	std::vector< T > &	set,
		T	a
	)

inlinestatic

Emplaces an element in an ordered vector if the element is not contained.

Note: This does inplace-construct the element at the back of the vector, then searches for an equal element in the ordered part of the vector. If the element is found, the newly-constructed element is popped back off. Otherwise, it is rotated to its position. This implies that this function may trigger reallocation of the vector even though the element is already part of the vector.

Parameters

set	An ordered vector to add the element to

Template Parameters

Args	parameter pack to forward to T's constructor

Parameters

args	Arguments to forward to T's constructor

template<typename T >

void Scine::Molassembler::Temple::TinySet< T >::emplace ( T a )

inline

Insert an element.

Note: This does not actually in-place construct. This is a copy and move.

Warning: Does not check if the element already exists

template<typename T >

static iterator Scine::Molassembler::Temple::TinySet< T >::find	(	std::vector< T > &	set,
		const T &	a
	)

inlinestatic

Emplaces an element in an ordered vector if the element is not contained.

Note: This does inplace-construct the element at the back of the vector, then searches for an equal element in the ordered part of the vector. If the element is found, the newly-constructed element is popped back off. Otherwise, it is rotated to its position. This implies that this function may trigger reallocation of the vector even though the element is already part of the vector.

Parameters

set	An ordered vector to add the element to

Template Parameters

Args	parameter pack to forward to T's constructor

Parameters

args	Arguments to forward to T's constructor

template<typename T >

static const_iterator Scine::Molassembler::Temple::TinySet< T >::find	(	const std::vector< T > &	set,
		const T &	a
	)

inlinestatic

Emplaces an element in an ordered vector if the element is not contained.

Note: This does inplace-construct the element at the back of the vector, then searches for an equal element in the ordered part of the vector. If the element is found, the newly-constructed element is popped back off. Otherwise, it is rotated to its position. This implies that this function may trigger reallocation of the vector even though the element is already part of the vector.

Parameters

set	An ordered vector to add the element to

Template Parameters

Args	parameter pack to forward to T's constructor

Parameters

args	Arguments to forward to T's constructor

template<typename T >

void Scine::Molassembler::Temple::TinySet< T >::insert ( T a )

inline

Inserts an element into the set.

Warning: Does not check if the element already exists

template<typename T >

template<typename It >

void Scine::Molassembler::Temple::TinySet< T >::insert	(	It	a,
		const It &	b
	)

inline

Inserts all elements contained in a range.

Warning: Does not check if the element already exists

template<typename T >

TinySet& Scine::Molassembler::Temple::TinySet< T >::operator= ( std::initializer_list< T > init )

inline

Assign from an initializer list.

Warning: Repeated elements are retained in insertion

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

Molassembler/Temple/TinySet.h

Public Types

Public Member Functions

Static Public Member Functions

Data Fields

Detailed Description

template<typename T> struct Scine::Molassembler::Temple::TinySet< T >

Member Function Documentation

template<typename T>
struct Scine::Molassembler::Temple::TinySet< T >