Regina Calculation Engine
Public Member Functions | List of all members
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 ()
 Constructs a new empty vector. More...
 
 MarkedVector (MarkedVector &&) noexcept=default
 Moves the contents of the given vector into this new vector. More...
 
MarkedVectoroperator= (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)
 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...
 
 MarkedVector (const MarkedVector &)=delete
 
MarkedVectoroperator= (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:

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 [], 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.

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() function, all of which preserve this constraint.

Precondition
The type T is a class derived from MarkedElement.
Python:\n Not present.

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

Copyright © 1999-2018, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).