regina::MarkedVector< T > Class Template Reference

A vector of objects with fast, space-efficient reverse lookup of array indices. More...

#include <utilities/markedvector.h>

Inheritance diagram for regina::MarkedVector< T >:

Public Member Functions
	MarkedVector ()=default
	Constructs a new empty vector. More...
	MarkedVector (MarkedVector &&) noexcept=default
	Moves the contents of the given vector into this new vector. More...
MarkedVector &	operator= (MarkedVector &&) noexcept=default
	Moves the contents of the given vector into this vector. More...
const std::vector< T * > &	operator() () const
	Casts this vector to a const std::vector, thus providing access to the entire const functionality of std::vector. More...
void	push_back (T *item)
	Pushes the given item onto the end of this vector. More...
std::vector< T * >::iterator	erase (typename std::vector< T * >::iterator pos)
	Erases the item at the given position in this vector. More...
std::vector< T * >::iterator	erase (typename std::vector< T * >::iterator first, typename std::vector< T * >::iterator last)
	Erases all items in the given range in this vector. More...
void	swap (MarkedVector< T > &other) noexcept
	Swaps the contents of this and the given vector. More...
template<typename Iterator >
void	refill (Iterator begin, Iterator end)
	Empties this vector and refills it with the given range of items. More...
void	clear_destructive ()
	Empties this vector and destroys all of the object that it contains. More...
	MarkedVector (const MarkedVector &)=delete
MarkedVector &	operator= (const MarkedVector &)=delete

Detailed Description

template<typename T>
class regina::MarkedVector< T >

A vector of objects with fast, space-efficient reverse lookup of array indices.

This class derives from std::vector, and so provides fast forward lookups from array indices to objects. What MarkedVector provides in addition to this is fast reverse lookups from objects back to array indices.

The way this class is able to provide fast constant-time reverse lookups without consuming a great deal of space is by storing array indices inside the objects themselves. As a result, there are two significant constraints:

• This class can only store objects derived from MarkedElement (which provides space for storing the array indices and handles their access control). In particular, it cannot store native types such as int or predefined types such as std::string.
• An object can only belong to one MarkedVector at a time. Any attempt to insert an object into more than one MarkedVector at the same time results in undefined behaviour.

Using this class is fairly simple. The class provides a restricted subset of the std::vector functionality, including iterator, const_iterator, begin, end, size, empty, front, back, operator [], reserve, and clear (this subset may grow over time if required). In addition, any const method of std::vector can be accessed through an explicit cast to const std::vector&. To perform a reverse lookup (find the index at which an array is stored), simply call the object's inherited method MarkedElement::markedIndex().

Note that, like its parent std::vector, this class performs no memory management. In particular, elements (which are pointers to real objects) are not destroyed when they are removed from a vector or when the vector is eventually destroyed. This class does, however, provide a convenience method clear_destructive() to assist other code with its memory cleanup.

Since an object can only belong to one MarkedVector at a time, this class does not offer a copy constructor or copy assignment. Instead it supports a move constructor and move assignment, as well as a swap() member function and a global swap() function, all of which preserve this constraint.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Precondition

The type T is a class derived from MarkedElement.

Python

Not present.

Constructor & Destructor Documentation

MarkedVector() [1/2]

template<typename T >

regina::MarkedVector< T >::MarkedVector ( )

default

Constructs a new empty vector.

MarkedVector() [2/2]

template<typename T >

regina::MarkedVector< T >::MarkedVector ( MarkedVector< T > &&  )

defaultnoexcept

Moves the contents of the given vector into this new vector.

The vector that was passed will no longer be usable.

Member Function Documentation

clear_destructive()

template<typename T >

void regina::MarkedVector< T >::clear_destructive ( )

inline

Empties this vector and destroys all of the object that it contains.

This is a convenience method that simply calls delete on each element of the vector, and then calls clear().

erase() [1/2]

template<typename T >

std::vector< T * >::iterator regina::MarkedVector< T >::erase ( typename std::vector< T * >::iterator  first, typename std::vector< T * >::iterator  last  )

inline

Erases all items in the given range in this vector.

The items will not be destroyed, and the (now irrelevant) indices stored inside them will not be modified.

Precondition

The given iterators describe a valid range in this vector.

Parameters

first	an iterator pointing to the first element to erase.
last	an iterator pointing just beyond the last element to erase.

Returns

an iterator pointing to the element immediately after the elements that were erased.

erase() [2/2]

template<typename T >

std::vector< T * >::iterator regina::MarkedVector< T >::erase ( typename std::vector< T * >::iterator  pos )

inline

Erases the item at the given position in this vector.

The item will not be destroyed, and the (now irrelevant) index stored inside it will not be modified.

Precondition

The given iterator points to an element of this vector.

Parameters

pos	an iterator pointing to the element to erase.

Returns

an iterator pointing to the element immediately after the element that was erased.

operator()()

template<typename T >

const std::vector< T * > & regina::MarkedVector< T >::operator() ( ) const

inline

Casts this vector to a const std::vector, thus providing access to the entire const functionality of std::vector.

Returns

a reference to this vector, cast as a const std::vector.

operator=()

template<typename T >

MarkedVector & regina::MarkedVector< T >::operator= ( MarkedVector< T > &&  )

defaultnoexcept

Moves the contents of the given vector into this vector.

The vector that was passed will no longer be usable.

Returns

a reference to this vector.

push_back()

template<typename T >

void regina::MarkedVector< T >::push_back ( T *  item )

inline

Pushes the given item onto the end of this vector.

The array index stored inside item will be modified accordingly.

The caller retains reponsibility for the ownership of item. This class will make no attempt to deallocate item when it is removed or when this vector is eventually destroyed.

Precondition

The given item does not already belong to some other MarkedVector.

Parameters

item	the item to add to this vector.

refill()

template<typename T >

template<typename Iterator >

void regina::MarkedVector< T >::refill ( Iterator  begin, Iterator  end  )

inline

Empties this vector and refills it with the given range of items.

Calling this routine is equivalent to calling clear() followed by push_back() for each item in the range from begin to end. Its implementation, however, is a little more efficient.

The algorithm only makes a single pass through the given range of iterators.

Template Parameters

Iterator

an input iterator type, whose dereference operator returns a pointer of type T*.

Parameters

begin	an iterator that points to the beginning of the range of items with which to refill this vector.
end	an iterator that points past the end of the range of items with which to refill this vector.

swap()

template<typename T >

void regina::MarkedVector< T >::swap ( MarkedVector< T > &  other )

inlinenoexcept

Swaps the contents of this and the given vector.

Parameters

other

the vector whose contents are to be swapped with this.

---

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

• utilities/markedvector.h