jem::util::Flex< T > Class Template Reference

Implements a generic, resizable vector. More...

#include <jem/util/Flex.h>

Public Types
typedef T *	Iterator
	A random access iterator type. More...
typedef const T *	ConstIterator
	A read-only random access iterator type. More...

Public Member Functions
	Flex ()
	Constructs an empty flex. More...
	Flex (int n)
	Constructs a flex of a given size. More...
	Flex (const Flex &rhs)
	Constructs a copy of another flex. More...
template<class InputIterator >
	Flex (InputIterator first, InputIterator last)
	Constructs a flex given two input iterators. More...
	~Flex ()
	Deallocates all memory allocated by this flex. More...
Iterator	begin ()
	Returns an iterator pointing to the begin of this flex. More...
ConstIterator	begin () const
	Returns a const iterator pointing to the begin of this flex. More...
Iterator	end ()
	Returns an iterator pointing to the end of this flex. More...
ConstIterator	end () const
	Returns a const iterator pointing to the end of this flex. More...
T &	front ()
	Returns a reference to the first element in this flex. More...
const T &	front () const
	Returns a const reference to the first element in this flex. More...
T &	back ()
	Returns a reference to the last element in this flex. More...
const T &	back () const
	Returns a const reference to the last element in this flex. More...
Flex &	operator= (const Flex &rhs)
	Copies another flex. More...
Flex &	operator= (T rhs)
	Sets all elements in this flex to a given value. More...
void	swap (Flex &rhs)
	Swaps the contents of this flex with another flex. More...
T &	operator[] (int i)
	Returns the element at a given index. More...
const T &	operator[] (int i) const
	Returns the element at a given index. More...
void	pushBack (T item)
	Appends an element to this flex. More...
void	pushBack (T item, int n)
	Appends multiple copies of an element to this flex. More...
template<class InputIterator >
void	pushBack (InputIterator first, InputIterator last)
	Appends the elements between two input iterators to this flex. More...
void	popBack ()
	Deletes the last element in this flex. More...
void	popBack (int n)
	Deletes multiple elements at the end of this flex. More...
void	insert (Iterator pos, T item)
	Inserts an element into this flex. More...
void	insert (Iterator pos, T item, int n)
	Inserts multiple copies of an element into this flex. More...
template<class InputIterator >
void	insert (Iterator pos, InputIterator first, InputIterator last)
	Inserts the elements between two input iterators into this flex. More...
void	erase (Iterator pos)
	Deletes an element from this flex. More...
void	erase (Iterator first, Iterator last)
	Deletes multiple elements from this flex. More...
void	clear ()
	Deletes all elements from this flex. More...
void	resize (int n)
	Adjusts the size of this flex. More...
void	reserve (int cap)
	Sets the capacity of this flex to a given value. More...
void	setExpansionFactor (float x)
	Sets the expansion factor if this flex to a given value. More...
float	getExpansionFactor () const
	Returns the expansion factor of this flex. More...
void	trimToSize ()
	Sets the capacity to the size of this flex. More...
int	capacity () const
	Returns the capacity of this flex. More...
int	size () const
	Returns the size of this flex. More...
T *	addr (int i=0)
	Returns a pointer to an element in this flex. More...
const T *	addr (int i=0) const
	Returns a const pointer to an element in this flex. More...

Static Public Attributes
static const float	EXPANSION_FACTOR
	The default expansion factor. More...

Related Functions
(Note that these are not member functions.)
template<class T >
io::DataInput &	operator>> (io::DataInput &in, Flex< T > &f)
	Flex de-serialization operator. More...
template<class T >
io::DataOutput &	operator<< (io::DataOutput &out, const Flex< T > &f)
	Flex serialization operator. More...
template<class T >
io::TextOutput &	operator<< (io::TextOutput &out, const Flex< T > &f)
	Flex print operator. More...
template<class T >
void	swap (Flex< T > &lhs, Flex< T > &rhs)
	Interchanges two flex instances. More...

Detailed Description

template<class T>
class jem::util::Flex< T >

The template class Flex represents a vector (one-dimensional array) containing elements of type T. The elements are numbered in the usual way from zero to the total number of elements minus one. They can be accessed in constant time by calling the overloaded subscript operator or by dereferencing an iterator returned by a Flex instance.

In contrast to the Array class, the Flex class provides functions for adding and removing elements. Although elements can be inserted at arbitrary positions, the Flex class is optimized for appending elements to the end of a Flex. Likewise, removing elements from the end of a Flex is much more efficient than removing elements from the middle or the beginning of a Flex.

A Flex has a capacity that specifies how many elements it can store without having to allocate additional memory. The capacity is automatically increased whenever there is no more space to store additional elements. The capacity can also be set manually when you know beforehand how many elements you are going to add to a Flex.

The automatic capacity growth of a Flex can be controlled by means of its expansion factor. Each time a Flex needs to allocate memory for additional elements, it multiplies its current capacity with its expansion factor to determine its new capacity. A larger expansion factor therefore leads to a more `aggressive' capacity growth.

Several members of the Flex class return iterators, pointers and references that refer to an element in a Flex instance. Unless stated otherwise, these iterators, pointers and references are valid as long as the Flex instance is not structurally modified, either by adding/removing elements, or by changing the capacity of the flex.

A Flex stores its elements in a contiguous array that can be accessed directly. This means that one can pass the elements in a Flex to a function that expects a standard array.

See also

Array, ArrayBuffer.

Member Typedef Documentation

template<class T>

typedef T* jem::util::Flex< T >::Iterator

A random access iterator type pointing to elements of type T. This iterator fulfills the requirements of the random access iterator category of the standard C++ library.

template<class T>

typedef const T* jem::util::Flex< T >::ConstIterator

A random access iterator type pointing to elements of type const T. This iterator fulfills the requirements of the random access iterator category of the standard C++ library.

Constructor & Destructor Documentation

template<class T>

jem::util::Flex< T >::Flex

(

)

Constructs an empty flex.

Postcondition

this->size() == 0 &&
this->capacity() == 0 &&
this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::Flex< T >::Flex ( int  n )

explicit

Constructs a flex of size n.

Parameters

n	- the size of this Flex.

Precondition

n >= 0
and the type T provides a default constructor.

Postcondition

this->size() == n &&
this->capacity() == n &&
this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::Flex< T >::Flex

(

const Flex< T > &

rhs

)

Constructs a flex containing copies of the elements of the rhs flex. The elements of the newly created flex are initialized by calling the copy constructor of type T.

Parameters

rhs	- the Flex to be copied.

Precondition

The type T has a copy constructor.

Postcondition

this->size() == rhs.size() &&
this->capacity() == this->size() &&
this->getExpansionFactor() == rhs.getExpansionFactor()

template<class T>

template<class InputIterator >

jem::util::Flex< T >::Flex	(	InputIterator	first,
		InputIterator	last
	)

Constructs a flex containing copies of the elements between the input iterators first and last. The elements of the newly created flex are initialized by calling the copy constructor of type T.

Parameters

first	- an input iterator pointing to the first element.
last	- an input iterator pointing one position past the last element.

Precondition

The expression *first can be converted to type T,
and the type T has a copy constructor,
and last is reachable from first.

Postcondition

this->size() == std::distance( first, last ) &&
this->capacity() == this->size() &&
this->getExpansionFactor() == EXPANSION_FACTOR

template<class T>

jem::util::Flex< T >::~Flex

(

)

Deallocates all memory that has been allocated by this flex. The destructor invalidates all iterators, pointers and references that point to an element in this flex.

Member Function Documentation

template<class T>

Iterator jem::util::Flex< T >::begin

(

)

Returns an iterator pointing to the first element in this flex, or end() if this flex is empty. The iterator is valid as long as this flex is not structurally modified, either by adding/removing elements, or by changing the capacity of this flex.

Returns

An iterator pointing to the begin of this flex.

template<class T>

ConstIterator jem::util::Flex< T >::begin

(

)

const

Returns a const iterator pointing to the first element in this flex, or end() if this flex is empty. The iterator is valid as long as this flex is not structurally modified.

Returns

A const iterator pointing to the begin of this flex.

template<class T>

Iterator jem::util::Flex< T >::end

(

)

Returns an iterator pointing to one position past the last element in this flex. The iterator is valid as long as this flex is not structurally modified.

Returns

An iterator pointing to the end of this flex.

template<class T>

ConstIterator jem::util::Flex< T >::end

(

)

const

Returns a const iterator pointing to one position past the last element in this flex. The iterator is valid as long as this flex is not structurally modified.

Returns

A const iterator pointing to the end of this flex.

template<class T>

T& jem::util::Flex< T >::front

(

)

Returns a reference to the first element in this flex. The reference is valid as long as this flex is not structurally modified.

Precondition

this->size() > 0

Returns

(*this)[0]

template<class T>

const T& jem::util::Flex< T >::front

(

)

const

Returns a const reference to the first element in this flex. The reference is valid as long as this flex is not structurally modified.

Precondition

this->size() > 0

Returns

(*this)[0]

template<class T>

T& jem::util::Flex< T >::back

(

)

Returns a reference to the last element in this flex. The reference is valid as long as this flex is not structurally modified.

Precondition

this->size() > 0

Returns

(*this)[ this->size() - 1 ]

template<class T>

const T& jem::util::Flex< T >::back

(

)

const

Returns a const reference to the last element in this flex. The reference is valid as long as this flex is not structurally modified.

Precondition

this->size() > 0

Returns

(*this)[ this->size() - 1 ]

template<class T>

Flex& jem::util::Flex< T >::operator=

(

const Flex< T > &

rhs

)

The assignment operator first resizes this flex so that it has the same size as the rhs flex. Next, the values of the elements in the rhs flex are assigned to the elements in this flex by calling the assignment operator of type T.

Parameters

rhs	- the Flex to be copied.

Precondition

The type T has an assignment operator.

Postcondition

this->size() == rhs.size() &&
this->getExpansionFactor() == rhs.getExpansionFactor()

Returns

*this

template<class T>

Flex& jem::util::Flex< T >::operator=

(

T

rhs

)

Sets all elements in this flex to the value rhs by calling the assignment operator of type T.

Parameters

rhs	- an instance of type T.

Precondition

The type T has an assignment operator.

Returns

*this

template<class T>

void jem::util::Flex< T >::swap

(

Flex< T > &

rhs

)

Swaps the internal state of this flex with that of the rhs flex. Note that this function just swaps a few pointers; it does not swap the individual elements.

Parameters

rhs	- a Flex instance.

template<class T>

T& jem::util::Flex< T >::operator[]

(

int

i

)

Returns a reference to the i-th element in this flex. The reference is valid as long as this flex is not structurally modified.

Parameters

i	- a valid index.

Precondition

i >= 0 && i < this->size()

Returns

A reference to the i-th element in this flex.

template<class T>

const T& jem::util::Flex< T >::operator[]

(

int

i

)

const

Returns a const reference to the i-th element in this flex. The reference is valid as long as this flex is not structurally modified.

Parameters

i	- a valid index.

Precondition

i >= 0 && i < this->size()

Returns

A const reference to the i-th element in this flex.

template<class T>

void jem::util::Flex< T >::pushBack

(

T

item

)

Appends a copy of the object item to the end of this flex. The copy is created by calling the copy constructor of type T. The capacity of this flex will be increased if necessary.

The time complexity of this function is O(1), provided that the capacity of this flex is large enough.

Parameters

item	- the object to be appended.

Precondition

The type T has a copy constructor.

Postcondition

this->back() == item

template<class T>

void jem::util::Flex< T >::pushBack	(	T	item,
		int	n
	)

Appends n copies of the object item to the end of this flex. The copies are initialized by calling the copy constructor of type T. The capacity of this flex will be increased if necessary.

The time complexity of this function is O(n), provided that the capacity of this flex is large enough.

Parameters

item	- the object to be copied and appended.
n	- the number of copies to be appended.

Precondition

n >= 0
and the type T has a copy constructor.

template<class T>

template<class InputIterator >

void jem::util::Flex< T >::pushBack	(	InputIterator	first,
		InputIterator	last
	)

Appends copies of the elements between the input iterators first and last to the end of this flex. The copies are initialized by calling the copy constructor of type T. The capacity of this will be increased if necessary.

Provided that the capacity of this flex is large enough, the time complexity of this function is O(n) with n the number elements between the two input iterators.

Parameters

first	- an input iterator pointing to the first element to be appended.
last	- an input iterator pointing one position past the lest element to be appended.

Precondition

The type T has a copy constructor,
and the expression *first can be converted to type T,
and last is reachable from first.

Warning

The iterators first and last should not point to elements in this flex, since this function invalidates all such iterators.

template<class T>

void jem::util::Flex< T >::popBack

(

)

Deletes the last element in this flex by calling the destructor of type T. The capacity of this flex is not modified.

The time complexity of this function is O(1).

Precondition

this->size() > 0

template<class T>

void jem::util::Flex< T >::popBack

(

int

n

)

Deletes the last n elements in this flex by calling the destructor of type T. The capacity of this flex is not modified.

This function is equivalent with:

int i;

for ( i = 0; i < n; i++ ) {
  this->popBack();
}

The time complexity of this function is O(n).

Parameters

n	- the number of elements to be deleted.

Precondition

this->size() >= n

template<class T>

void jem::util::Flex< T >::insert	(	Iterator	pos,
		T	item
	)

Inserts a copy of the object item into this flex before the iterator pos. The copy is initialized by calling the assignent operator of type T. The element pointed to by pos, and all succeeding elements, are shifted one position to the right. The capacity of this flex will be increased is necessary.

If the capacity of this flex is large enough, the time complexity of this function is O(k) with k equal to (end() - pos).

Parameters

pos	- an iterator pointing to an element in this flex, or end().
item	- the object to be inserted.

Precondition

The type T has both a default constructor and an assignment operator.

template<class T>

void jem::util::Flex< T >::insert	(	Iterator	pos,
		T	item,
		int	n
	)

Inserts n copies of the object item into this flex before the iterator pos. The copies are initialized by calling the assignent operator of type T. The element pointed to by pos, and all succeeding elements, are shifted n positions to the right. The capacity of this flex will be increased is necessary.

If the capacity of this flex is sufficient, the time complexity of this function if O(n + k) with k equal to (end() - pos).

Parameters

pos	- an iterator pointing to an element in this flex, or end().
item	- the object to be inserted.
n	- the number of copies to be inserted.

Precondition

The type T has both a default constructor and an assignment operator.

template<class T>

template<class InputIterator >

void jem::util::Flex< T >::insert	(	Iterator	pos,
		InputIterator	first,
		InputIterator	last
	)

Inserts copies of the elements between the input iterators first and last into this flex before the iterator pos. The copies are initialized by calling the assignent operator of type T. The element pointed to by pos, and all succeeding elements, are shifted to the right. The capacity of this flex will be increased is necessary.

If the capacity of this flex is large enough, the time complexity of this function if O(n + k) with n equal to std::distance( first, last ) and k equal to (end() - pos).

Parameters

pos	- an iterator pointing to an element in this flex, or end().
first	- an input iterator pointing to the first element to be inserted.
last	- an input iterator pointing to one position past the last element to be inserted.

Precondition

The type T has both a default constructor and an assignment operator,
and the expression *first can be converted to type T,
and last is reachable from first.

template<class T>

void jem::util::Flex< T >::erase

(

Iterator

pos

)

Deletes the element pointed to by the iterator pos from this flex by calling the destructor of type T. All succeeding elements are shifted one position to the left. The capacity of this flex is not modified.

The time complexity of this function is O(k) with k equal to (end() - pos).

Parameters

pos	- an iterator pointing to an element in this flex, or end().

template<class T>

void jem::util::Flex< T >::erase	(	Iterator	first,
		Iterator	last
	)

Deletes all elements between the iterators first and last from this flex by calling the destructor of type T. All elements succeeding the last deleted element are shifted to the left. The capacity of this flex is not modified.

The time complexity of this function is O(n + k) with n equal to (last - first) and k equal to (end() - pos).

Parameters

first	- an iterator pointing to the first element to be deleted, or end().
last	- an iterator pointing one position past the last element to be deleted, or end().

Precondition

last is reachable from first.

template<class T>

void jem::util::Flex< T >::clear

(

)

Deletes all elements in this flex. The capacity of this flex is not modified.

This function is equivalent with:

erase( begin(), end() )

Postcondition

this->size() == 0

template<class T>

void jem::util::Flex< T >::resize

(

int

n

)

Sets the size of this flex to n. This function is equivalent with:

if ( n < size() )
{
  popBack ( size() - n );
}
else
{
  pushBack ( T(), n - size() );
}

Parameters

n	- the new size of this flex.

Precondition

n >= 0
and the type T has a default constructor.

Postcondition

this->size() == n

template<class T>

void jem::util::Flex< T >::reserve

(

int

cap

)

If cap is larger than the current capacity, then the capacity of this flex is increased to cap. Otherwise, this function does nothing.

Parameters

cap	- the new capacity of this flex.

Postcondition

this->capacity() >= cap

template<class T>

void jem::util::Flex< T >::setExpansionFactor

(

float

x

)

Sets the expansion factor of this flex to the value x.

Parameters

x	- the new expansion factor of this flex.

Precondition

x >= 1.0

Postcondition

this->getExpansionFactor() == x

template<class T>

float jem::util::Flex< T >::getExpansionFactor

(

)

const

Returns the expansion factor of this flex.

Returns

The expansion factor of this flex.

template<class T>

void jem::util::Flex< T >::trimToSize

(

)

Adjusts the capacity so that it becomes equal to the size of this flex.

Postcondition

this->capacity() == this->size()

template<class T>

int jem::util::Flex< T >::capacity

(

)

const

Returns the capacity of this flex.

Returns

The capacity of this flex.

template<class T>

int jem::util::Flex< T >::size

(

)

const

Returns the number of elements stored in this flex.

Returns

The size of this flex.

template<class T>

T* jem::util::Flex< T >::addr

(

int

i = 0

)

Returns a pointer to the i-th element in this flex. The pointer is valid as long as this flex is not structurally modified.

Parameters

i	- a valid index or size().

Precondition

i >= 0 && i <= this->size()

template<class T>

const T* jem::util::Flex< T >::addr

(

int

i = 0

)

const

Returns a const pointer to the i-th element in this flex. The pointer is valid as long as this flex is not structurally modified.

Parameters

i	- a valid index or size().

Precondition

i >= 0 && i <= this->size()

Friends And Related Function Documentation

template<class T >

io::DataInput & operator>> ( io::DataInput &  in, Flex< T > &  f  )

related

Reads the Flex f from the data input stream in. The current contents of the flex f are discarded by calling f.clear().

Parameters

in	- a data input stream.
f	- the flex to be read.

Returns

in

Exceptions

io::IOException	- if an IO error occurs.
io::SerializationException	- if the data input stream is corrupt.

Precondition

The type T provides a de-serialization operator.

template<class T >

io::DataOutput & operator<< ( io::DataOutput &  out, const Flex< T > &  f  )

related

Writes the Flex f to the data output stream out. The de-serialization operator can be used to restore the Flex object.

Parameters

out	- a data output stream.
f	- the flex to be written.

Returns

out

Exceptions

io::IOException

- if an I/O error occurs.

Precondition

The type T provides a serialization operator.

template<class T >

io::TextOutput & operator<< ( io::TextOutput &  out, const Flex< T > &  f  )

related

Prints the contents of the Flex f in a human readable format to the text output stream out.

Parameters

out	- a text output stream.
f	- the flex to be printed.

Returns

out

Exceptions

io::IOException

- if an I/O error occurs.

Precondition

The type T provides a print operator.

template<class T >

void swap ( Flex< T > &  lhs, Flex< T > &  rhs  )

related

Interchanges the state of two Flex objects. This function is equivalent with:

lhs.swap ( rhs )

Parameters

lhs	- a flex.
rhs	- another flex.

Member Data Documentation

template<class T>

const float jem::util::Flex< T >::EXPANSION_FACTOR

static

This floating point constant specifies the default expansion factor of a Flex. Its current value is 1.5, but a different value may be used in a future version of Jem.