Sorted std::vector wrapper. This class is a light alternative to std::set. Inspired from: [1] www.lafstern.org/matt/col1.pdf. More...

#include <utils_sorted_vector.hpp>

Inheritance diagram for lxgui::utils::sorted_vector< T, Cmp >:

Public Types
using	iterator = typename base::iterator

using	const_iterator = typename base::const_iterator

using	reverse_iterator = typename base::reverse_iterator

using	const_reverse_iterator = typename base::const_reverse_iterator

Public Member Functions
	sorted_vector ()=default
	Default constructor. Creates an empty vector.

	sorted_vector (const sorted_vector &s)=default
	Copy another vector into this one.

	sorted_vector (sorted_vector &&s)=default
	Move another sorted_vector into this one. The other vector is left empty in the process, and all its content is transfered into this new one.

sorted_vector &	operator= (const sorted_vector &s)=default
	Copy another sorted_vector into this one.

sorted_vector &	operator= (sorted_vector &&s)=default
	Move another vector into this one. The other vector is left empty in the process, and all its content is transfered into this new one.

	sorted_vector (const base &s)
	Copy a pre-built vector into this one. The provided vector must be sorted, and shall not contain any duplicate value.

	sorted_vector (base &&s)
	Move a pre-built vector into this one. The provided vector must be sorted, and shall not contain any duplicate value. It is left empty in the process, and all its content is transfered into this new sorted_vector.

	sorted_vector (const Cmp &c)
	Default constructor, with comparator. Creates an empty vector and sets the comparator function.

	sorted_vector (std::initializer_list< T > l)
	Write an initializer list into this vector. The list need not be sorted.

Cmp &	comparator ()
	Return the comparator object.

const Cmp &	comparator () const
	Return the comparator object.

template<typename U >
std::pair< iterator, bool >	insert (U &&t)
	Insert the provided object in the vector, only if no object exists with the same key.

template<typename U >
iterator	insert_or_assign (U &&t)
	Insert the provided object in the vector.

iterator	erase (iterator iter)
	Erase an element from this vector.

iterator	erase (iterator first, iterator last)
	Erase a range from this vector.

template<typename Key >
iterator	erase (const Key &k)
	Erase an element from this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no object is found with that key, this function does nothing.

template<typename Key >
iterator	find (const Key &k)
	Find an object in this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no element is found, this function returns end().

template<typename Key >
const_iterator	find (const Key &k) const
	Find an object in this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no element is found, this function returns end().

Detailed Description

template<typename T, typename Cmp = std::less<T>>
class lxgui::utils::sorted_vector< T, Cmp >

Sorted std::vector wrapper. This class is a light alternative to std::set. Inspired from: [1] www.lafstern.org/matt/col1.pdf.

The sorted vector achieves the same O(log(N)) look up complexity as std::set, but with a lower constant of proportionality thanks to the binary search algorithm (twice lower according to [1]). The fact that this container uses an std::vector internally also implies that it has the lowest possible memory usage.

On the other hand, it has worse insertion complexity (O(N), compared to the O(log(N)) of std::set). This drawback can be completely ignored if either:

one does much more look-ups than insertions,
all the data are available when the vector is created, so that the insertions are all performed in one go,
and, even better, if one builds an already sorted std::vector and creates a sorted_vector out of it.

The elements of this container are sorted according to the Cmp template argument, which defaults to std::less<T> (i.e. the elements are sorted using operator<()). One can provide a custom comparison functor if std::less is not desirable. Using a custom comparison functor can also allow to find elements by keys instead of their own value. For example, if T is

struct test { int id; };

then one can use the following comparison functor:

struct comp {
    bool operator() (const test& n1, const test& n2) const {
        return n1.id < n2.id;
    }
    bool operator() (const test& n1, int i) const {
        return n1.id < i;
    }
    bool operator() (int i, const test& n2) const {
        return i < n2.id;
    }
};

and use an integer as the key to find elements in the container

using vec_t = sorted_vector<test, comp>;
vec_t vec;
// ... fill vec with some data ...
// Then find the element that has the 'id' equal to 5
vec_t::iterator it = vec.find(5);

Definition at line 69 of file utils_sorted_vector.hpp.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename Cmp = std::less<T>>

using lxgui::utils::sorted_vector< T, Cmp >::const_iterator = typename base::const_iterator

Definition at line 75 of file utils_sorted_vector.hpp.

◆ const_reverse_iterator

template<typename T , typename Cmp = std::less<T>>

using lxgui::utils::sorted_vector< T, Cmp >::const_reverse_iterator = typename base::const_reverse_iterator

Definition at line 77 of file utils_sorted_vector.hpp.

◆ iterator

template<typename T , typename Cmp = std::less<T>>

using lxgui::utils::sorted_vector< T, Cmp >::iterator = typename base::iterator

Definition at line 74 of file utils_sorted_vector.hpp.

◆ reverse_iterator

template<typename T , typename Cmp = std::less<T>>

using lxgui::utils::sorted_vector< T, Cmp >::reverse_iterator = typename base::reverse_iterator

Definition at line 76 of file utils_sorted_vector.hpp.

Constructor & Destructor Documentation

◆ sorted_vector() [1/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( )

default

Default constructor. Creates an empty vector.

◆ sorted_vector() [2/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( const sorted_vector< T, Cmp > & s )

default

Copy another vector into this one.

◆ sorted_vector() [3/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( sorted_vector< T, Cmp > && s )

default

Move another sorted_vector into this one. The other vector is left empty in the process, and all its content is transfered into this new one.

◆ sorted_vector() [4/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( const base & s )

inlineexplicit

Copy a pre-built vector into this one. The provided vector must be sorted, and shall not contain any duplicate value.

Definition at line 109 of file utils_sorted_vector.hpp.

◆ sorted_vector() [5/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( base && s )

inlineexplicit

Move a pre-built vector into this one. The provided vector must be sorted, and shall not contain any duplicate value. It is left empty in the process, and all its content is transfered into this new sorted_vector.

Definition at line 117 of file utils_sorted_vector.hpp.

◆ sorted_vector() [6/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( const Cmp & c )

inlineexplicit

Default constructor, with comparator. Creates an empty vector and sets the comparator function.

Definition at line 123 of file utils_sorted_vector.hpp.

◆ sorted_vector() [7/7]

template<typename T , typename Cmp = std::less<T>>

lxgui::utils::sorted_vector< T, Cmp >::sorted_vector ( std::initializer_list< T > l )

inline

Write an initializer list into this vector. The list need not be sorted.

Definition at line 129 of file utils_sorted_vector.hpp.

Member Function Documentation

◆ comparator() [1/2]

template<typename T , typename Cmp = std::less<T>>

Cmp & lxgui::utils::sorted_vector< T, Cmp >::comparator ( )

inline

Return the comparator object.

Definition at line 136 of file utils_sorted_vector.hpp.

◆ comparator() [2/2]

template<typename T , typename Cmp = std::less<T>>

const Cmp & lxgui::utils::sorted_vector< T, Cmp >::comparator ( ) const

inline

Return the comparator object.

Definition at line 141 of file utils_sorted_vector.hpp.

◆ erase() [1/3]

template<typename T , typename Cmp = std::less<T>>

template<typename Key >

iterator lxgui::utils::sorted_vector< T, Cmp >::erase ( const Key & k )

inline

Erase an element from this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no object is found with that key, this function does nothing.

Definition at line 195 of file utils_sorted_vector.hpp.

◆ erase() [2/3]

template<typename T , typename Cmp = std::less<T>>

iterator lxgui::utils::sorted_vector< T, Cmp >::erase	(	iterator	first,
		iterator	last
	)

inline

Erase a range from this vector.

Definition at line 184 of file utils_sorted_vector.hpp.

◆ erase() [3/3]

template<typename T , typename Cmp = std::less<T>>

iterator lxgui::utils::sorted_vector< T, Cmp >::erase ( iterator iter )

inline

Erase an element from this vector.

Definition at line 179 of file utils_sorted_vector.hpp.

◆ find() [1/2]

template<typename T , typename Cmp = std::less<T>>

template<typename Key >

iterator lxgui::utils::sorted_vector< T, Cmp >::find ( const Key & k )

inline

Find an object in this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no element is found, this function returns end().

Definition at line 210 of file utils_sorted_vector.hpp.

◆ find() [2/2]

template<typename T , typename Cmp = std::less<T>>

template<typename Key >

const_iterator lxgui::utils::sorted_vector< T, Cmp >::find ( const Key & k ) const

inline

Find an object in this vector by its key. The key can be a copy of the element itself, or any other object that is supported by the chosen comparison function. If no element is found, this function returns end().

Definition at line 226 of file utils_sorted_vector.hpp.

◆ insert()

template<typename T , typename Cmp = std::less<T>>

template<typename U >

std::pair< iterator, bool > lxgui::utils::sorted_vector< T, Cmp >::insert ( U && t )

inline

Insert the provided object in the vector, only if no object exists with the same key.

Note: If an object already exists with the same key, the vector is unchanged and the boolean in the returned pair is set to false. Else, the vector is modified and the boolean is set to true.

Definition at line 152 of file utils_sorted_vector.hpp.

◆ insert_or_assign()

template<typename T , typename Cmp = std::less<T>>

template<typename U >

iterator lxgui::utils::sorted_vector< T, Cmp >::insert_or_assign ( U && t )

inline

Insert the provided object in the vector.

Note: If an object already exists with the same key, it is destroyed and replaced by this one.

Definition at line 171 of file utils_sorted_vector.hpp.

◆ operator=() [1/2]

template<typename T , typename Cmp = std::less<T>>

sorted_vector & lxgui::utils::sorted_vector< T, Cmp >::operator= ( const sorted_vector< T, Cmp > & s )

default

Copy another sorted_vector into this one.

◆ operator=() [2/2]

template<typename T , typename Cmp = std::less<T>>

sorted_vector & lxgui::utils::sorted_vector< T, Cmp >::operator= ( sorted_vector< T, Cmp > && s )

default

Move another vector into this one. The other vector is left empty in the process, and all its content is transfered into this new one.

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

/home/runner/work/lxgui/lxgui/include/lxgui/utils_sorted_vector.hpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ sorted_vector() [1/7]

◆ sorted_vector() [2/7]

◆ sorted_vector() [3/7]

◆ sorted_vector() [4/7]

◆ sorted_vector() [5/7]

◆ sorted_vector() [6/7]

◆ sorted_vector() [7/7]

Member Function Documentation

◆ comparator() [1/2]

◆ comparator() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ insert()

◆ insert_or_assign()

◆ operator=() [1/2]

◆ operator=() [2/2]