Vector that maintains its elements sorted. More...

#include <SortedVector.hpp>

Public Types
using	value_type = T
	Type of the elements in the sorted list.

using	size_type = size_t
	Type of the size of the sorted list.

using	difference_type = std::ptrdiff_t
	Type of the difference between two iterators.

using	reference = T&
	Type of the reference to an element in the sorted list.

using	const_reference = const T&
	Type of the const reference to an element in the sorted list.

using	pointer = T*
	Type of the pointer to an element in the sorted list.

using	const_pointer = const T*
	Type of the const pointer to an element in the sorted list.

using	iterator = typename std::vector<T>::iterator
	Type of the iterator to the sorted list.

using	const_iterator = typename std::vector<T>::const_iterator
	Type of the const iterator to the sorted list.

using	reverse_iterator
	Type of the reverse iterator to the sorted list.

using	const_reverse_iterator
	Type of the const reverse iterator to the sorted list.

Public Member Functions
	SortedVector ()=default
	Construct a new SortedVector object.

	SortedVector (size_t size)
	Construct a new SortedVector object with the giver `size`.

	SortedVector (std::initializer_list< T > list)
	Construct a new SortedVector object using an initializer `list`.

template<typename V >
iterator	insert (V &&value)
	Insert an element with the provided `value` into the sorted list.

template<typename V >
iterator	insert (V &&value, bool insert_lower)
	Insert an element with the provided `value` into the sorted list.

template<typename... Args>
iterator	emplace (Args &&... args)
	Emplace a new element into the sorted list.

template<typename... Args>
iterator	emplace (bool insert_lower, Args &&... args)
	Emplace a new element into the sorted list.

size_t	size () const
	Get read-only access to the size of the vector.

bool	empty () const
	Check whether the vector is emtpy.

const T &	at (size_t i) const
	Access element at index `i` with bounds checking.

const T &	at (int i) const
	Access element at index `i` with bounds checking.

const T &	operator[] (size_t i) const
	Direct access to the underlying vector.

const T &	front () const
	Reference to the first element in the sorted list.

const T &	back () const
	Reference to the last element in the sorted list.

bool	erase (const const_iterator &it)
	Remove the element at position `it` from the sorted list.

bool	erase (size_t i)
	Remove the element at index `i` from the sorted list.

bool	erase (int i)
	Remove the element at index `i` from the sorted list.

bool	erase_value (const T &value)
	Remove an element with the provided `value` from the sorted list.

const_iterator	find (const T &value) const
	Find the index of an element with the provided `value` in the sorted list.

const_iterator	lower_bound (const T &value) const
	Find the first position in which an element with the provided `value` could be inserted without changing the ordering.

const_iterator	upper_bound (const T &value) const
	Find the last position in which an element with the provided `value` could be inserted without changing the ordering.

size_t	count (const T &value) const
	Count the number of occurrences of an element with the provided `value` in the sorted list.

bool	contains (const T &value) const
	Check if the element with the provided `value` is contained in the vector.

const_iterator	lesser_end (const T &value) const
	Find the last element in the vector with a value lesser than `value` and return an iterator to the position after that one.

const_iterator	greater_begin (const T &value) const
	Find the first element in the vector with a value greater than `value` and return an iterator to its position.

void	clear ()
	Clear the sorted list, removing all elements.

Private Member Functions
bool	is_equal (const T &lhs, const T &rhs) const
	Use the compare_ function to check if two elements are equal.

Private Attributes
std::vector< T >	vector_
	Underlying vector to store the sorted list.

Compare	compare_
	Comparison function to maintain the sorted order.

Detailed Description

template<class T, class Compare = std::less<T>>
class dlinear::SortedVector< T, Compare >

Vector that maintains its elements sorted.

This class is implemented as a wrapper around std::vector to provide a sorted list of elements. Each time an element is inserted, it is placed in the correct position to maintain the sorted order.

SortedVector<int> sorted_vector;
sorted_vector.insert(3);
sorted_vector.insert(1);
sorted_vector.insert(2);
for (const auto& value : sorted_vector) {
  std::cout << value << " ";
}
// Output: 1 2 3

Using a custom comparison function is also supported:

SortedVector<int, std::greater<>> sorted_vector;
sorted_vector.insert(3);
sorted_vector.insert(1);
sorted_vector.insert(2);
for (const auto& value : sorted_vector) {
  std::cout << value << " ";
}
// Output: 3 2 1

Template Parameters

T	type of the elements in the sorted list
Compare	comparison function to maintain the sorted order

Definition at line 49 of file SortedVector.hpp.

Constructor & Destructor Documentation

◆ SortedVector() [1/2]

template<class T , class Compare = std::less<T>>

dlinear::SortedVector< T, Compare >::SortedVector ( size_t size )

inlineexplicit

Construct a new SortedVector object with the giver size.

Parameters

size	size of the sorted list.

Definition at line 71 of file SortedVector.hpp.

◆ SortedVector() [2/2]

template<class T , class Compare = std::less<T>>

dlinear::SortedVector< T, Compare >::SortedVector ( std::initializer_list< T > list )

inline

Construct a new SortedVector object using an initializer list.

The elements are placed in the correct position to maintain the sorted order.

Parameters

list	initializer list of elements

Definition at line 78 of file SortedVector.hpp.

Member Function Documentation

◆ at() [1/2]

template<class T , class Compare = std::less<T>>

const T & dlinear::SortedVector< T, Compare >::at ( int i ) const

inline

Access element at index i with bounds checking.

It also supports negative indices, where -1 is the last element, -2 is the second to last, and so on.

Parameters

i	position of the element to access (negative indices are supported)

Returns: element at the given position

Exceptions

std::out_of_range if i is out of range

Definition at line 167 of file SortedVector.hpp.

◆ at() [2/2]

template<class T , class Compare = std::less<T>>

const T & dlinear::SortedVector< T, Compare >::at ( size_t i ) const

inline

Access element at index i with bounds checking.

Parameters

i	position of the element to access

Returns: element at the given position

Exceptions

std::out_of_range if i is out of range

Definition at line 154 of file SortedVector.hpp.

◆ back()

template<class T , class Compare = std::less<T>>

const T & dlinear::SortedVector< T, Compare >::back ( ) const

inline

Reference to the last element in the sorted list.

Returns: reference to the last element

Definition at line 190 of file SortedVector.hpp.

◆ contains()

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::contains ( const T & value ) const

inlinenodiscard

Check if the element with the provided value is contained in the vector.

Parameters

value value of the element to search

Returns: true if the element is present; false if the element is not present

Definition at line 307 of file SortedVector.hpp.

◆ count()

template<class T , class Compare = std::less<T>>

size_t dlinear::SortedVector< T, Compare >::count ( const T & value ) const

inlinenodiscard

Count the number of occurrences of an element with the provided value in the sorted list.

If the element is not found, 0 is returned.

Parameters

value value of the element to count

Returns: number of occurrences of the element in the sorted list

Definition at line 293 of file SortedVector.hpp.

◆ emplace() [1/2]

template<class T , class Compare = std::less<T>>

template<typename... Args>

iterator dlinear::SortedVector< T, Compare >::emplace ( Args &&... args )

inline

Emplace a new element into the sorted list.

The arguments are forwarded to the constructor of the element type. The element is placed in the correct position to maintain the sorted order.

Parameters

args	arguments to forward to the constructor of the element type

Definition at line 124 of file SortedVector.hpp.

◆ emplace() [2/2]

template<class T , class Compare = std::less<T>>

template<typename... Args>

iterator dlinear::SortedVector< T, Compare >::emplace	(	bool	insert_lower,
		Args &&...	args )

inline

Emplace a new element into the sorted list.

The arguments are forwarded to the constructor of the element type. The element is placed in the correct position to maintain the sorted order. This version allows to specify if the element should be inserted in the lower or upper bound.

Parameters

insert_lower	if true, the element is inserted in the lower bound, otherwise in the upper bound
args	arguments to forward to the constructor of the element type

Definition at line 138 of file SortedVector.hpp.

◆ empty()

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::empty ( ) const

inlinenodiscard

Check whether the vector is emtpy.

Returns: true if the vector is emtpy; false if the vector is not emtpy

Definition at line 146 of file SortedVector.hpp.

◆ erase() [1/3]

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::erase ( const const_iterator & it )

inline

Remove the element at position it from the sorted list.

If the iterator is out of range, false is returned.

Parameters

it	iterator to the element to remove

Returns: true if the element has been removed; false if the element was not found

Definition at line 200 of file SortedVector.hpp.

◆ erase() [2/3]

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::erase ( int i )

inline

Remove the element at index i from the sorted list.

It also supports negative indices, where -1 is the last element, -2 is the second to last, and so on. If the index is out of range, false is returned.

Parameters

i	index of the element to remove

Returns: true if the element has been removed; false if the element was not found

Definition at line 226 of file SortedVector.hpp.

◆ erase() [3/3]

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::erase ( size_t i )

inline

Remove the element at index i from the sorted list.

If the index is out of range, false is returned.

Parameters

i	index of the element to remove

Returns: true if the element has been removed; false if the element was not found

Definition at line 212 of file SortedVector.hpp.

◆ erase_value()

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::erase_value ( const T & value )

inline

Remove an element with the provided value from the sorted list.

If multiple elements have the same value, only the first one is removed. If the element is not found, false is returned.

Parameters

value value of the element to remove

Returns: true if the element has been removed; false if the element was not found

Definition at line 241 of file SortedVector.hpp.

◆ find()

template<class T , class Compare = std::less<T>>

const_iterator dlinear::SortedVector< T, Compare >::find ( const T & value ) const

inline

Find the index of an element with the provided value in the sorted list.

If the element is not found, the end iterator is returned.

Parameters

value value of the element to find

Returns: iterator to the element if it is found; end iterator if the element is not found

Definition at line 256 of file SortedVector.hpp.

◆ front()

template<class T , class Compare = std::less<T>>

const T & dlinear::SortedVector< T, Compare >::front ( ) const

inline

Reference to the first element in the sorted list.

Returns: reference to the first element

Definition at line 184 of file SortedVector.hpp.

◆ greater_begin()

template<class T , class Compare = std::less<T>>

const_iterator dlinear::SortedVector< T, Compare >::greater_begin ( const T & value ) const

inlinenodiscard

Find the first element in the vector with a value greater than value and return an iterator to its position.

Parameters

value lower bound for the search

Returns: iterator to the first element with value less than value

Definition at line 325 of file SortedVector.hpp.

◆ insert() [1/2]

template<class T , class Compare = std::less<T>>

template<typename V >

iterator dlinear::SortedVector< T, Compare >::insert ( V && value )

inline

Insert an element with the provided value into the sorted list.

The element is placed in the correct position to maintain the sorted order. It returns an iterator to the inserted element.

Template Parameters

V	type of the element to insert

Parameters

value value of the element to insert

Returns: iterator to the inserted element

Definition at line 93 of file SortedVector.hpp.

◆ insert() [2/2]

template<class T , class Compare = std::less<T>>

template<typename V >

iterator dlinear::SortedVector< T, Compare >::insert	(	V &&	value,
		bool	insert_lower )

inline

Insert an element with the provided value into the sorted list.

The element is placed in the correct position to maintain the sorted order. It returns an iterator to the inserted element. This version allows to specify if the element should be inserted in the lower or upper bound.

Template Parameters

V	type of the element to insert

Parameters

value	value of the element to insert
insert_lower	if true, the element is inserted in the lower bound, otherwise in the upper bound

Returns: iterator to the inserted element

Definition at line 110 of file SortedVector.hpp.

◆ is_equal()

template<class T , class Compare = std::less<T>>

bool dlinear::SortedVector< T, Compare >::is_equal	(	const T &	lhs,
		const T &	rhs ) const

inlinenodiscardprivate

Use the compare_ function to check if two elements are equal.

Since the function only checks ordering, to make sure two elements are equal compare_ must be used twice.

Parameters

lhs	left-hand side element
rhs	right-hand side element

Returns: true if the elements are equal; false if the elements are not equal

Definition at line 357 of file SortedVector.hpp.

◆ lesser_end()

template<class T , class Compare = std::less<T>>

const_iterator dlinear::SortedVector< T, Compare >::lesser_end ( const T & value ) const

inlinenodiscard

Find the last element in the vector with a value lesser than value and return an iterator to the position after that one.

Parameters

value upper bound for the search

Returns: iterator to the position after the last element with value less than value

Definition at line 315 of file SortedVector.hpp.

◆ lower_bound()

template<class T , class Compare = std::less<T>>

const_iterator dlinear::SortedVector< T, Compare >::lower_bound ( const T & value ) const

inline

Find the first position in which an element with the provided value could be inserted without changing the ordering.

It is equivalent to using std::lower_bound with the Compare function.

Parameters

value value of the element to find

Returns: iterator to the first valid position

Definition at line 270 of file SortedVector.hpp.

◆ operator[]()

template<class T , class Compare = std::less<T>>

const T & dlinear::SortedVector< T, Compare >::operator[] ( size_t i ) const

inline

Direct access to the underlying vector.

Parameters

i	position of the element to access

Returns: element at the given position

Definition at line 178 of file SortedVector.hpp.

◆ size()

template<class T , class Compare = std::less<T>>

size_t dlinear::SortedVector< T, Compare >::size ( ) const

inlinenodiscard

Get read-only access to the size of the vector.

Returns: size of the vector

Definition at line 143 of file SortedVector.hpp.

◆ upper_bound()

template<class T , class Compare = std::less<T>>

const_iterator dlinear::SortedVector< T, Compare >::upper_bound ( const T & value ) const

inline

Find the last position in which an element with the provided value could be inserted without changing the ordering.

It is equivalent to using std::upper_bound with the Compare function.

Parameters

value value of the element to find

Returns: iterator to the last valid position

Definition at line 282 of file SortedVector.hpp.

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

dlinear/util/SortedVector.hpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SortedVector() [1/2]

◆ SortedVector() [2/2]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ back()

◆ contains()

◆ count()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ empty()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ erase_value()

◆ find()

◆ front()

◆ greater_begin()

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_equal()

◆ lesser_end()

◆ lower_bound()

◆ operator[]()

◆ size()

◆ upper_bound()