/src/immer/immer/set.hpp

Source
//
// 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 T,
          typename Hash,
          typename Equal,
          typename MemoryPolicy,
          detail::hamts::bits_t B>
class set_transient;

/*!
 * Immutable set representing an unordered bag of values.
 *
 * @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 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 :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/set/intro.cpp
 *      :language: c++
 *      :start-after: intro/start
 *      :end-before:  intro/end
 *
 * @endrst
 *
 */
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 set
{
    using impl_t = detail::hamts::champ<T, Hash, Equal, MemoryPolicy, B>;

    using move_t =
        std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;

    struct project_value_ptr
    {
        const T* operator()(const T& v) const noexcept { return &v; }
    };

public:
    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>;

    using memory_policy_type = MemoryPolicy;

    /*!
     * Default constructor.  It creates a set of `size() == 0`.  It
     * does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    set() = default;

    /*!
     * Constructs a set containing the elements in `values`.
     */
    set(std::initializer_list<value_type> values)
        : impl_{impl_t::from_initializer_list(values)}
    {}

    /*!
     * Constructs a set containing the elements in the range
     * defined by the input iterator `first` and range sentinel `last`.
     */
    template <typename Iter,
              typename Sent,
              std::enable_if_t<detail::compatible_sentinel_v<Iter, Sent>,
                               bool> = true>
    set(Iter first, Sent last)
        : impl_{impl_t::from_range(first, last)}
    {}

    /*!
     * 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 `value` is contained in the set or `0`
     * otherwise. It won't allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     *
     * This overload participates in overload resolution only if
     * `Hash::is_transparent` is valid and denotes a type.
     */
    template <typename K,
              typename U = Hash,
              typename   = typename U::is_transparent>
    IMMER_NODISCARD size_type count(const K& value) const
    {
        return impl_.template get<detail::constantly<size_type, 1>,
                                  detail::constantly<size_type, 0>>(value);
    }

    /*!
     * Returns `1` when `value` is contained in the set or `0`
     * otherwise. It won't allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     */
    IMMER_NODISCARD size_type count(const T& value) const
    {
        return impl_.template get<detail::constantly<size_type, 1>,
                                  detail::constantly<size_type, 0>>(value);
    }

    /*!
     * 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*
     * @f$ O(1) @f$.
     */
    IMMER_NODISCARD const T* find(const T& value) const
    {
        return impl_.template get<project_value_ptr,
                                  detail::constantly<const T*, nullptr>>(value);
    }

    /*!
     * 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*
     * @f$ O(1) @f$.
     *
     * This overload participates in overload resolution only if
     * `Hash::is_transparent` is valid and denotes a type.
     */
    template <typename K,
              typename U = Hash,
              typename   = typename U::is_transparent>
    IMMER_NODISCARD const T* find(const K& value) const
    {
        return impl_.template get<project_value_ptr,
                                  detail::constantly<const T*, nullptr>>(value);
    }

    /*!
     * Returns whether the sets are equal.
     */
    IMMER_NODISCARD bool operator==(const set& other) const
    {
        return impl_.equals(other.impl_);
    }
    IMMER_NODISCARD bool operator!=(const set& other) const
    {
        return !(*this == other);
    }

    /*!
     * 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* @f$ O(1) @f$.
     */
    IMMER_NODISCARD set insert(T value) const&
    {
        return impl_.add(std::move(value));
    }
    IMMER_NODISCARD decltype(auto) insert(T value) &&
    {
        return insert_move(move_t{}, std::move(value));
    }

    /*!
     * 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* @f$ O(1) @f$.
     */
    IMMER_NODISCARD set erase(const T& value) const&
    {
        return impl_.sub(value);
    }
    IMMER_NODISCARD decltype(auto) erase(const T& value) &&
    {
        return erase_move(move_t{}, value);
    }

    /*!
     * Returns an @a transient form of this container, a
     * `immer::set_transient`.
     */
    IMMER_NODISCARD transient_type transient() const&
    {
        return transient_type{impl_};
    }
    IMMER_NODISCARD transient_type transient() &&
    {
        return transient_type{std::move(impl_)};
    }

    /*!
     * 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.
     */
    void* identity() const { return impl_.root; }

    // Semi-private
    const impl_t& impl() const { return impl_; }

private:
    friend transient_type;

    set&& insert_move(std::true_type, value_type value)
    {
        impl_.add_mut({}, std::move(value));
        return std::move(*this);
    }
    set insert_move(std::false_type, value_type value)
    {
        return impl_.add(std::move(value));
    }

    set&& erase_move(std::true_type, const value_type& value)
    {
        impl_.sub_mut({}, value);
        return std::move(*this);
    }
    set erase_move(std::false_type, const value_type& value)
    {
        return impl_.sub(value);
    }

    set(impl_t impl)
        : impl_(std::move(impl))
    {}

    impl_t impl_ = impl_t::empty();
};

} // namespace immer

Coverage Report

Created: 2023-06-07 06:37

Line	Count	Source
1		//
2		// immer: immutable data structures for C++
3		// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4		//
5		// This software is distributed under the Boost Software License, Version 1.0.
6		// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7		//
8
9		#pragma once
10
11		#include <immer/detail/hamts/champ.hpp>
12		#include <immer/detail/hamts/champ_iterator.hpp>
13		#include <immer/memory_policy.hpp>
14
15		#include <functional>
16
17		namespace immer {
18
19		template <typename T,
20		typename Hash,
21		typename Equal,
22		typename MemoryPolicy,
23		detail::hamts::bits_t B>
24		class set_transient;
25
26		/*!
27		* Immutable set representing an unordered bag of values.
28		*
29		* @tparam T The type of the values to be stored in the container.
30		* @tparam Hash The type of a function object capable of hashing
31		* values of type `T`.
32		* @tparam Equal The type of a function object capable of comparing
33		* values of type `T`.
34		* @tparam MemoryPolicy Memory management policy. See @ref
35		* memory_policy.
36		*
37		* @rst
38		*
39		* This container provides a good trade-off between cache locality,
40		* membership checks, update performance and structural sharing. It
41		* does so by storing the data in contiguous chunks of :math:`2^{B}`
42		* elements. When storing big objects, the size of these contiguous
43		* chunks can become too big, damaging performance. If this is
44		* measured to be problematic for a specific use-case, it can be
45		* solved by using a `immer::box` to wrap the type `T`.
46		*
47		* Example
48		* .. literalinclude:: ../example/set/intro.cpp
49		* :language: c++
50		* :start-after: intro/start
51		* :end-before: intro/end
52		*
53		* @endrst
54		*
55		*/
56		template <typename T,
57		typename Hash = std::hash<T>,
58		typename Equal = std::equal_to<T>,
59		typename MemoryPolicy = default_memory_policy,
60		detail::hamts::bits_t B = default_bits>
61		class set
62		{
63		using impl_t = detail::hamts::champ<T, Hash, Equal, MemoryPolicy, B>;
64
65		using move_t =
66		std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;
67
68		struct project_value_ptr
69		{
70		const T* operator()(const T& v) const noexcept { return &v; }
71		};
72
73		public:
74		using value_type = T;
75		using size_type = detail::hamts::size_t;
76		using diference_type = std::ptrdiff_t;
77		using hasher = Hash;
78		using key_equal = Equal;
79		using reference = const T&;
80		using const_reference = const T&;
81
82		using iterator =
83		detail::hamts::champ_iterator<T, Hash, Equal, MemoryPolicy, B>;
84		using const_iterator = iterator;
85
86		using transient_type = set_transient<T, Hash, Equal, MemoryPolicy, B>;
87
88		using memory_policy_type = MemoryPolicy;
89
90		/*!
91		* Default constructor. It creates a set of `size() == 0`. It
92		* does not allocate memory and its complexity is @f$ O(1) @f$.
93		*/
94	13.4k	set() = default;
95
96		/*!
97		* Constructs a set containing the elements in `values`.
98		*/
99		set(std::initializer_list<value_type> values)
100		: impl_{impl_t::from_initializer_list(values)}
101		{}
102
103		/*!
104		* Constructs a set containing the elements in the range
105		* defined by the input iterator `first` and range sentinel `last`.
106		*/
107		template <typename Iter,
108		typename Sent,
109		std::enable_if_t<detail::compatible_sentinel_v<Iter, Sent>,
110		bool> = true>
111		set(Iter first, Sent last)
112		: impl_{impl_t::from_range(first, last)}
113		{}
114
115		/*!
116		* Returns an iterator pointing at the first element of the
117		* collection. It does not allocate memory and its complexity is
118		* @f$ O(1) @f$.
119		*/
120	9.47k	IMMER_NODISCARD iterator begin() const { return {impl_}; }
121
122		/*!
123		* Returns an iterator pointing just after the last element of the
124		* collection. It does not allocate and its complexity is @f$ O(1) @f$.
125		*/
126		IMMER_NODISCARD iterator end() const
127	9.47k	{
128	9.47k	return {impl_, typename iterator::end_t{}};
129	9.47k	}
130
131		/*!
132		* Returns the number of elements in the container. It does
133		* not allocate memory and its complexity is @f$ O(1) @f$.
134		*/
135		IMMER_NODISCARD size_type size() const { return impl_.size; }
136
137		/*!
138		* Returns `true` if there are no elements in the container. It
139		* does not allocate memory and its complexity is @f$ O(1) @f$.
140		*/
141		IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
142
143		/*!
144		* Returns `1` when `value` is contained in the set or `0`
145		* otherwise. It won't allocate memory and its complexity is
146		* effectively @f$ O(1) @f$.
147		*
148		* This overload participates in overload resolution only if
149		* `Hash::is_transparent` is valid and denotes a type.
150		*/
151		template <typename K,
152		typename U = Hash,
153		typename = typename U::is_transparent>
154		IMMER_NODISCARD size_type count(const K& value) const
155		{
156		return impl_.template get<detail::constantly<size_type, 1>,
157		detail::constantly<size_type, 0>>(value);
158		}
159
160		/*!
161		* Returns `1` when `value` is contained in the set or `0`
162		* otherwise. It won't allocate memory and its complexity is
163		* effectively @f$ O(1) @f$.
164		*/
165		IMMER_NODISCARD size_type count(const T& value) const
166	230k	{
167	230k	return impl_.template get<detail::constantly<size_type, 1>,
168	230k	detail::constantly<size_type, 0>>(value);
169	230k	}
170
171		/*!
172		* Returns a pointer to the value if `value` is contained in the
173		* set, or nullptr otherwise.
174		* It does not allocate memory and its complexity is effectively
175		* @f$ O(1) @f$.
176		*/
177		IMMER_NODISCARD const T* find(const T& value) const
178		{
179		return impl_.template get<project_value_ptr,
180		detail::constantly<const T*, nullptr>>(value);
181		}
182
183		/*!
184		* Returns a pointer to the value if `value` is contained in the
185		* set, or nullptr otherwise.
186		* It does not allocate memory and its complexity is effectively
187		* @f$ O(1) @f$.
188		*
189		* This overload participates in overload resolution only if
190		* `Hash::is_transparent` is valid and denotes a type.
191		*/
192		template <typename K,
193		typename U = Hash,
194		typename = typename U::is_transparent>
195		IMMER_NODISCARD const T* find(const K& value) const
196		{
197		return impl_.template get<project_value_ptr,
198		detail::constantly<const T*, nullptr>>(value);
199		}
200
201		/*!
202		* Returns whether the sets are equal.
203		*/
204		IMMER_NODISCARD bool operator==(const set& other) const
205		{
206		return impl_.equals(other.impl_);
207		}
208		IMMER_NODISCARD bool operator!=(const set& other) const
209		{
210		return !(*this == other);
211		}
212
213		/*!
214		* Returns a set containing `value`. If the `value` is already in
215		* the set, it returns the same set. It may allocate memory and
216		* its complexity is effectively @f$ O(1) @f$.
217		*/
218		IMMER_NODISCARD set insert(T value) const&
219	391k	{
220	391k	return impl_.add(std::move(value));
221	391k	}
222		IMMER_NODISCARD decltype(auto) insert(T value) &&
223	34.4k	{
224	34.4k	return insert_move(move_t{}, std::move(value));
225	34.4k	}
226
227		/*!
228		* Returns a set without `value`. If the `value` is not in the
229		* set it returns the same set. It may allocate memory and its
230		* complexity is effectively @f$ O(1) @f$.
231		*/
232		IMMER_NODISCARD set erase(const T& value) const&
233	6.38k	{
234	6.38k	return impl_.sub(value);
235	6.38k	}
236		IMMER_NODISCARD decltype(auto) erase(const T& value) &&
237	26.7k	{
238	26.7k	return erase_move(move_t{}, value);
239	26.7k	}
240
241		/*!
242		* Returns an @a transient form of this container, a
243		* `immer::set_transient`.
244		*/
245		IMMER_NODISCARD transient_type transient() const&
246		{
247		return transient_type{impl_};
248		}
249		IMMER_NODISCARD transient_type transient() &&
250		{
251		return transient_type{std::move(impl_)};
252		}
253
254		/*!
255		* Returns a value that can be used as identity for the container. If two
256		* values have the same identity, they are guaranteed to be equal and to
257		* contain the same objects. However, two equal containers are not
258		* guaranteed to have the same identity.
259		*/
260		void* identity() const { return impl_.root; }
261
262		// Semi-private
263	208k	const impl_t& impl() const { return impl_; }
264
265		private:
266		friend transient_type;
267
268		set&& insert_move(std::true_type, value_type value)
269	34.4k	{
270	34.4k	impl_.add_mut({}, std::move(value));
271	34.4k	return std::move(*this);
272	34.4k	}
273		set insert_move(std::false_type, value_type value)
274		{
275		return impl_.add(std::move(value));
276		}
277
278		set&& erase_move(std::true_type, const value_type& value)
279	26.7k	{
280	26.7k	impl_.sub_mut({}, value);
281	26.7k	return std::move(*this);
282	26.7k	}
283		set erase_move(std::false_type, const value_type& value)
284		{
285		return impl_.sub(value);
286		}
287
288		set(impl_t impl)
289		: impl_(std::move(impl))
290	398k	{}
291
292		impl_t impl_ = impl_t::empty();
293		};
294
295		} // namespace immer