|
Thea
|
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_iterator > | const_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... | |
| BoundedSortedArray & | operator= (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... | |
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.
Definition at line 38 of file BoundedSortedArray.hpp.
| 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.
| BoundedSortedArray | ( | size_t | capacity_ = 0, |
| Compare | compare_ = Compare() |
||
| ) |
Constructor.
Allocates memory for capacity_ elements.
| 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.
| ~BoundedSortedArray | ( | ) |
Destructor.
Definition at line 93 of file BoundedSortedArray.hpp.
|
noexcept |
Iterator to the beginning of the array.
Definition at line 120 of file BoundedSortedArray.hpp.
|
noexcept |
Iterator to the beginning of the array.
Definition at line 121 of file BoundedSortedArray.hpp.
|
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.
|
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.
|
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.
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.
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.
|
noexcept |
Reverse iterator to the end of the array.
Definition at line 124 of file BoundedSortedArray.hpp.
|
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.
1.8.11