SortedArray< T, Compare > Class Template Reference

An array sorted in ascending order according to a comparator. More...

#include <SortedArray.hpp>

Public Member Functions
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...
bool	empty () const
	Check if the array is empty or not. More...
void	erase (intx 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...
intx	find (T const &t) const
	Get the index of a given value, or negative if it is not present in the array. More...
T const &	first () const
	Get the first element in the sorted sequence. More...
intx	insert (T const &t)
	Insert a value into the array. More...
intx	insertUnique (T const &t)
	Insert a value into the array only if it does not already exist. More...
T const &	last () const
	Get the last element in the sorted sequence. More...
intx	lowerBound (T const &t) const
	Get the index of the first element equal to or greater than t, or return the size of the array if no such element is present. More...
T const &	operator[] (intx i) const
	Get the element at a given position in the sorted sequence. More...
intx	size () const
	Get the number of elements in the array. More...
	SortedArray (Compare compare_=Compare())
	Constructor. More...
intx	upperBound (T const &t) const
	Get the index of the first element strictly greater than t, or return the size of the array if no such element is present. More...

Detailed Description

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

An array sorted in ascending order according to a comparator.

Definition at line 26 of file SortedArray.hpp.

Constructor & Destructor Documentation

SortedArray

(

Compare

compare_ = Compare()

)

Constructor.

Parameters

compare_

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

Definition at line 38 of file SortedArray.hpp.

Member Function Documentation

void clear

(

)

Remove all elements from the array.

Definition at line 189 of file SortedArray.hpp.

bool contains

(

T const &

t

)

const

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

Definition at line 68 of file SortedArray.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 74 of file SortedArray.hpp.

bool empty

(

)

const

Check if the array is empty or not.

Definition at line 44 of file SortedArray.hpp.

void erase

(

intx

i

)

Remove the element at the given position from the array.

Definition at line 177 of file SortedArray.hpp.

void erase

(

T const &

t

)

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

Definition at line 183 of file SortedArray.hpp.

intx find

(

T const &

t

)

const

Get the index of a given value, or negative if it is not present in the array.

If the value occurs multiple times, the index of any one occurrence is returned.

Definition at line 87 of file SortedArray.hpp.

T const& first

(

)

const

Get the first element in the sorted sequence.

Definition at line 47 of file SortedArray.hpp.

intx insert

(

T const &

t

)

Insert a value into the array.

Returns

The index of the newly inserted element, or negative if the value could not be inserted.

Definition at line 146 of file SortedArray.hpp.

intx 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 negative 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 168 of file SortedArray.hpp.

T const& last

(

)

const

Get the last element in the sorted sequence.

Definition at line 54 of file SortedArray.hpp.

intx lowerBound

(

T const &

t

)

const

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

Definition at line 121 of file SortedArray.hpp.

T const& operator[]

(

intx

i

)

const

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

Definition at line 61 of file SortedArray.hpp.

intx size

(

)

const

Get the number of elements in the array.

Definition at line 41 of file SortedArray.hpp.

intx upperBound

(

T const &

t

)

const

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

Definition at line 97 of file SortedArray.hpp.

---

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

• SortedArray.hpp