regina::NMarkedVector< T > Class Template Reference
Utilities

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

`#include <utilities/nmarkedvector.h>`

Inheritance diagram for regina::NMarkedVector< T >:

## Public Member Functions

| NMarkedVector ()
| Constructs a new empty 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 (NMarkedVector< T > &other)
| Swaps the contents of this and the given vector. More...

## Detailed Description

### template<typename T>
class regina::NMarkedVector< 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 NMarkedVector 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 NMarkedElement (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 NMarkedVector at a time. Any attempt to insert an object into more than one NMarkedVector 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 [], 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 NMarkedElement::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.

Precondition
  The type T is a class derived from NMarkedElement.

Python:
  Not present.

## Constructor & Destructor Documentation

template<typename T>

regina::NMarkedVector< T >::NMarkedVector | ( |  | ) |

inline

Constructs a new empty vector.

## Member Function Documentation

template<typename T>

std::vector<T*>::iterator regina::NMarkedVector< 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.

template<typename T>

std::vector<T*>::iterator regina::NMarkedVector< 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.

template<typename T>

const std::vector<T*>& regina::NMarkedVector< 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.

template<typename T>

void regina::NMarkedVector< 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 NMarkedVector.

Parameters

  item | the item to add to this vector.

template<typename T>

void regina::NMarkedVector< T >::swap | ( | NMarkedVector< T > & | other | ) |

inline

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/nmarkedvector.h

Copyright © 1999-2014, 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@debian.org).