Thea
Public Types | Public Member Functions | Static Public Member Functions | List of all members
BoundedSortedArrayN< N, T, Compare > Class Template Reference

A sorted array of bounded maximum size N, ordered in ascending order according to a comparator. More...

#include <BoundedSortedArrayN.hpp>

Public Types

typedef T const * const_iterator
 Iterator over immutable elements. More...
 
typedef std::reverse_iterator< const_iteratorconst_reverse_iterator
 Reverse iterator over immutable elements. More...
 

Public Member Functions

const_iterator begin () const noexcept
 Iterator to the beginning of the array. More...
 
 BoundedSortedArrayN (Compare compare_=Compare())
 Constructor. More...
 
const_iterator cbegin () const noexcept
 Iterator to the beginning of the array. More...
 
const_iterator cend () const noexcept
 Iterator to the end of the array. More...
 
void clear ()
 Remove all elements from the array. More...
 
bool contains (T const &t) const
 Check if the array contains an element with a given value. More...
 
template<typename EqualityComparatorT >
bool contains (T const &t, EqualityComparatorT const &comp) const
 Check if the array already contains an element with a given value, by testing every element in the set for equality with the query. More...
 
const_reverse_iterator crbegin () const noexcept
 Reverse iterator to the beginning of the array. More...
 
T const * data () const
 Get a pointer to the data buffer. More...
 
bool empty () const
 Check if the array is empty or not. More...
 
const_iterator end () const noexcept
 Iterator to the end of the array. More...
 
void erase (size_t i)
 Remove the element at the given position from the array. More...
 
void erase (T const &t)
 Remove (one occurrence of) the given value from the array, if it is present. More...
 
size_t find (T const &t) const
 Get the index of a given value in the array. More...
 
T const & first () const
 Get the first element in the sorted sequence. More...
 
size_t insert (T const &t)
 Insert a value into the array. More...
 
size_t insertUnique (T const &t)
 Insert a value into the array only if it does not already exist. More...
 
bool isInsertable (T const &t) const
 Check if a value can be inserted in the array. More...
 
T const & last () const
 Get the last element in the sorted sequence. More...
 
size_t lowerBound (T const &t) const
 Get the index of the first element equal to or greater than t, or return the capacity of the array (N) if no such element is present. More...
 
T const & operator[] (size_t i) const
 Get the element at a given position in the sorted sequence. More...
 
const_reverse_iterator rbegin () const noexcept
 Reverse iterator to the end of the array. More...
 
const_reverse_iterator rend () const noexcept
 Reverse iterator to the beginning of the array. More...
 
size_t size () const
 Get the number of elements in the array. More...
 
size_t upperBound (T const &t) const
 Get the index of the first element strictly greater than t, or return the capacity of the array (N) if no such element is present. More...
 

Static Public Member Functions

static constexpr size_t getCapacity ()
 Get the maximum number of elements the array can hold. More...
 

Detailed Description

template<size_t N, typename T, typename Compare = std::less<T>>
class Thea::BoundedSortedArrayN< N, T, Compare >

A sorted array of bounded maximum size N, ordered in ascending order according to a comparator.

If the array is full and a new element is added, the last element is dropped. The capacity is set as a template parameter N, so the array can be stored entirely on the stack. If the array size is known at compile-time, this class is usually a more efficient alternative to BoundedSortedArray.

To get some extra speed when T has a trivial (bit-copy) assignment operator, make sure that std::is_trivially_copyable is true for T.

The implementation always allocates enough space to store the maximum number of instances of T. The capacity N should be positive (non-zero).

See also
BoundedSortedArray

Definition at line 40 of file BoundedSortedArrayN.hpp.

Member Typedef Documentation

typedef T const* const_iterator

Iterator over immutable elements.

Definition at line 50 of file BoundedSortedArrayN.hpp.

typedef std::reverse_iterator<const_iterator> const_reverse_iterator

Reverse iterator over immutable elements.

Definition at line 51 of file BoundedSortedArrayN.hpp.

Constructor & Destructor Documentation

BoundedSortedArrayN ( Compare  compare_ = Compare())

Constructor.

Parameters
compare_The comparator that evaluates the "less-than" operator on objects of type T.

Definition at line 58 of file BoundedSortedArrayN.hpp.

Member Function Documentation

const_iterator begin ( ) const
noexcept

Iterator to the beginning of the array.

Definition at line 72 of file BoundedSortedArrayN.hpp.

const_iterator cbegin ( ) const
noexcept

Iterator to the beginning of the array.

Definition at line 73 of file BoundedSortedArrayN.hpp.

const_iterator cend ( ) const
noexcept

Iterator to the end of the array.

Reverse iterator to the end of the array.

Definition at line 75 of file BoundedSortedArrayN.hpp.

void clear ( )

Remove all elements from the array.

Definition at line 249 of file BoundedSortedArrayN.hpp.

bool contains ( T const &  t) const

Check if the array contains an element with a given value.

Definition at line 109 of file BoundedSortedArrayN.hpp.

bool contains ( T const &  t,
EqualityComparatorT const &  comp 
) const

Check if the array already contains an element with a given value, by testing every element in the set for equality with the query.

This is useful when searching with other notions of equality than that defined by the ordering comparator.

Definition at line 115 of file BoundedSortedArrayN.hpp.

const_reverse_iterator crbegin ( ) const
noexcept

Reverse iterator to the beginning of the array.

Definition at line 79 of file BoundedSortedArrayN.hpp.

T const* data ( ) const

Get a pointer to the data buffer.

Definition at line 70 of file BoundedSortedArrayN.hpp.

bool empty ( ) const

Check if the array is empty or not.

Definition at line 67 of file BoundedSortedArrayN.hpp.

const_iterator end ( ) const
noexcept

Iterator to the end of the array.

Definition at line 74 of file BoundedSortedArrayN.hpp.

void erase ( size_t  i)

Remove the element at the given position from the array.

Definition at line 233 of file BoundedSortedArrayN.hpp.

void erase ( T const &  t)

Remove (one occurrence of) the given value from the array, if it is present.

Definition at line 243 of file BoundedSortedArrayN.hpp.

size_t find ( T const &  t) const

Get the index of a given value in the array.

If the value is not present in the array, the capacity of the array is returned. If the value occurs multiple times, the index of any one occurrence is returned.

Definition at line 128 of file BoundedSortedArrayN.hpp.

T const& first ( ) const

Get the first element in the sorted sequence.

Definition at line 88 of file BoundedSortedArrayN.hpp.

static constexpr size_t getCapacity ( )
static

Get the maximum number of elements the array can hold.

Definition at line 61 of file BoundedSortedArrayN.hpp.

size_t insert ( T const &  t)

Insert a value into the array.

Returns
The index of the newly inserted element, or the capacity of the array (N) if the value could not be inserted.

Definition at line 196 of file BoundedSortedArrayN.hpp.

size_t insertUnique ( T const &  t)

Insert a value into the array only if it does not already exist.

Returns
The index of the newly inserted element, or the capacity of the array (N) if the value could not be inserted.
Todo:
Make this faster by merging the containment test with the lookup for the insertion position.

Definition at line 224 of file BoundedSortedArrayN.hpp.

bool isInsertable ( T const &  t) const

Check if a value can be inserted in the array.

This requires that either the array has fewer elements than its capacity, or the value is "less than" the last element in the array.

Definition at line 186 of file BoundedSortedArrayN.hpp.

T const& last ( ) const

Get the last element in the sorted sequence.

Definition at line 95 of file BoundedSortedArrayN.hpp.

size_t lowerBound ( T const &  t) const

Get the index of the first element equal to or greater than t, or return the capacity of the array (N) if no such element is present.

Definition at line 162 of file BoundedSortedArrayN.hpp.

T const& operator[] ( size_t  i) const

Get the element at a given position in the sorted sequence.

Definition at line 102 of file BoundedSortedArrayN.hpp.

const_reverse_iterator rbegin ( ) const
noexcept

Reverse iterator to the end of the array.

Definition at line 76 of file BoundedSortedArrayN.hpp.

const_reverse_iterator rend ( ) const
noexcept

Reverse iterator to the beginning of the array.

Definition at line 82 of file BoundedSortedArrayN.hpp.

size_t size ( ) const

Get the number of elements in the array.

Definition at line 64 of file BoundedSortedArrayN.hpp.

size_t upperBound ( T const &  t) const

Get the index of the first element strictly greater than t, or return the capacity of the array (N) if no such element is present.

Definition at line 138 of file BoundedSortedArrayN.hpp.


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