atermpp::indexed_set

Include file:

#include "mcrl2/atermpp/indexed_set.h
class atermpp::indexed_set

Indexed set.

Protected attributes

std::stack<std::size_t> free_positions
std::vector<std::size_t> hashtable
std::deque<ELEMENT> m_keys
unsigned int max_load
std::size_t nr_of_insertions_until_next_rehash
std::size_t sizeMinus1

public-static-attrib

const std::size_t npos

A constant that if returned as an index means that the index does not exist.

Protected member functions

std::size_t put_in_hashtable(const ELEMENT &key, std::size_t n)
void resize_hashtable()

Public member functions

void clear()

Clear the hash table in the set. This function clears the hash table in the set, but does not release the memory. Using indexed_set_reset instead of indexed_set_destroy is preferable when indexed sets of approximately the same size are being used.

bool defined(std::size_t index) const

Indicates whether a certain index is defined.

Parameters:

  • index A positive number.

Returns: The element in the set with the given index.

bool erase(const ELEMENT &key)

Remove an element from set.

The element with the indicated key is removed from the indexed set, and if a number was assigned to it, this number is freed to be reassigned to another element, that may be put into the set at some later instance.

Parameters:

  • key The key of the element that is removed.

Returns: whether the element was successfully removed.

const ELEMENT &get(std::size_t index) const

Retrieve the element at index in set. This function must be invoked with a valid index and it returns the elem assigned to this index. If it is invoked with an invalid index, effects are not predictable.

Parameters:

  • index A positive number.

Returns: The element in the set with the given index.

ssize_t index(const ELEMENT &elem) const

Find the index of elem in set. The index assigned to elem is returned, except when elem is not in the set, in which case the return value is indexed_set::npos, i.e. the largest number in std::size_t.

Parameters:

  • elem An element of the set.

Returns: The index of the element.

indexed_set(std::size_t initial_size = 100, unsigned int max_load_pct = 75)

Create a new indexed_set.

Parameters:

  • initial_size The initial capacity of the set.
  • max_load_pct The maximum load percentage.
std::size_t operator[](const ELEMENT &elem)

Find the index of elem in set. The index assigned to elem is returned. When elem is not in the set, it will be added first.

Parameters:

  • elem An element of the set.

Returns: The index of the element.

std::pair<std::size_t, bool> put(const ELEMENT &key)

Enter an element with the indicated key into the set.

This functions enters an element with the indicated key into the set. If elem was already in the set the previously assigned index of key is returned, and the boolean is set to false. If key did not yet occur in set a new number is assigned, and the boolean is set to true. This number can either be the number of an element that has been removed, or, if such a number is not available, the lowest non used number is assigned to elem and returned. The lowest number that is used is 0.

Parameters:

  • key An element to be put in the set.

Returns: A pair denoting the index of the element in the set, and a boolean denoting whether the term was already contained in the set.

std::size_t size() const

Returns the size of the indexed set.