1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
//
// 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>;
struct project_value_ptr
{
const T* operator()(const T& v) const noexcept { return &v; }
};
public:
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>;
/*!
* Default constructor. It creates a set of `size() == 0`. It
* does not allocate memory and its complexity is @f$ O(1) @f$.
*/
set() = 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 `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 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));
}
/*!
* 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); }
/*!
* 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_)};
}
// Semi-private
const impl_t& impl() const { return impl_; }
private:
friend transient_type;
set(impl_t impl)
: impl_(std::move(impl))
{}
impl_t impl_ = impl_t::empty();
};
} // namespace immer
|
