Transients¶

Transients is a concept borrowed from Clojure, with some twists to make it more idiomatic in C++. Essentially, they are a mutable interface built on top of the same data structures that implement the immutable containers under the hood.

These can be useful for performing efficient batch updates or interfacing with standard algorithms.

array_transient¶

template <typename T, typename MemoryPolicy = default_memory_policy>

class immer::array_transient¶

Mutable version of immer::array.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using value_type = T¶

using reference = const T&¶

using size_type = std::size_t¶

using difference_type = std::ptrdiff_t¶

using const_reference = const T&¶

using iterator = const T *¶

using const_iterator = iterator ¶

using reverse_iterator = std::reverse_iterator<iterator>¶

using memory_policy = MemoryPolicy¶

using persistent_type = array<T, MemoryPolicy>¶

Public Functions

array_transient()¶: Default constructor. It creates a mutable array of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

reverse_iterator rbegin() const¶: Returns an iterator that traverses the collection backwards, pointing at the first element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

reverse_iterator rend() const¶: Returns an iterator that traverses the collection backwards, pointing after the last element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

std::size_t size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

const T *data() const¶: Access the raw data.

T *data_mut()¶: Provide mutable access to the raw underlaying data.

const T &back() const¶: Access the last element.

const T &front() const¶: Access the first element.

reference operator[](size_type index) const¶: Returns a const reference to the element at position index. It is undefined when \( 0 index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

reference at(size_type index) const¶: Returns a const reference to the element at position index. It throws an std::out_of_range exception when \( index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

void push_back(value_type value)¶: Inserts value at the end. It may allocate memory and its complexity is effectively \( O(1) \).

void set(size_type index, value_type value)¶: Sets to the value value at position idx. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

template <typename FnT>
void update(size_type index, FnT &&fn)¶: Updates the array to contain the result of the expression fn((*this)[idx]) at position idx. Undefined for 0 >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

void take(size_type elems)¶: Resizes the array to only contain the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

persistent_type persistent()¶: Returns an immutable form of this container, an immer::array.

persistent_type persistent()¶

vector_transient¶

template <typename T, typename MemoryPolicy = default_memory_policy, detail::rbts::bits_t B = default_bits, detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>

class immer::vector_transient¶

Mutable version of immer::vector.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using memory_policy = MemoryPolicy¶

using value_type = T¶

using reference = const T&¶

using size_type = detail::rbts::size_t¶

using difference_type = std::ptrdiff_t¶

using const_reference = const T&¶

using iterator = detail::rbts::rbtree_iterator<T, MemoryPolicy, B, BL>¶

using const_iterator = iterator ¶

using reverse_iterator = std::reverse_iterator<iterator>¶

using persistent_type = vector<T, MemoryPolicy, B, BL>¶

Public Functions

vector_transient()¶: Default constructor. It creates a mutable vector of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

reverse_iterator rbegin() const¶: Returns an iterator that traverses the collection backwards, pointing at the first element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

reverse_iterator rend() const¶: Returns an iterator that traverses the collection backwards, pointing after the last element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

size_type size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

reference operator[](size_type index) const¶: Returns a const reference to the element at position index. It is undefined when \( 0 index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

reference at(size_type index) const¶: Returns a const reference to the element at position index. It throws an std::out_of_range exception when \( index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

void push_back(value_type value)¶: Inserts value at the end. It may allocate memory and its complexity is effectively \( O(1) \).

void set(size_type index, value_type value)¶: Sets to the value value at position idx. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

template <typename FnT>
void update(size_type index, FnT &&fn)¶: Updates the vector to contain the result of the expression fn((*this)[idx]) at position idx. Undefined for 0 >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

void take(size_type elems)¶: Resizes the vector to only contain the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

persistent_type persistent()¶: Returns an immutable form of this container, an immer::vector.

persistent_type persistent()¶

Public Static Attributes

constexpr auto bits = B¶

constexpr auto bits_leaf = BL¶

flex_vector_transient¶

template <typename T, typename MemoryPolicy = default_memory_policy, detail::rbts::bits_t B = default_bits, detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>

class immer::flex_vector_transient¶

Mutable version of immer::flex_vector.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using memory_policy = MemoryPolicy¶

using value_type = T¶

using reference = const T&¶

using size_type = detail::rbts::size_t¶

using difference_type = std::ptrdiff_t¶

using const_reference = const T&¶

using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>¶

using const_iterator = iterator ¶

using reverse_iterator = std::reverse_iterator<iterator>¶

using persistent_type = flex_vector<T, MemoryPolicy, B, BL>¶

Public Functions

flex_vector_transient()¶: Default constructor. It creates a flex_vector of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

flex_vector_transient(vector_transient<T, MemoryPolicy, B, BL> v)¶: Default constructor. It creates a flex_vector with the same contents as v. It does not allocate memory and is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

reverse_iterator rbegin() const¶: Returns an iterator that traverses the collection backwards, pointing at the first element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

reverse_iterator rend() const¶: Returns an iterator that traverses the collection backwards, pointing after the last element of the reversed collection. It does not allocate memory and its complexity is \( O(1) \).

size_type size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

reference operator[](size_type index) const¶: Returns a const reference to the element at position index. It is undefined when \( 0 index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

reference at(size_type index) const¶: Returns a const reference to the element at position index. It throws an std::out_of_range exception when \( index \geq size() \). It does not allocate memory and its complexity is effectively \( O(1) \).

void push_back(value_type value)¶: Inserts value at the end. It may allocate memory and its complexity is effectively \( O(1) \).

void set(size_type index, value_type value)¶: Sets to the value value at position idx. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

template <typename FnT>
void update(size_type index, FnT &&fn)¶: Updates the vector to contain the result of the expression fn((*this)[idx]) at position idx. Undefined for 0 >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

void take(size_type elems)¶: Resizes the vector to only contain the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

void drop(size_type elems)¶: Removes the first the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

void append(flex_vector_transient &r)¶: Appends the contents of the r at the end. It may allocate memory and its complexity is: \( O(log(max(size_r, size_l))) \)

void append(flex_vector_transient &&r)¶

void prepend(flex_vector_transient &l)¶: Prepends the contents of the l at the beginning. It may allocate memory and its complexity is: \( O(log(max(size_r, size_l))) \)

void prepend(flex_vector_transient &&l)¶

persistent_type persistent()¶: Returns an immutable form of this container, an immer::flex_vector.

persistent_type persistent()¶

Public Static Attributes

constexpr auto bits = B¶

constexpr auto bits_leaf = BL¶

set_transient¶

template <typename T, typename Hash = std::hash<T>, typename Equal = std::equal_to<T>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

class immer::set_transient¶

Mutable version of immer::set.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using persistent_type = set<T, Hash, Equal, MemoryPolicy, B>¶

using value_type = T¶

using size_type = detail::hamts::size_t¶

using difference_type = std::ptrdiff_t¶

using hasher = Hash¶

using key_equal = Equal¶

using reference = const T&¶

using const_reference = const T&¶

using iterator = typename persistent_type::iterator¶

using const_iterator = iterator ¶

Public Functions

set_transient()¶: Default constructor. It creates a set of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

size_type size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

template <typename K, typename U = Hash, typename = typename U::is_transparent>

size_type count(const K &value) const¶

Returns 1 when value is contained in the set or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

size_type count(const T &value) const¶: Returns 1 when value is contained in the set or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

const T *find(const T &value) const¶: Returns a pointer to the value if value is contained in the set, or nullptr otherwise. It does not allocate memory and its complexity is effectively \( O(1) \).

template <typename K, typename U = Hash, typename = typename U::is_transparent>

const T *find(const K &value) const¶

Returns a pointer to the value if value is contained in the set, or nullptr otherwise. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

void insert(T value)¶: Inserts value into the set, and does nothing if the value is already there It may allocate memory and its complexity is effectively \( O(1) \).

void erase(const T &value)¶: Removes the value from the set, doing nothing if the value is not in the set. It may allocate memory and its complexity is effectively \( O(1) \).

persistent_type persistent()¶: Returns an immutable form of this container, an immer::set.

persistent_type persistent()¶

const impl_t &impl() const¶

map_transient¶

template <typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

class immer::map_transient¶

Mutable version of immer::map.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using persistent_type = map<K, T, Hash, Equal, MemoryPolicy, B>¶

using key_type = K¶

using mapped_type = T¶

using value_type = std::pair<K, T>¶

using size_type = detail::hamts::size_t¶

using difference_type = std::ptrdiff_t¶

using hasher = Hash¶

using key_equal = Equal¶

using reference = const value_type&¶

using const_reference = const value_type&¶

using iterator = typename persistent_type::iterator¶

using const_iterator = iterator ¶

Public Functions

map_transient()¶: Default constructor. It creates a map of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

size_type size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

size_type count(const Key &k) const¶

Returns 1 when the key k is contained in the map or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

size_type count(const K &k) const¶: Returns 1 when the key k is contained in the map or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

const T &operator[](const Key &k) const¶

Returns a const reference to the values associated to the key k. If the key is not contained in the map, it returns a default constructed value. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

const T &operator[](const K &k) const¶: Returns a const reference to the values associated to the key k. If the key is not contained in the map, it returns a default constructed value. It does not allocate memory and its complexity is effectively \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>
const T &at(const Key &k) const¶: Returns a const reference to the values associated to the key k. If the key is not contained in the map, throws an std::out_of_range error. It does not allocate memory and its complexity is effectively \( O(1) \).

const T &at(const K &k) const¶

Returns a const reference to the values associated to the key k. If the key is not contained in the map, throws an std::out_of_range error. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

const T *find(const K &k) const¶

Returns a pointer to the value associated with the key k. If the key is not contained in the map, a nullptr is returned. It does not allocate memory and its complexity is effectively \( O(1) \).

Why doesn’t this function return an iterator?

Associative containers from the C++ standard library provide a find method that returns an iterator pointing to the element in the container or end() when the key is missing. In the case of an unordered container, the only meaningful thing one may do with it is to compare it with the end, to test if the find was succesfull, and dereference it. This comparison is cumbersome compared to testing for a non-empty optional value. Furthermore, for an immutable container, returning an iterator would have some additional performance cost, with no benefits otherwise.

In our opinion, this function should return a std::optional<const T&> but this construction is not valid in any current standard. As a compromise we return a pointer, which has similar syntactic properties yet it is unfortunately unnecessarily unrestricted.

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

const T *find(const Key &k) const¶

Returns a pointer to the value associated with the key k. If the key is not contained in the map, a nullptr is returned. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

void insert(value_type value)¶: Inserts the association value. If the key is already in the map, it replaces its association in the map. It may allocate memory and its complexity is effectively \( O(1) \).

void set(key_type k, mapped_type v)¶: Inserts the association (k, v). If the key is already in the map, it replaces its association in the map. It may allocate memory and its complexity is effectively \( O(1) \).

template <typename Fn>
void update(key_type k, Fn &&fn)¶: Replaces the association (k, v) by the association new association (k, fn(v)), where v is the currently associated value for k in the map or a default constructed value otherwise. It may allocate memory and its complexity is effectively \( O(1) \).

template <typename Fn>
void update_if_exists(key_type k, Fn &&fn)¶: Replaces the association (k, v) by the association new association (k, fn(v)), where v is the currently associated value for k in the map or does nothing if k is not present in the map. It may allocate memory and its complexity is effectively \( O(1) \).

void erase(const K &k)¶: Removes the key k from the k. Does nothing if the key is not associated in the map. It may allocate memory and its complexity is effectively \( O(1) \).

persistent_type persistent()¶: Returns an immutable form of this container, an immer::map.

persistent_type persistent()¶

const impl_t &impl() const¶

table_transient¶

template <typename T, typename KeyFn, typename Hash, typename Equal, typename MemoryPolicy, detail::hamts::bits_t B>

class immer::table_transient¶

Mutable version of immer::table.

Refer to Transients to learn more about when and how to use the mutable versions of immutable containers.

Public Types

using persistent_type = table<T, KeyFn, Hash, Equal, MemoryPolicy, B>¶

using key_type = K¶

using mapped_type = T¶

using value_type = T¶

using size_type = detail::hamts::size_t¶

using difference_type = std::ptrdiff_t¶

using hasher = Hash¶

using key_equal = Equal¶

using reference = const value_type&¶

using const_reference = const value_type&¶

using iterator = typename persistent_type::iterator¶

using const_iterator = iterator ¶

Public Functions

table_transient()¶: Default constructor. It creates a table of size() == 0. It does not allocate memory and its complexity is \( O(1) \).

iterator begin() const¶: Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is \( O(1) \).

iterator end() const¶: Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is \( O(1) \).

size_type size() const¶: Returns the number of elements in the container. It does not allocate memory and its complexity is \( O(1) \).

bool empty() const¶: Returns true if there are no elements in the container. It does not allocate memory and its complexity is \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

size_type count(const Key &k) const¶

Returns 1 when the key k is contained in the table or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

size_type count(const K &k) const¶: Returns 1 when the key k is contained in the table or 0 otherwise. It won’t allocate memory and its complexity is effectively \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

const T &operator[](const Key &k) const¶

Returns a const reference to the values associated to the key k. If there is no entry with such a key in the table, it returns a default constructed value. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

const T &operator[](const K &k) const¶: Returns a const reference to the values associated to the key k. If there is no entry with such a key in the table, it returns a default constructed value. It does not allocate memory and its complexity is effectively \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

const T &at(const Key &k) const¶

Returns a const reference to the values associated to the key k. If there is no entry with such a key in the table, throws an std::out_of_range error. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

const T &at(const K &k) const¶: Returns a const reference to the values associated to the key k. If there is no entry with such a key in the table, throws an std::out_of_range error. It does not allocate memory and its complexity is effectively \( O(1) \).

const T *find(const K &k) const¶: Returns a pointer to the value associated with the key k. If there is no entry with such a key in the table, a nullptr is returned. It does not allocate memory and its complexity is effectively \( O(1) \).

template <typename Key, typename U = Hash, typename = typename U::is_transparent>

const T *find(const Key &k) const¶

Returns a pointer to the value associated with the key k. If there is no entry with such a key in the table, a nullptr is returned. It does not allocate memory and its complexity is effectively \( O(1) \).

This overload participates in overload resolution only if Hash::is_transparent is valid and denotes a type.

void insert(value_type value)¶: Inserts value to the table. If there is an entry with its key is already, it replaces this entry by value. It may allocate memory and its complexity is effectively \( O(1) \).

template <typename Fn>
void update(key_type k, Fn &&fn)¶: Returns this->insert(fn((*this)[k])). In particular, fn maps T to T. The key k will be set into the value returned bu fn. It may allocate memory and its complexity is effectively \( O(1) \).

template <typename Fn>
void update_if_exists(key_type k, Fn &&fn)¶: Returns this->insert(fn((*this)[k])) when this->count(k) > 0. In particular, fn maps T to T. The key k will be replaced into the value returned by fn. It may allocate memory and its complexity is effectively \( O(1) \).

void erase(const K &k)¶: Removes table entry by given key k if there is any. It may allocate memory and its complexity is effectively \( O(1) \).

persistent_type persistent()¶: Returns an immutable form of this container, an immer::table.

persistent_type persistent()¶: Returns an immutable form of this container, an immer::table.

const impl_t &impl() const¶