Containers¶

This section describes all the containers provided by the library. Check the Design section for a general discussion of these containers and how to use them.

box¶

template <typename T, typename MemoryPolicy = default_memory_policy>

class immer::box¶

Immutable box for a single value of type T.

The box is always copiable and movable. The T copy or move operations are never called. Since a box is immutable, copying or moving just copy the underlying pointers.

Public Types

using value_type = T¶

using memory_policy = MemoryPolicy¶

Public Functions

const holder *impl() const¶

box()¶: Constructs a box holding T{}.

template <typename Arg, typename Enable = std::enable_if_t< !std::is_same<box, std::decay_t<Arg>>::value>>
box(Arg &&arg)¶: Constructs a box holding T{arg}

template <typename Arg1, typename Arg2, typename… Args>
box(Arg1 &&arg1, Arg2 &&arg2, Args&&... args)¶: Constructs a box holding T{arg1, arg2, args...}

box(box &&other)¶

box(const box &other)¶

box &operator=(box &&other)¶

box &operator=(const box &other)¶

~box()¶

const T &get() const¶: Query the current value.

operator const T&() const¶: Conversion to the boxed type.

const T &operator*() const¶: Access via dereference

const T *operator->() const¶: Access via pointer member access

template <typename Fn>

box update(Fn &&fn) const¶

Returns a new box built by applying the fn to the underlying value.

Example

auto v1 = immer::box<std::string>{"hello"};
auto v2 = v1.update([&](auto l) { return l + ", world!"; });

assert((v1 == immer::box<std::string>{"hello"}));
assert((v2 == immer::box<std::string>{"hello, world!"}));

template <typename Fn>
box &&update(Fn &&fn)¶

Friends

friend immer::box::detail::gc_atom_impl< T, MemoryPolicy >

friend immer::box::detail::refcount_atom_impl< T, MemoryPolicy >

void swap(box &a, box &b)¶

array¶

template <typename T, typename MemoryPolicy = default_memory_policy>

class immer::array¶

Immutable container that stores a sequence of elements in contiguous memory.

It supports the most efficient iteration and random access, equivalent to a std::vector or std::array, but all manipulations are \(O(size)\).

Tip

Don’t be fooled by the bad complexity of this data structure. It is a great choice for short sequence or when it is seldom or never changed. This depends on the sizeof(T) and the expensiveness of its T’s copy constructor. In case of doubt, measure. For basic types, using an array when \(n < 100\) is a good heuristic.

Template Parameters

T: The type of the values to be stored in the container.

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 transient_type = array_transient<T, MemoryPolicy>¶

Public Functions

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

array(std::initializer_list<T> values)¶: Constructs an array containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent > && detail::is_forward_iterator_v< Iter >, bool > = true>
array(Iter first, Sent last)¶: Constructs a array containing the elements in the range defined by the forward iterator first and range sentinel last.

array(size_type n, T v = {})¶: Constructs an array containing the element val repeated n times.

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 memory 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.

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 \( 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) \).

bool operator==(const array &other) const¶: Returns whether the vectors are equal.

bool operator!=(const array &other) const¶

array push_back(value_type value) const¶

Returns an array with value inserted at the end. It may allocate memory and its complexity is \( O(size) \).

Example

auto v1 = immer::array<int>{1};
auto v2 = v1.push_back(8);

assert((v1 == immer::array<int>{1}));
assert((v2 == immer::array<int>{1, 8}));

decltype(auto) immer::array::push_back(value_type value)

array set(std::size_t index, value_type value) const¶

Returns an array containing value value at position idx. Undefined for index >= size(). It may allocate memory and its complexity is \( O(size) \).

Example

auto v1 = immer::array<int>{1, 2, 3};
auto v2 = v1.set(0, 5);

assert((v1 == immer::array<int>{1, 2, 3}));
assert((v2 == immer::array<int>{5, 2, 3}));

decltype(auto) immer::array::set(size_type index, value_type value)

template <typename FnT>

array update(std::size_t index, FnT &&fn) const¶

Returns an array containing the result of the expression fn((*this)[idx]) at position idx. Undefined for index >= size(). It may allocate memory and its complexity is \( O(size) \).

Example

auto v1 = immer::array<int>{1, 2, 3, 4};
auto v2 = v1.update(2, [&](auto l) { return ++l; });

assert((v1 == immer::array<int>{1, 2, 3, 4}));
assert((v2 == immer::array<int>{1, 2, 4, 4}));

template <typename FnT>
decltype(auto) immer::array::update(size_type index, FnT && fn)

array take(size_type elems) const¶

Returns a array containing only the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::array<int>{1, 2, 3, 4, 5, 6};
auto v2 = v1.take(3);

assert((v1 == immer::array<int>{1, 2, 3, 4, 5, 6}));
assert((v2 == immer::array<int>{1, 2, 3}));

decltype(auto) immer::array::take(size_type elems)

transient_type transient() const¶: Returns an transient form of this container, an immer::array_transient.

transient_type transient()¶

void *identity() const¶: Returns a value that can be used as identity for the container. If two values have the same identity, they are guaranteed to be equal and to contain the same objects. However, two equal containers are not guaranteed to have the same identity.

const impl_t &impl() const¶

vector¶

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¶

Immutable sequential container supporting both random access and structural sharing.

This container provides a good trade-off between cache locality, random access, update performance and structural sharing. It does so by storing the data in contiguous chunks of \(2^{BL}\) elements. By default, when sizeof(T) == sizeof(void*) then \(B=BL=5\), such that data would be stored in contiguous chunks of \(32\) elements.

You may learn more about the meaning and implications of B and BL parameters in the Implementation overview section.

Note

In several methods we say that their complexity is effectively \(O(...)\). Do not confuse this with the word amortized, which has a very different meaning. In this context, effective means that while the mathematically rigurous complexity might be higher, for all practical matters the provided complexity is more useful to think about the actual cost of the operation.

Example

#include <immer/vector.hpp>
int main()
{
    const auto v0 = immer::vector<int>{};
    const auto v1 = v0.push_back(13);
    assert((v0 == immer::vector<int>{}));
    assert((v1 == immer::vector<int>{13}));

    const auto v2 = v1.set(0, 42);
    assert(v1[0] == 13);
    assert(v2[0] == 42);
}

Template Parameters

T: The type of the values to be stored in the container.
MemoryPolicy: Memory management policy. See memory_policy.

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 transient_type = vector_transient<T, MemoryPolicy, B, BL>¶

Public Functions

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

vector(std::initializer_list<T> values)¶: Constructs a vector containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent >, bool > = true>
vector(Iter first, Sent last)¶: Constructs a vector containing the elements in the range defined by the input iterator first and range sentinel last.

vector(size_type n, T v = {})¶: Constructs a vector containing the element val repeated n times.

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) \).

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) \).

bool operator==(const vector &other) const¶: Returns whether the vectors are equal.

bool operator!=(const vector &other) const¶

vector push_back(value_type value) const¶

Returns a vector with value inserted at the end. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::vector<int>{1};
auto v2 = v1.push_back(8);

assert((v1 == immer::vector<int>{1}));
assert((v2 == immer::vector<int>{1, 8}));

decltype(auto) immer::vector::push_back(value_type value)

vector set(size_type index, value_type value) const¶

Returns a vector containing value value at position idx. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::vector<int>{1, 2, 3};
auto v2 = v1.set(0, 5);

assert((v1 == immer::vector<int>{1, 2, 3}));
assert((v2 == immer::vector<int>{5, 2, 3}));

decltype(auto) immer::vector::set(size_type index, value_type value)

template <typename FnT>

vector update(size_type index, FnT &&fn) const¶

Returns a vector containing 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) \).

Example

auto v1 = immer::vector<int>{1, 2, 3, 4};
auto v2 = v1.update(2, [&](auto l) { return ++l; });

assert((v1 == immer::vector<int>{1, 2, 3, 4}));
assert((v2 == immer::vector<int>{1, 2, 4, 4}));

template <typename FnT>
decltype(auto) immer::vector::update(size_type index, FnT && fn)

vector take(size_type elems) const¶

Returns a vector containing only the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::vector<int>{1, 2, 3, 4, 5, 6};
auto v2 = v1.take(3);

assert((v1 == immer::vector<int>{1, 2, 3, 4, 5, 6}));
assert((v2 == immer::vector<int>{1, 2, 3}));

decltype(auto) immer::vector::take(size_type elems)

transient_type transient() const¶: Returns an transient form of this container, an immer::vector_transient.

transient_type transient()¶

std::pair<void *, void *> identity() const¶: Returns a value that can be used as identity for the container. If two values have the same identity, they are guaranteed to be equal and to contain the same objects. However, two equal containers are not guaranteed to have the same identity.

const impl_t &impl() const¶

Public Static Functions

static constexpr size_type max_size()¶: Returns the maximum theoretical size supported by the internal structure given the current B, BL.

Public Static Attributes

constexpr auto bits = B¶

constexpr auto bits_leaf = BL¶

flex_vector¶

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¶

Immutable sequential container supporting both random access, structural sharing and efficient concatenation and slicing.

This container is very similar to vector but also supports \(O(log(size))\) concatenation, slicing and insertion at any point. Its performance characteristics are almost identical until one of these operations is performed. After that, performance is degraded by a constant factor that usually oscilates in the range \([1, 2)\) depending on the operation and the amount of flexible operations that have been performed.

Tip

A vector can be converted to a flex_vector in constant time without any allocation. This is so because the internal structure of a vector is a strict subset of the internal structure of a flexible vector. You can take advantage of this property by creating normal vectors as long as the flexible operations are not needed, and convert later in your processing pipeline once and if these are needed.

Template Parameters

T: The type of the values to be stored in the container.
MemoryPolicy: Memory management policy. See memory_policy.

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 transient_type = flex_vector_transient<T, MemoryPolicy, B, BL>¶

Public Functions

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

flex_vector(std::initializer_list<T> values)¶: Constructs a flex_vector containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent >, bool > = true>
flex_vector(Iter first, Sent last)¶: Constructs a flex_vector containing the elements in the range defined by the input iterator first and range sentinel last.

flex_vector(size_type n, T v = {})¶: Constructs a vector containing the element val repeated n times.

flex_vector(vector<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) \).

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) \).

bool operator==(const flex_vector &other) const¶: Returns whether the vectors are equal.

bool operator!=(const flex_vector &other) const¶

flex_vector push_back(value_type value) const¶

Returns a flex_vector with value inserted at the end. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::flex_vector<int>{1};
auto v2 = v1.push_back(8);

assert((v1 == immer::flex_vector<int>{1}));
assert((v2 == immer::flex_vector<int>{1, 8}));

decltype(auto) immer::flex_vector::push_back(value_type value)

flex_vector push_front(value_type value) const¶

Returns a flex_vector with value inserted at the front. It may allocate memory and its complexity is \( O(log(size)) \).

Example

auto v1 = immer::flex_vector<int>{1};
auto v2 = v1.push_front(8);

assert((v1 == immer::flex_vector<int>{1}));
assert((v2 == immer::flex_vector<int>{8, 1}));

flex_vector set(size_type index, value_type value) const¶

Returns a flex_vector containing value value at position index. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::flex_vector<int>{1, 2, 3};
auto v2 = v1.set(0, 5);

assert((v1 == immer::flex_vector<int>{1, 2, 3}));
assert((v2 == immer::flex_vector<int>{5, 2, 3}));

decltype(auto) immer::flex_vector::set(size_type index, value_type value)

template <typename FnT>

flex_vector update(size_type index, FnT &&fn) const¶

Returns a vector containing the result of the expression fn((*this)[idx]) at position idx. Undefined for index >= size(). It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::flex_vector<int>{1, 2, 3, 4};
auto v2 = v1.update(2, [&](auto l) { return ++l; });

assert((v1 == immer::flex_vector<int>{1, 2, 3, 4}));
assert((v2 == immer::flex_vector<int>{1, 2, 4, 4}));

template <typename FnT>
decltype(auto) immer::flex_vector::update(size_type index, FnT && fn)

flex_vector take(size_type elems) const¶

Returns a vector containing only the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5, 6};
auto v2 = v1.take(3);

assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5, 6}));
assert((v2 == immer::flex_vector<int>{1, 2, 3}));

decltype(auto) immer::flex_vector::take(size_type elems)

flex_vector drop(size_type elems) const¶

Returns a vector without the first min(elems, size()) elements. It may allocate memory and its complexity is effectively \( O(1) \).

Example

auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5, 6};
auto v2 = v1.drop(3);

assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5, 6}));
assert((v2 == immer::flex_vector<int>{4, 5, 6}));

decltype(auto) immer::flex_vector::drop(size_type elems)

decltype(auto) friend immer::flex_vector::operator+(flex_vector && l, const flex_vector & r)

decltype(auto) friend immer::flex_vector::operator+(const flex_vector & l, flex_vector && r)

decltype(auto) friend immer::flex_vector::operator+(flex_vector && l, flex_vector && r)

flex_vector insert(size_type pos, T value) const¶

Returns a flex_vector with the value inserted at index pos. It may allocate memory and its complexity is \( O(log(size)) \)

Example

auto v1 = immer::flex_vector<int>{1, 2, 3};
auto v2 = v1.insert(0, 0);

assert((v1 == immer::flex_vector<int>{1, 2, 3}));
assert((v2 == immer::flex_vector<int>{0, 1, 2, 3}));

decltype(auto) immer::flex_vector::insert(size_type pos, T value)

flex_vector insert(size_type pos, flex_vector value) const¶

decltype(auto) immer::flex_vector::insert(size_type pos, flex_vector value)

flex_vector erase(size_type pos) const¶

Returns a flex_vector without the element at index pos. It may allocate memory and its complexity is \( O(log(size)) \)

Example

auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5};
auto v2 = v1.erase(2);

assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5}));
assert((v2 == immer::flex_vector<int>{1, 2, 4, 5}));

decltype(auto) immer::flex_vector::erase(size_type pos)

flex_vector erase(size_type pos, size_type lpos) const¶

decltype(auto) immer::flex_vector::erase(size_type pos, size_type lpos)

transient_type transient() const¶: Returns an transient form of this container, an immer::flex_vector_transient.

transient_type transient()¶

std::pair<void *, void *> identity() const¶: Returns a value that can be used as identity for the container. If two values have the same identity, they are guaranteed to be equal and to contain the same objects. However, two equal containers are not guaranteed to have the same identity.

const impl_t &impl() const¶

Public Static Functions

static constexpr size_type max_size()¶: Returns the maximum theoretical size supported by the internal structure given the current B, BL.

Public Static Attributes

constexpr auto bits = B¶

constexpr auto bits_leaf = BL¶

Friends

flex_vector operator+(const flex_vector &l, const flex_vector &r)¶

Concatenation operator. Returns a flex_vector with the contents of l followed by those of r. It may allocate memory and its complexity is \( O(log(max(size_r, size_l))) \)

Example

auto v1 = immer::flex_vector<int>{1, 2, 3};
auto v2 = v1 + v1;

assert((v1 == immer::flex_vector<int>{1, 2, 3}));
assert((v2 == immer::flex_vector<int>{1, 2, 3, 1, 2, 3}));

set¶

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¶

Immutable set representing an unordered bag of values.

This container provides a good trade-off between cache locality, membership checks, update performance and structural sharing. It does so by storing the data in contiguous chunks of \(2^{B}\) elements. When storing big objects, the size of these contiguous chunks can become too big, damaging performance. If this is measured to be problematic for a specific use-case, it can be solved by using a immer::box to wrap the type T.

Example

#include <immer/set.hpp>
int main()
{
    const auto v0 = immer::set<int>{};
    const auto v1 = v0.insert(42);
    assert(v0.count(42) == 0);
    assert(v1.count(42) == 1);

    const auto v2 = v1.erase(42);
    assert(v1.count(42) == 1);
    assert(v2.count(42) == 0);
}

Template Parameters

T: The type of the values to be stored in the container.
Hash: The type of a function object capable of hashing values of type T.
Equal: The type of a function object capable of comparing values of type T.
MemoryPolicy: Memory management policy. See memory_policy.

Public Types

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 = detail::hamts::champ_iterator<T, Hash, Equal, MemoryPolicy, B>¶

using const_iterator = iterator ¶

using transient_type = set_transient<T, Hash, Equal, MemoryPolicy, B>¶

using memory_policy_type = MemoryPolicy¶

Public Functions

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

set(std::initializer_list<value_type> values)¶: Constructs a set containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent >, bool > = true>
set(Iter first, Sent last)¶: Constructs a set containing the elements in the range defined by the input iterator first and range sentinel last.

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.

bool operator==(const set &other) const¶: Returns whether the sets are equal.

bool operator!=(const set &other) const¶

set insert(T value) const¶: Returns a set containing value. If the value is already in the set, it returns the same set. It may allocate memory and its complexity is effectively \( O(1) \).

decltype(auto) immer::set::insert(T value)

set erase(const T &value) const¶: Returns a set without value. If the value is not in the set it returns the same set. It may allocate memory and its complexity is effectively \( O(1) \).

decltype(auto) immer::set::erase(const T & value)

transient_type transient() const¶: Returns an transient form of this container, a immer::set_transient.

transient_type transient()¶

void *identity() const¶: Returns a value that can be used as identity for the container. If two values have the same identity, they are guaranteed to be equal and to contain the same objects. However, two equal containers are not guaranteed to have the same identity.

const impl_t &impl() const¶

map¶

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¶

Immutable unordered mapping of values from type K to type T.

This container provides a good trade-off between cache locality, search, update performance and structural sharing. It does so by storing the data in contiguous chunks of \(2^{B}\) elements. When storing big objects, the size of these contiguous chunks can become too big, damaging performance. If this is measured to be problematic for a specific use-case, it can be solved by using a immer::box to wrap the type T.

Example

#include <immer/map.hpp>
int main()
{
    const auto v0 = immer::map<std::string, int>{};
    const auto v1 = v0.set("hello", 42);
    assert(v0["hello"] == 0);
    assert(v1["hello"] == 42);

    const auto v2 = v1.erase("hello");
    assert(*v1.find("hello") == 42);
    assert(!v2.find("hello"));
}

Template Parameters

K: The type of the keys.
T: The type of the values to be stored in the container.
Hash: The type of a function object capable of hashing values of type T.
Equal: The type of a function object capable of comparing values of type T.
MemoryPolicy: Memory management policy. See memory_policy.

Public Types

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 = detail::hamts::champ_iterator<value_t, hash_key, equal_key, MemoryPolicy, B>¶

using const_iterator = iterator ¶

using transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>¶

using memory_policy_type = MemoryPolicy¶

Public Functions

map(std::initializer_list<value_type> values)¶: Constructs a map containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent >, bool > = true>
map(Iter first, Sent last)¶: Constructs a map containing the elements in the range defined by the input iterator first and range sentinel last.

map()¶: 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.

bool operator==(const map &other) const¶: Returns whether the maps are equal.

bool operator!=(const map &other) const¶

map insert(value_type value) const¶: Returns a map containing 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) \).

decltype(auto) immer::map::insert(value_type value)

map set(key_type k, mapped_type v) const¶: Returns a map containing 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) \).

decltype(auto) immer::map::set(key_type k, mapped_type v)

template <typename Fn>
map update(key_type k, Fn &&fn) const¶: Returns a map replacing 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>
decltype(auto) immer::map::update(key_type k, Fn && fn)

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

template <typename Fn>
decltype(auto) immer::map::update_if_exists(key_type k, Fn && fn)

map erase(const K &k) const¶: Returns a map without the key k. If the key is not associated in the map it returns the same map. It may allocate memory and its complexity is effectively \( O(1) \).

decltype(auto) immer::map::erase(const K & k)

transient_type transient() const¶: Returns a transient form of this container, an immer::map_transient.

transient_type transient()¶

void *identity() const¶: Returns a value that can be used as identity for the container. If two values have the same identity, they are guaranteed to be equal and to contain the same objects. However, two equal containers are not guaranteed to have the same identity.

const impl_t &impl() const¶

table¶

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

class immer::table¶

Immutable unordered set of values of type T. Values are indexed via operator()(const T&) from KeyFn template parameter. By default, key is &T::id.

This container is based on the immer::map underlying data structure.

This container provides a good trade-off between cache locality, search, update performance and structural sharing. It does so by storing the data in contiguous chunks of \(2^{B}\) elements. When storing big objects, the size of these contiguous chunks can become too big, damaging performance. If this is measured to be problematic for a specific use-case, it can be solved by using a immer::box to wrap the type T.

Example

#include <immer/table.hpp>

int main()
{
    struct Item
    {
        std::string id;
        int value;
    };

    const auto v0 = immer::table<Item>{};
    const auto v1 = v0.insert({"hello", 42});
    assert(v0["hello"].value == 0);
    assert(v1["hello"].value == 42);

    const auto v2 = v1.erase("hello");
    assert(v1.find("hello")->value == 42);
    assert(!v2.find("hello"));
}

Template Parameters

T: The type of the values to be stored in the container.
KeyFn: Type which implements operator()(const T&)
Hash: The type of a function object capable of hashing values of type T.
Equal: The type of a function object capable of comparing values of type T.
MemoryPolicy: Memory management policy. See memory_policy.

Public Types

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 = detail::hamts::champ_iterator<value_t, hash_key, equal_key, MemoryPolicy, B>¶

using const_iterator = iterator ¶

using transient_type = table_transient<T, KeyFn, Hash, Equal, MemoryPolicy, B>¶

using memory_policy_type = MemoryPolicy¶

Public Functions

table(std::initializer_list<value_type> values)¶: Constructs a table containing the elements in values.

template <typename Iter, typename Sent, std::enable_if_t< detail::compatible_sentinel_v< Iter, Sent >, bool > = true>
table(Iter first, Sent last)¶: Constructs a table containing the elements in the range defined by the input iterator first and range sentinel last.

table()¶: 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.

bool operator==(const table &other) const¶

bool operator!=(const table &other) const¶

table insert(value_type value) const¶: Returns a table containing the value. 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) \).

decltype(auto) immer::table::insert(value_type value): Returns a table containing the value. 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>
table update(key_type k, Fn &&fn) const¶: Returns this->insert(fn((*this)[k])). In particular, fn maps T to T. The key k will be replaced inside the value returned by fn. It may allocate memory and its complexity is effectively \( O(1) \).

template <typename Fn>
decltype(auto) immer::table::update(key_type k, Fn && fn)

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

template <typename Fn>
decltype(auto) immer::table::update_if_exists(key_type k, Fn && fn)

table erase(const K &k) const¶: Returns a table without entries with given key k. If the key is not present it returns *this. It may allocate memory and its complexity is effectively \( O(1) \).

decltype(auto) immer::table::erase(const K & k): Returns a table without entries with given key k. If the key is not present it returns *this. It may allocate memory and its complexity is effectively \( O(1) \).

transient_type transient() const¶: Returns a transient form of this container, an immer::table_transient.

transient_type transient()¶: Returns a transient form of this container, an immer::table_transient.

const impl_t &impl() const¶