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

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

#include <BoundedSortedArray.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...
 
 BoundedSortedArray (size_t capacity_=0, Compare compare_=Compare())
 Constructor. More...
 
 BoundedSortedArray (BoundedSortedArray const &src)
 Copy 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 getCapacity () const
 Get the maximum number of elements the array can hold. 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 if no such element is present. More...
 
BoundedSortedArrayoperator= (BoundedSortedArray const &src)
 Assignment operator. 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...
 
void setCapacity (size_t capacity_)
 Set the maximum number of elements the array can hold. 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 if no such element is present. More...
 
 ~BoundedSortedArray ()
 Destructor. More...
 

Detailed Description

template<typename T, typename Compare = std::less<T>>
class Thea::BoundedSortedArray< T, Compare >

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

If the array is full and a new element is added, the last element is dropped.

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. This space is allocated on the heap: if the capacity is known at compile-time, BoundedSortedArrayN, which can use stack storage, is usually preferred.

See also
BoundedSortedArrayN

Definition at line 38 of file BoundedSortedArray.hpp.

Member Typedef Documentation

typedef T const* const_iterator

Iterator over immutable elements.

Definition at line 46 of file BoundedSortedArray.hpp.

typedef std::reverse_iterator<const_iterator> const_reverse_iterator

Reverse iterator over immutable elements.

Definition at line 47 of file BoundedSortedArray.hpp.

Constructor & Destructor Documentation

BoundedSortedArray ( size_t  capacity_ = 0,
Compare  compare_ = Compare() 
)

Constructor.

Allocates memory for capacity_ elements.

Parameters
capacity_The maximum number of elements the array can hold. Must be a non-negative integer.
compare_The comparator that evaluates the "less-than" operator on objects of type T.

Definition at line 55 of file BoundedSortedArray.hpp.

BoundedSortedArray ( BoundedSortedArray< T, Compare > const &  src)

Copy constructor.

Definition at line 65 of file BoundedSortedArray.hpp.

Destructor.

Definition at line 93 of file BoundedSortedArray.hpp.

Member Function Documentation

const_iterator begin ( ) const
noexcept

Iterator to the beginning of the array.

Definition at line 120 of file BoundedSortedArray.hpp.

const_iterator cbegin ( ) const
noexcept

Iterator to the beginning of the array.

Definition at line 121 of file BoundedSortedArray.hpp.

const_iterator cend ( ) const
noexcept

Iterator to the end of the array.

Reverse iterator to the end of the array.

Definition at line 123 of file BoundedSortedArray.hpp.

void clear ( )

Remove all elements from the array.

Definition at line 300 of file BoundedSortedArray.hpp.

bool contains ( T const &  t) const

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

Definition at line 157 of file BoundedSortedArray.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 163 of file BoundedSortedArray.hpp.

const_reverse_iterator crbegin ( ) const
noexcept

Reverse iterator to the beginning of the array.

Definition at line 127 of file BoundedSortedArray.hpp.

T const* data ( ) const

Get a pointer to the data buffer.

Definition at line 118 of file BoundedSortedArray.hpp.

bool empty ( ) const

Check if the array is empty or not.

Definition at line 115 of file BoundedSortedArray.hpp.

const_iterator end ( ) const
noexcept

Iterator to the end of the array.

Definition at line 122 of file BoundedSortedArray.hpp.

void erase ( size_t  i)

Remove the element at the given position from the array.

Definition at line 284 of file BoundedSortedArray.hpp.

void erase ( T const &  t)

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

Definition at line 294 of file BoundedSortedArray.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 176 of file BoundedSortedArray.hpp.

T const& first ( ) const

Get the first element in the sorted sequence.

Definition at line 136 of file BoundedSortedArray.hpp.

size_t getCapacity ( ) const

Get the maximum number of elements the array can hold.

Definition at line 109 of file BoundedSortedArray.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 if the value could not be inserted.

Definition at line 244 of file BoundedSortedArray.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 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 275 of file BoundedSortedArray.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 234 of file BoundedSortedArray.hpp.

T const& last ( ) const

Get the last element in the sorted sequence.

Definition at line 143 of file BoundedSortedArray.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 if no such element is present.

Definition at line 210 of file BoundedSortedArray.hpp.

BoundedSortedArray& operator= ( BoundedSortedArray< T, Compare > const &  src)

Assignment operator.

Definition at line 74 of file BoundedSortedArray.hpp.

T const& operator[] ( size_t  i) const

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

Definition at line 150 of file BoundedSortedArray.hpp.

const_reverse_iterator rbegin ( ) const
noexcept

Reverse iterator to the end of the array.

Definition at line 124 of file BoundedSortedArray.hpp.

const_reverse_iterator rend ( ) const
noexcept

Reverse iterator to the beginning of the array.

Definition at line 130 of file BoundedSortedArray.hpp.

void setCapacity ( size_t  capacity_)

Set the maximum number of elements the array can hold.

The array is cleared and all prior data is discarded.

Definition at line 96 of file BoundedSortedArray.hpp.

size_t size ( ) const

Get the number of elements in the array.

Definition at line 112 of file BoundedSortedArray.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 if no such element is present.

Definition at line 186 of file BoundedSortedArray.hpp.


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