VectorDeque satisfies the resource constraints typically expected of both Vectors and Deques. More...

#include <VectorDeque.hpp>

Public Types
typedef IteratorBase < VectorDeque, DataType, false >	Iterator
	Mutable iterator for `VectorDeque`s.

typedef IteratorBase< const VectorDeque, const DataType, false >	ConstIterator
	Immutable iterator for `VectorDeque`s.

typedef IteratorBase < VectorDeque, DataType, true >	ReverseIterator
	Mutable reverse iterator for `VectorDeque`s.

typedef IteratorBase< const VectorDeque, const DataType, true >	ConstReverseIterator
	Immutable reverse iterator for `VectorDeque`s.

Public Member Functions
	VectorDeque () throw ()
	Constructs a `VectorDeque` with a default initial capacity. More...

	VectorDeque (const size_t capacity) throw ()
	Constructs a `VectorDeque` with the given initial capacity. More...

	VectorDeque (const VectorDeque &that) throw ()
	Non-temporary copy constructor. More...

	VectorDeque (VectorDeque &&that) throw ()
	Temporary copy constructor. More...

VectorDeque &	operator= (const VectorDeque &that) throw ()
	Non-temporary assignment. More...

VectorDeque &	operator= (VectorDeque &&that) throw ()
	Temporary assignment. More...

bool	operator== (const VectorDeque &that) const throw ()
	Checks to see if `*this` is equal to another `VectorDeque`. More...

bool	operator!= (const VectorDeque &that) const throw ()
	Checks to see if `*this` is not equal to another VectorDeque. More...

DataType &	operator[] (const size_t index) const
	Access the element at `index`. More...

	operator std::string () const throw ()
	Gives a human-readable representation of `*this`. More...

void	add (const DataType &element) throw ()
	Add `element` to the back of `*this`. More...

void	addAll (const DataType *const elements, const size_t length) throw ()
	Add an array of elements to the back of `*this`. More...

template<class IteratorType >
void	addAll (IteratorType begin, IteratorType end) throw ()
	Add a collection of elements to the back of `*this`. More...

void	addAllFirst (const DataType *const elements, const size_t length) throw ()
	Add an array of elements to the front of `*this`. More...

template<class IteratorType >
void	addAllFirst (IteratorType begin, IteratorType end) throw ()
	Add a collection of elements to the front of `*this`. More...

void	addFirst (const DataType &element) throw ()
	Add `element` to the front of `*this`. More...

Iterator	begin () throw ()
	Get an iterator pointing to the first element of `*this`. More...

ConstIterator	cbegin () const throw ()
	Get a constant iterator pointing to the first element of `*this`. More...

ConstIterator	cend () const throw ()
	Get an iterator past the last element of `*this`. More...

void	clear () throw ()
	Remove all elements from `*this`. More...

bool	contains (const DataType &element) const throw ()
	Check to see if `element` is contained in `*this`. More...

void	copyToArray (DataType *const target) const throw ()
	Copy the contents of `*this` to `target`. More...

ConstReverseIterator	crbegin () const throw ()
	Get a constant reverse iterator pointing to the last element of `*this`. More...

ConstReverseIterator	crend () const throw ()
	Get an iterator past the last element of `*this`. More...

Iterator	end () throw ()
	Get an iterator past the last element of `*this`. More...

ssize_t	find (const DataType &element) const throw ()
	Check to see where `element` is located in `*this`. More...

DataType &	fromBack (const size_t index) const
	Access the element at `index` starting from the last element. More...

void	insert (const DataType &element, const size_t before)
	Insert `element` before `before`. More...

void	insert (const DataType &element, const ConstIterator &it)
	Insert `element` before the element pointed to by `it`. More...

void	insert (const DataType &element, const ConstReverseIterator &it)
	Insert `element` after (with respect to `*this`) the element pointed to by the reverse iterator `it`. More...

bool	isEmpty () const throw ()
	Checks whether `*this` is empty. More...

DataType	peek () const
	Get the first element of `*this`. More...

DataType	peekLast () const
	Get the last element of `*this`. More...

DataType	pop ()
	Remove and return the first element. More...

void	popAll (DataType *const target) throw ()
	Put every element into `target` and then remove them from `*this`. More...

void	popAllLast (DataType *const target) throw ()
	Put every element into `target` from the back and then remove them from `*this`. More...

DataType	popLast ()
	Remove and return the last element. More...

void	popSome (DataType *const target, const size_t amount)
	Remove `amount` elements and put them into `target`. More...

void	popSomeLast (DataType *const target, const size_t amount)
	Remove `amount` elements from the back and put them into `target`. More...

ReverseIterator	rbegin () throw ()
	Get a reverse iterator pointing to the last element of `*this`. More...

DataType	removeAt (const size_t index)
	Remove the element at `index`. More...

DataType	removeAt (const ConstIterator &it)
	Remove the element pointed to by `it`. More...

DataType	removeAt (const ConstReverseIterator &it)
	Remove the element pointed to by `it`. More...

Iterator	rend () throw ()
	Get an iterator past the last element of `*this`. More...

void	reverseCopyToArray (DataType *const target) const throw ()
	Copy the contents of `*this` to the given array in reverse order. More...

void	reverseSliceToArray (DataType *const target, const size_t from, const size_t until) const
	Copy a slice of contents of `*this` to `target` in reverse order. More...

size_t	size () const throw ()
	Returns the number of elements in `*this`. More...

void	skip (const size_t amount=1)
	Removes `amount` elements from the front of `*this`. More...

void	skipLast (const size_t amount=1)
	Removes `amount` elements from the back of `*this`. More...

void	sliceToArray (DataType *const target, const size_t from, const size_t until) const
	Copy a slice of elements of `*this` to `target`. More...

Static Public Attributes
static const size_t	DEFAULT_INITIAL_CAPACITY = 11
	The capacity to initialize a `VectorDeque` to by default.

Friends
class	VectorDequeTest

Detailed Description

template<class DataType>
class VectorDeque< DataType >

VectorDeque satisfies the resource constraints typically expected of both Vectors and Deques.

In particular, it has

O(1) Member access
O(1) Append
O(1) Prepend

Additionally, VectorDeque will only automatically resize when it is at full capacity. Iterators for VectorDeque maintain an index to the element they are currently pointing to, and modifications to the VectorDeque will not change that index. For example, suppose an element is added to the front of the VectorDeque while an iterator is pointing to the third element. That iterator will now be pointing to what was previously the second element, since that element is now the third element and the iterator's index did not change.

Parameters

DataType The type of the data to contain.

Constructor & Destructor Documentation

template<class DataType >

VectorDeque< DataType >::VectorDeque	(	)
throw	(
	)

inline

Constructs a VectorDeque with a default initial capacity.

Runtime: O(1)

template<class DataType >

VectorDeque< DataType >::VectorDeque	(	const size_t	capacity	)
throw	(
	)

inlineexplicit

Constructs a VectorDeque with the given initial capacity.

Runtime: O(1)

Parameters

capacity Initial capacity to construct with.

template<class DataType >

VectorDeque< DataType >::VectorDeque	(	const VectorDeque< DataType > &	that	)
throw	(
	)

inline

Non-temporary copy constructor.

Differs from the temporary copy constructor in that the underlying array is copied instead of moved. Runtime: O(that.size())

Parameters

that	`VectorDeque` to construct from.

template<class DataType >

VectorDeque< DataType >::VectorDeque	(	VectorDeque< DataType > &&	that	)
throw	(
	)

inline

Temporary copy constructor.

Differs from the non-temporary copy constructor in the the underlying array is moved instead of copied. Runtime: O(1)

Parameters

that	Temporary `VectorDeque` to construct from.

Member Function Documentation

template<class DataType >

void VectorDeque< DataType >::add	(	const DataType &	element	)
throw	(
	)

inline

Add element to the back of *this.

Runtime: O(1)

Parameters

element Element to add.

template<class DataType >

void VectorDeque< DataType >::addAll	(	const DataType *const	elements,
		const size_t	length
	)
throw	(
	)

inline

Add an array of elements to the back of *this.

Runtime: O(length)

Parameters

elements	Elements to add.
length	Amount of elements to add.

template<class DataType >

template<class IteratorType >

void VectorDeque< DataType >::addAll	(	IteratorType	begin,
		IteratorType	end
	)
throw	(
	)

inline

Add a collection of elements to the back of *this.

Runtime: O(size of given collection)

Parameters

begin	Iterator to the first element to add.
end	Iterator past the last element to add.
IteratorType	The type of the iterator.

template<class DataType >

void VectorDeque< DataType >::addAllFirst	(	const DataType *const	elements,
		const size_t	length
	)
throw	(
	)

inline

Add an array of elements to the front of *this.

This method works as though addFirst was sequentially called on elements. Thus, the last element added is the first element in *this after addAllFirst terminates. Runtime: O(length)

Parameters

elements	Elements to add.
length	Amount of elements to add.

template<class DataType >

template<class IteratorType >

void VectorDeque< DataType >::addAllFirst	(	IteratorType	begin,
		IteratorType	end
	)
throw	(
	)

inline

Add a collection of elements to the front of *this.

This method works as though addFirst was sequentially called on for the given iterator. Thus, the last element added is the first element in *this after addAllFirst terminates. Runtime: O(size of given collection)

Parameters

begin	Iterator to the first element to add.
end	Iterator past the last element to add.
IteratorType	The type of the iterator.

template<class DataType >

void VectorDeque< DataType >::addFirst	(	const DataType &	element	)
throw	(
	)

inline

Add element to the front of *this.

Runtime: O(1)

Parameters

element Element to add.

template<class DataType >

Iterator VectorDeque< DataType >::begin	(	)
throw	(
	)

inline

Get an iterator pointing to the first element of *this.

Runtime: O(1)

Returns: Iterator pointing to the first element of *this.

template<class DataType >

ConstIterator VectorDeque< DataType >::cbegin	(	)	const
throw	(
	)

inline

Get a constant iterator pointing to the first element of *this.

Runtime: O(1)

Returns: Constant iterator pointing to the first element of *this.

template<class DataType >

ConstIterator VectorDeque< DataType >::cend	(	)	const
throw	(
	)

inline

Get an iterator past the last element of *this.

Runtime: O(1)

Returns: Iterator past the last element of *this.

template<class DataType >

void VectorDeque< DataType >::clear	(	)
throw	(
	)

inline

Remove all elements from *this.

Runtime: O(1).

template<class DataType >

bool VectorDeque< DataType >::contains	(	const DataType &	element	)	const
throw	(
	)

inline

Check to see if element is contained in *this.

Runtime: O(size())

Parameters

element Element to check for.

Returns: true If (*this)[i] == element for some 0 <= i < size() and false otherwise.

template<class DataType >

void VectorDeque< DataType >::copyToArray	(	DataType *const	target	)	const
throw	(
	)

inline

Copy the contents of *this to target.

Runtime: O(size())

Parameters

target Array to copy to.

template<class DataType >

ConstReverseIterator VectorDeque< DataType >::crbegin	(	)	const
throw	(
	)

inline

Get a constant reverse iterator pointing to the last element of *this.

Runtime: O(1)

Returns: Constant reverse iterator pointing to the last element of *this.

template<class DataType >

ConstReverseIterator VectorDeque< DataType >::crend	(	)	const
throw	(
	)

inline

Get an iterator past the last element of *this.

Runtime: O(1)

Returns: Iterator past the last element of *this.

template<class DataType >

Iterator VectorDeque< DataType >::end	(	)
throw	(
	)

inline

Get an iterator past the last element of *this.

Runtime: O(1)

Returns: Iterator past the last element of *this.

template<class DataType >

ssize_t VectorDeque< DataType >::find	(	const DataType &	element	)	const
throw	(
	)

inline

Check to see where element is located in *this.

Runtime: O(size())

Parameters

element Element to check for.

Returns: The first i such that (*this)[i] == element or -1 if no such element exists.

template<class DataType >

DataType& VectorDeque< DataType >::fromBack ( const size_t index ) const

inline

Access the element at index starting from the last element.

Runtime: O(1) Exception Safety: Strong

Parameters

index Index to get an element at.

Returns: A reference to the element.

Exceptions

std::length_error If index >= size().

template<class DataType >

void VectorDeque< DataType >::insert	(	const DataType &	element,
		const size_t	before
	)

inline

Insert element before before.

Runtime: Amortized O(min(before, size() - before)) Exception Safety: Strong

Parameters

element	Element to insert.
before	Index of the element to insert before. The inserted element's index will be `before`.

Exceptions

std::length_error If before > size().

template<class DataType >

void VectorDeque< DataType >::insert	(	const DataType &	element,
		const ConstIterator &	it
	)

inline

Insert element before the element pointed to by it.

If the call is successful, the iterator will be pointing to the new element. Runtime: O(size()) Exception Safety: Strong

Parameters

it	Iterator whose pointed-to element will be after the inserted element.

Exceptions

std::length_error	If `it` points to an out-of-bounds element.
std::invalid_argument	If `it` is not iterating over `*this`.

template<class DataType >

void VectorDeque< DataType >::insert	(	const DataType &	element,
		const ConstReverseIterator &	it
	)

inline

Insert element after (with respect to *this) the element pointed to by the reverse iterator it.

If the call is successful, the iterator will be pointing to the new element. Runtime: O(size()) Exception Safety: Strong

Parameters

it	Iterator whose pointed-to element will be after the inserted element.

Exceptions

std::length_error	If `it` points to an out-of-bounds element.
std::invalid_argument	If `it` is not iterating over `*this`.

template<class DataType >

bool VectorDeque< DataType >::isEmpty	(	)	const
throw	(
	)

inline

Checks whether *this is empty.

Runtime: O(1)

Returns: true If size() == 0, false otherwise.

template<class DataType >

VectorDeque< DataType >::operator std::string	(	)	const
throw	(
	)

inline

Gives a human-readable representation of *this.

Runtime: O(size())

Returns: Each element of *this, comma-separated and enclosed in curly braces.

template<class DataType >

bool VectorDeque< DataType >::operator!=	(	const VectorDeque< DataType > &	that	)	const
throw	(
	)

inline

Checks to see if *this is not equal to another VectorDeque.

Runtime: O(size())

Parameters

that	Other `VectorDeque` to check inequality for.

Returns: true If (*this)[i] != that[i] for some 0 <= i < size() or this->size() != that.size().

template<class DataType >

VectorDeque& VectorDeque< DataType >::operator=	(	const VectorDeque< DataType > &	that	)
throw	(
	)

inline

Non-temporary assignment.

Differs from temporary assignment in that the underlying array is copied instead of moved. Runtime: O(that.size())

Parameters

that	`VectorDeque` to assign from.

Returns: A reference to *this.

template<class DataType >

VectorDeque& VectorDeque< DataType >::operator=	(	VectorDeque< DataType > &&	that	)
throw	(
	)

inline

Temporary assignment.

Differs from the non-temporary assignment in the the underlying array is moved instead of copied. Runtime: O(1)

Parameters

that	Temporary `VectorDeque` to assign from.

Returns: A reference to *this.

template<class DataType >

bool VectorDeque< DataType >::operator==	(	const VectorDeque< DataType > &	that	)	const
throw	(
	)

inline

Checks to see if *this is equal to another VectorDeque.

Runtime:O(size())

Parameters

that	Other `VectorDeque` to check equality for.

Returns: true If (*this)[i] == that[i] for every 0 <= i < size() and this->size() == that.size().

template<class DataType >

DataType& VectorDeque< DataType >::operator[] ( const size_t index ) const

inline

Access the element at index.

Runtime: O(1) Exception Safety: Strong

Parameters

index Index to get an element at.

Returns: A reference to the element.

Exceptions

std::length_error If index >= size().

template<class DataType >

DataType VectorDeque< DataType >::peek ( ) const

inline

Get the first element of *this.

Runtime: O(1) Exception Safety: Strong

Returns: The first element of *this.

Exceptions

std::length_error If isEmpty().

template<class DataType >

DataType VectorDeque< DataType >::peekLast ( ) const

inline

Get the last element of *this.

Runtime: O(1) Exception Safety: Strong

Returns: The last element of *this.

Exceptions

std::length_error If isEmpty().

template<class DataType >

DataType VectorDeque< DataType >::pop ( )

inline

Remove and return the first element.

Runtime: O(1) Exception Safety: Strong

Returns: The first element.

Exceptions

std::length_error If isEmpty().

template<class DataType >

void VectorDeque< DataType >::popAll	(	DataType *const	target	)
throw	(
	)

inline

Put every element into target and then remove them from *this.

Runtime: O(size())

Parameters

target Array to put elements into.

template<class DataType >

void VectorDeque< DataType >::popAllLast	(	DataType *const	target	)
throw	(
	)

inline

Put every element into target from the back and then remove them from *this.

Runtime: O(size())

Parameters

target Array to put elements into.

template<class DataType >

DataType VectorDeque< DataType >::popLast ( )

inline

Remove and return the last element.

Runtime: O(1) Exception Safety: Strong

Returns: The last element.

Exceptions

std::length_error If isEmpty().

template<class DataType >

void VectorDeque< DataType >::popSome	(	DataType *const	target,
		const size_t	amount
	)

inline

Remove amount elements and put them into target.

Runtime: O(amount) Exception Safety: Strong

Parameters

target Array to put removed elements into.

Exceptions

std::length_error If size() < amount.

template<class DataType >

void VectorDeque< DataType >::popSomeLast	(	DataType *const	target,
		const size_t	amount
	)

inline

Remove amount elements from the back and put them into target.

This method works as if amount invocations of popLast were sequentially called on *this. Thus, the last element popped will be the last element in target. Runtime: O(amount) Exception Safety: Strong

Parameters

target Array to put removed elements into.

Exceptions

std::length_error If size() < amount.

template<class DataType >

ReverseIterator VectorDeque< DataType >::rbegin	(	)
throw	(
	)

inline

Get a reverse iterator pointing to the last element of *this.

Runtime: O(1)

Returns: Reverse iterator pointing to the first element of *this.

template<class DataType >

DataType VectorDeque< DataType >::removeAt ( const size_t index )

inline

Remove the element at index.

Runtime: O(size()) Exception Safety: Strong

Parameters

index Index to remove the element at.

Returns: The removed element.

Exceptions

std::length_error If index >= size().

template<class DataType >

DataType VectorDeque< DataType >::removeAt ( const ConstIterator & it )

inline

Remove the element pointed to by it.

Runtime: O(size()) Exception Safety: Strong

Parameters

it	Iterator to remove the pointed-to element for.

Returns: The removed element.

Exceptions

std::length_error	If `it` points to an out-of-bounds element.
std::invalid_argument	If `it` is not iterating over `*this`.

template<class DataType >

DataType VectorDeque< DataType >::removeAt ( const ConstReverseIterator & it )

inline

Remove the element pointed to by it.

Runtime: O(size()) Exception Safety: Strong

Parameters

it	Iterator to remove the pointed-to element for.

Returns: The removed element.

Exceptions

std::length_error	If `it` points to an out-of-bounds element.
std::invalid_argument	If `it` is not iterating over `*this`.

template<class DataType >

Iterator VectorDeque< DataType >::rend	(	)
throw	(
	)

inline

Get an iterator past the last element of *this.

Runtime: O(1)

Returns: Iterator past the last element of *this.

template<class DataType >

void VectorDeque< DataType >::reverseCopyToArray	(	DataType *const	target	)	const
throw	(
	)

inline

Copy the contents of *this to the given array in reverse order.

Runtime: O(size())

Parameters

target Array to copy to.

template<class DataType >

void VectorDeque< DataType >::reverseSliceToArray	(	DataType *const	target,
		const size_t	from,
		const size_t	until
	)		const

inline

Copy a slice of contents of *this to target in reverse order.

Runtime: O(until - from) Exception Safety: Strong

Parameters

target	Array to copy to.
from	Index of `*this` to start copying.
until	Index of `*this` to stop copying (exclusive).

Exceptions

std::length_error	If `until > size()`.
std::invalid_argument	If `from > until`.

template<class DataType >

size_t VectorDeque< DataType >::size	(	)	const
throw	(
	)

inline

Returns the number of elements in *this.

Runtime: O(1)

Returns: The number of elements in *this.

template<class DataType >

void VectorDeque< DataType >::skip ( const size_t amount = 1 )

inline

Removes amount elements from the front of *this.

Runtime: O(1) Exception Safety: Strong

Parameters

amount Amount of elements to remove.

Exceptions

std::length_error If amount > size().

template<class DataType >

void VectorDeque< DataType >::skipLast ( const size_t amount = 1 )

inline

Removes amount elements from the back of *this.

Runtime: O(1) Exception Safety: Strong

Parameters

amount Amount of elements to remove.

Exceptions

std::length_error If amount > size()

template<class DataType >

void VectorDeque< DataType >::sliceToArray	(	DataType *const	target,
		const size_t	from,
		const size_t	until
	)		const

inline

Copy a slice of elements of *this to target.

Runtime: O(until - from) Exception Safety: Strong

Parameters

target	Array to copy to.
from	Index of `*this` to start copying.
until	Index of `*this` to stop copying (exclusive).

Exceptions

std::length_error If until > size() or from > until.

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

main/include/VectorDeque.hpp

Public Types

Public Member Functions

Static Public Attributes

Friends

Detailed Description

template<class DataType> class VectorDeque< DataType >

Constructor & Destructor Documentation

Member Function Documentation

template<class DataType>
class VectorDeque< DataType >