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

box()

Constructs a box holding T{}.

template <typename Arg, typename Enable = std::enable_if_t< !std::is_same<box, std::decay_t<Arg>>::value && std::is_constructible<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

bool operator==(detail::exact_t<const box&> other) const

Comparison.

bool operator!=(detail::exact_t<const box&> other) const
bool operator<(detail::exact_t<const box&> other) const
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 a 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 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 \( 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 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()
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 cotainer 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()
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 frony. 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()
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 key_type = T
using value_type = T
using size_type = detail::hamts::size_t
using diference_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>

Public Functions

set()

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

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

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

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

transient_type transient() const

Returns an transient form of this container, a immer::set_transient.

transient_type transient()
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 cotainer 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 diference_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>

Public Functions

map()

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

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

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

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

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 unfortunatelly unnecessarily unrestricted.

bool operator==(const map &other) const

Returns whether the sets 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) \).

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

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

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

transient_type transient() const

Returns an transient form of this container, a immer::map_transient.

transient_type transient()
const impl_t &impl() const