diff options
Diffstat (limited to 'immer/map.hpp')
| -rw-r--r-- | immer/map.hpp | 342 |
1 files changed, 342 insertions, 0 deletions
diff --git a/immer/map.hpp b/immer/map.hpp new file mode 100644 index 000000000000..58a84d2de939 --- /dev/null +++ b/immer/map.hpp @@ -0,0 +1,342 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/detail/hamts/champ.hpp> +#include <immer/detail/hamts/champ_iterator.hpp> +#include <immer/memory_policy.hpp> + +#include <functional> + +namespace immer { + +template <typename K, + typename T, + typename Hash, + typename Equal, + typename MemoryPolicy, + detail::hamts::bits_t B> +class map_transient; + +/*! + * Immutable unordered mapping of values from type `K` to type `T`. + * + * @tparam K The type of the keys. + * @tparam T The type of the values to be stored in the container. + * @tparam Hash The type of a function object capable of hashing + * values of type `T`. + * @tparam Equal The type of a function object capable of comparing + * values of type `T`. + * @tparam MemoryPolicy Memory management policy. See @ref + * memory_policy. + * + * @rst + * + * 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 :math:`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** + * .. literalinclude:: ../example/map/intro.cpp + * :language: c++ + * :start-after: intro/start + * :end-before: intro/end + * + * @endrst + * + */ +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 map +{ + using value_t = std::pair<K, T>; + + struct project_value + { + const T& operator()(const value_t& v) const noexcept + { + return v.second; + } + }; + + struct project_value_ptr + { + const T* operator()(const value_t& v) const noexcept + { + return &v.second; + } + }; + + struct combine_value + { + template <typename Kf, typename Tf> + value_t operator()(Kf&& k, Tf&& v) const + { + return {std::forward<Kf>(k), std::forward<Tf>(v)}; + } + }; + + struct default_value + { + const T& operator()() const + { + static T v{}; + return v; + } + }; + + struct error_value + { + const T& operator()() const + { + throw std::out_of_range{"key not found"}; + } + }; + + struct hash_key + { + auto operator()(const value_t& v) { return Hash{}(v.first); } + + auto operator()(const K& v) { return Hash{}(v); } + }; + + struct equal_key + { + auto operator()(const value_t& a, const value_t& b) + { + return Equal{}(a.first, b.first); + } + + auto operator()(const value_t& a, const K& b) + { + return Equal{}(a.first, b); + } + }; + + struct equal_value + { + auto operator()(const value_t& a, const value_t& b) + { + return Equal{}(a.first, b.first) && a.second == b.second; + } + }; + + using impl_t = + detail::hamts::champ<value_t, hash_key, equal_key, MemoryPolicy, B>; + +public: + 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>; + + /*! + * Default constructor. It creates a set of `size() == 0`. It + * does not allocate memory and its complexity is @f$ O(1) @f$. + */ + map() = default; + + /*! + * Returns an iterator pointing at the first element of the + * collection. It does not allocate memory and its complexity is + * @f$ O(1) @f$. + */ + IMMER_NODISCARD iterator begin() const { return {impl_}; } + + /*! + * Returns an iterator pointing just after the last element of the + * collection. It does not allocate and its complexity is @f$ O(1) @f$. + */ + IMMER_NODISCARD iterator end() const + { + return {impl_, typename iterator::end_t{}}; + } + + /*! + * Returns the number of elements in the container. It does + * not allocate memory and its complexity is @f$ O(1) @f$. + */ + IMMER_NODISCARD size_type size() const { return impl_.size; } + + /*! + * Returns `true` if there are no elements in the container. It + * does not allocate memory and its complexity is @f$ O(1) @f$. + */ + IMMER_NODISCARD bool empty() const { return impl_.size == 0; } + + /*! + * Returns `1` when the key `k` is contained in the map or `0` + * otherwise. It won't allocate memory and its complexity is + * *effectively* @f$ O(1) @f$. + */ + IMMER_NODISCARD size_type count(const K& k) const + { + return impl_.template get<detail::constantly<size_type, 1>, + detail::constantly<size_type, 0>>(k); + } + + /*! + * 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* @f$ O(1) @f$. + */ + IMMER_NODISCARD const T& operator[](const K& k) const + { + return impl_.template get<project_value, default_value>(k); + } + + /*! + * 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* @f$ O(1) @f$. + */ + const T& at(const K& k) const + { + return impl_.template get<project_value, error_value>(k); + } + + /*! + * 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* + * @f$ O(1) @f$. + * + * @rst + * + * .. admonition:: 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. + * + * @endrst + */ + IMMER_NODISCARD const T* find(const K& k) const + { + return impl_.template get<project_value_ptr, + detail::constantly<const T*, nullptr>>(k); + } + + /*! + * Returns whether the sets are equal. + */ + IMMER_NODISCARD bool operator==(const map& other) const + { + return impl_.template equals<equal_value>(other.impl_); + } + IMMER_NODISCARD bool operator!=(const map& other) const + { + return !(*this == other); + } + + /*! + * 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* @f$ + * O(1) @f$. + */ + IMMER_NODISCARD map insert(value_type value) const + { + return impl_.add(std::move(value)); + } + + /*! + * 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* @f$ + * O(1) @f$. + */ + IMMER_NODISCARD map set(key_type k, mapped_type v) const + { + return impl_.add({std::move(k), std::move(v)}); + } + + /*! + * 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* @f$ O(1) @f$. + */ + template <typename Fn> + IMMER_NODISCARD map update(key_type k, Fn&& fn) const + { + return impl_ + .template update<project_value, default_value, combine_value>( + std::move(k), std::forward<Fn>(fn)); + } + + /*! + * 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* @f$ O(1) @f$. + */ + IMMER_NODISCARD map erase(const K& k) const { return impl_.sub(k); } + + /*! + * Returns an @a transient form of this container, a + * `immer::map_transient`. + */ + IMMER_NODISCARD transient_type transient() const& + { + return transient_type{impl_}; + } + IMMER_NODISCARD transient_type transient() && + { + return transient_type{std::move(impl_)}; + } + + // Semi-private + const impl_t& impl() const { return impl_; } + +private: + friend transient_type; + + map(impl_t impl) + : impl_(std::move(impl)) + {} + + impl_t impl_ = impl_t::empty(); +}; + +} // namespace immer |