ext::linear_set

An adaptor set with lookup complexity O(N) based on sequence (contiguous structure by default). More...

#include <linear_set.h>

Public Types

	Name
using KeyFromValue	key_from_value <br>Public typedefs similar to standard sets.
using Value	value_type
using std::decay_t< decltype(key_from_value()(static_cast< value_type >(nullptr)))>	key_type
using Sequence< value_type >	container_type
using typename container_type::pointer	pointer <br>Iterator-related typedefs redeclared from the underlying container type.
using typename container_type::const_pointer	const_pointer
using typename container_type::reference	reference
using typename container_type::const_reference	const_reference
using typename container_type::iterator	iterator
using typename container_type::const_iterator	const_iterator
using typename container_type::reverse_iterator	reverse_iterator
using typename container_type::const_reverse_iterator	const_reverse_iterator
using typename container_type::size_type	size_type
using typename container_type::difference_type	difference_type

Public Functions

	Name
	linear_set() =default<br>Standard constructors (copy and move are implicit).
	linear_set(std::initializer_list< value_type > init_list)
template <typename Iterator > <br>	linear_set(Iterator first1, Iterator last1)
const_iterator	find(const key_type & key) const<br>Finds an entry in the set by key.
iterator	find(const key_type & key)
std::pair< iterator, bool >	insert(const value_type & value)<br>Inserts a value into the set if the equal value is not in the set.
std::pair< iterator, bool >	insert(value_type && value)
iterator	erase(const_iterator pos)<br>Erases the entry pointed by an iterator.
iterator	erase(iterator pos)
container_type &	data()
const container_type &	data() const
const_iterator	cbegin() const
const_iterator	begin() const
const_iterator	cend() const
const_iterator	end() const
reverse_iterator	rbegin()<br>Corresponding reverse iterators.
reverse_iterator	rend()
const_reverse_iterator	crbegin() const
const_reverse_iterator	rbegin() const
const_reverse_iterator	crend() const
const_reverse_iterator	rend() const
key_from_value	key_extractor() const
size_type	count(const key_type & key) const<br>Determines if an entry in the set.
template <typename Iterator > <br>void	insert(Iterator first1, Iterator last1)<br>Inserts a range of elements.
template <typename... Ts> <br>std::pair< iterator, bool >	emplace(Ts &&... args)<br>Attempts to build and insert an entry.
size_type	erase(const key_type & key)<br>Erases the entry with a key.
void	swap(linear_set & other)<br>Swaps data with another linear set.
size_type	size() const
bool	empty() const
void	clear()<br>Erases all entries in the set.
void	reserve(size_type n)<br>Prepares the linear set for a specified number of entries.
size_type	capacity() const
iterator	begin()
iterator	end()

Friends

	Name
bool	operator==(const linear_set & lhs, const linear_set & rhs) <br>Non-member equality test operators.
bool	operator!=(const linear_set & lhs, const linear_set & rhs)
void	swap(linear_set & lhs, linear_set & rhs) <br>Friend swap definition for convenience sake.

Detailed Description

cpp

template <typename Value ,
typename KeyFromValue  =identity,
template< typename... > class Sequence =std::vector>
class ext::linear_set;

An adaptor set with lookup complexity O(N) based on sequence (contiguous structure by default).

Template Parameters:

Value The type of the values.
KeyFromValue The key extraction functor.
Sequence The underlying container type.

This set is designed for a small number of elements. Consider this class a convenient wrapper around std::vector<Value>.

Since this set is based on the vector by default, the order of insertions is preserved, and it provides random access iterators.

Unlike STL sets, this set is designed like boost::multi_index or Python sets; that is, there is key retrieval (indexation) policy for values. Therefore, this set also acts like a map.

The major differences from the standard library sets:

Values are not const.
Iterators, references, pointers can be invalidated by modifier functions (insert, erase, reserve, etc.). This is the inherited behavior from std::vector.
Some API may be extra or missing.
Key extraction is not stored as member data. Instead, it is treated as a policy.

The performance of the set critically depends on the number of entries, the size of the value, and the cost of comparing values for equality. The advantage of the linear_set comes from cache-friendliness, and fewer CPU front-end and back-end stalls.

Public Types Documentation

using key_from_value

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::key_from_value =  KeyFromValue;

Public typedefs similar to standard sets.

using value_type

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::value_type =  Value;

using key_type

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::key_type =  std::decay_t<decltype( key_from_value()(*static_cast<value_type*>(nullptr)))>;

using container_type

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::container_type =  Sequence<value_type>;

using pointer

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::pointer =  typename container_type::pointer;

Iterator-related typedefs redeclared from the underlying container type.

using const_pointer

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::const_pointer =  typename container_type::const_pointer;

using reference

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::reference =  typename container_type::reference;

using const_reference

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::const_reference =  typename container_type::const_reference;

using iterator

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::iterator =  typename container_type::iterator;

using const_iterator

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::const_iterator =  typename container_type::const_iterator;

using reverse_iterator

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::reverse_iterator =  typename container_type::reverse_iterator;

using const_reverse_iterator

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::const_reverse_iterator =  typename container_type::const_reverse_iterator;

using size_type

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::size_type =  typename container_type::size_type;

using difference_type

cpp

using ext::linear_set< Value, KeyFromValue, Sequence >::difference_type =  typename container_type::difference_type;

Public Functions Documentation

function linear_set

cpp

linear_set() =default

Standard constructors (copy and move are implicit).

function linear_set

cpp

inline linear_set(
    std::initializer_list< value_type > init_list
)

function linear_set

cpp

template <typename Iterator >
inline linear_set(
    Iterator first1,
    Iterator last1
)

function find

cpp

inline const_iterator find(
    const key_type & key
) const

Finds an entry in the set by key.

Parameters:

key The key of the entry.

Return: Iterator pointing to the entry, or end() if not found.

function find

cpp

inline iterator find(
    const key_type & key
)

function insert

cpp

inline std::pair< iterator, bool > insert(
    const value_type & value
)

Inserts a value into the set if the equal value is not in the set.

Parameters:

value The new value to be inserted.

Return: A pair of an iterator and insertion flag. The iterator points to possibly inserted entry, and the flag indicates whether the entry is actually inserted.

function insert

cpp

inline std::pair< iterator, bool > insert(
    value_type && value
)

function erase

cpp

inline iterator erase(
    const_iterator pos
)

Erases the entry pointed by an iterator.

Parameters:

pos An iterator pointing to the entry.

Return: An iterator pointing after the entry.

function erase

cpp

inline iterator erase(
    iterator pos
)

function data

cpp

inline container_type & data()

Return: The underlying data container. The container elements are ordered exactly as inserted.

function data

cpp

inline const container_type & data() const

function cbegin

cpp

inline const_iterator cbegin() const

Return: A read-only iterator pointing to the first entry.

function begin

cpp

inline const_iterator begin() const

function cend

cpp

inline const_iterator cend() const

Return: A read-only iterator pointing one past the last entry.

function end

cpp

inline const_iterator end() const

function rbegin

cpp

inline reverse_iterator rbegin()

Corresponding reverse iterators.

function rend

cpp

inline reverse_iterator rend()

function crbegin

cpp

inline const_reverse_iterator crbegin() const

function rbegin

cpp

inline const_reverse_iterator rbegin() const

function crend

cpp

inline const_reverse_iterator crend() const

function rend

cpp

inline const_reverse_iterator rend() const

function key_extractor

cpp

inline key_from_value key_extractor() const

Return: Value-to-key converter.

function count

cpp

inline size_type count(
    const key_type & key
) const

Determines if an entry in the set.

Parameters:

key The key of the entry.

Return: 1 if there's an entry, 0 otherwise.

function insert

cpp

template <typename Iterator >
inline void insert(
    Iterator first1,
    Iterator last1
)

Inserts a range of elements.

Parameters:

first1 The beginning of the range.
last1 The end of the range.

Template Parameters:

Iterator Iterator to the container with values.

The range is not assumed to be unique.

function emplace

cpp

template <typename... Ts>
inline std::pair< iterator, bool > emplace(
    Ts &&... args
)

Attempts to build and insert an entry.

Parameters:

args Arguments for the construction of the entry.

Return: An iterator pointing to the entry, and a flag indicating if the insertion actually happened.

function erase

cpp

inline size_type erase(
    const key_type & key
)

Erases the entry with a key.

Parameters:

key The key of the entry.

Return: 1 if the existing entry has been removed, 0 if there's no entry with the given key.

function swap

cpp

inline void swap(
    linear_set & other
)

Swaps data with another linear set.

Parameters:

other Another linear set.

function size

cpp

inline size_type size() const

Return: The number of entries in the set.

function empty

cpp

inline bool empty() const

Return: true if there are no entries.

function clear

cpp

inline void clear()

Erases all entries in the set.

function reserve

cpp

inline void reserve(
    size_type n
)

Prepares the linear set for a specified number of entries.

Parameters:

n The number of expected entries.

function capacity

cpp

inline size_type capacity() const

Return: The capacity of the underlying container.

function begin

cpp

inline iterator begin()

Return: A read/write iterator pointing to the first entry.

function end

cpp

inline iterator end()

Return: A read/write iterator pointing one past the last entry.

Friends

friend operator==

cpp

friend bool operator==(
    const linear_set & lhs,

    const linear_set & rhs
);

Non-member equality test operators.

Parameters:

lhs First set.
rhs Second set.

Note: The order of elements is not relevant. If the order matters for equality, compare the underlying data containers directly.

The complexity is O(N^2).

friend operator!=

cpp

friend bool operator!=(
    const linear_set & lhs,

    const linear_set & rhs
);

friend swap

cpp

friend void swap(
    linear_set & lhs,

    linear_set & rhs
);

Friend swap definition for convenience sake.

Updated on 2026-01-09 at 21:59:12 +0000

ext::linear_set ​

Public Types ​

Public Functions ​

Friends ​

Detailed Description ​

Public Types Documentation ​

using key_from_value ​

using value_type ​

using key_type ​

using container_type ​

using pointer ​

using const_pointer ​

using reference ​

using const_reference ​

using iterator ​

using const_iterator ​

using reverse_iterator ​

using const_reverse_iterator ​

using size_type ​

using difference_type ​

Public Functions Documentation ​

function linear_set ​

function linear_set ​

function linear_set ​

function find ​

function find ​

function insert ​

function insert ​

function erase ​

function erase ​

function data ​

function data ​

function cbegin ​

function begin ​

function cend ​

function end ​

function rbegin ​

function rend ​

function crbegin ​

function rbegin ​

function crend ​

function rend ​

function key_extractor ​

function count ​

function insert ​

function emplace ​

function erase ​

function swap ​

function size ​

function empty ​

function clear ​

function reserve ​

function capacity ​

function begin ​

function end ​

Friends ​

friend operator== ​

friend operator!= ​

friend swap ​

ext::linear_set

Public Types

Public Functions

Friends

Detailed Description

Public Types Documentation

using key_from_value

using value_type

using key_type

using container_type

using pointer

using const_pointer

using reference

using const_reference

using iterator

using const_iterator

using reverse_iterator

using const_reverse_iterator

using size_type

using difference_type

Public Functions Documentation

function linear_set

function linear_set

function linear_set

function find

function find

function insert

function insert

function erase

function erase

function data

function data

function cbegin

function begin

function cend

function end

function rbegin

function rend

function crbegin

function rbegin

function crend

function rend

function key_extractor

function count

function insert

function emplace

function erase

function swap

function size

function empty

function clear

function reserve

function capacity

function begin

function end

Friends

friend operator==

friend operator!=

friend swap