datastructures 0.1.0
Loading...
Searching...
No Matches
map.ipp
Go to the documentation of this file.
1
7
8#pragma once
9
10#include "map.hpp" // for clangd
11
12#include <stdexcept>
13#include <tuple>
14
15namespace datastructures {
16
17// ==== Constructors & Assigments ====
18
19template <class TKey, class TValue, class TKeyComp, class TAlloc>
20map<TKey, TValue, TKeyComp, TAlloc>::map() : map(key_compare{}) {}
21
22template <class TKey, class TValue, class TKeyComp, class TAlloc>
23map<TKey, TValue, TKeyComp, TAlloc>::map(const key_compare &comparator,
24 const allocator_type &allocator)
25 : comparator(comparator), value_comparator(comparator),
26 tree(value_comparator, allocator) {}
27
28template <class TKey, class TValue, class TKeyComp, class TAlloc>
31
32template <class TKey, class TValue, class TKeyComp, class TAlloc>
33map<TKey, TValue, TKeyComp, TAlloc>::map(const map &other)
34 : comparator(other.comparator), value_comparator(other.comparator),
35 tree(other.tree) {}
36
37template <class TKey, class TValue, class TKeyComp, class TAlloc>
38map<TKey, TValue, TKeyComp, TAlloc> &
39map<TKey, TValue, TKeyComp, TAlloc>::operator=(const map &other) {
40 comparator = other.comparator;
41 value_comparator = other.comparator;
42 tree = other.tree;
43 return *this;
44}
45
46template <class TKey, class TValue, class TKeyComp, class TAlloc>
47map<TKey, TValue, TKeyComp, TAlloc>::map(map &&other) noexcept
48 : comparator(std::move(other.comparator)),
49 value_comparator(std::move(other.comparator)),
50 tree(std::move(other.tree)) {}
51
52template <class TKey, class TValue, class TKeyComp, class TAlloc>
53map<TKey, TValue, TKeyComp, TAlloc> &
54map<TKey, TValue, TKeyComp, TAlloc>::operator=(map &&other) noexcept {
55 comparator = std::move(other.comparator);
56 value_comparator = std::move(other.comparator);
57 tree = std::move(other.tree);
58 return *this;
59}
60
61template <class TKey, class TValue, class TKeyComp, class TAlloc>
62map<TKey, TValue, TKeyComp, TAlloc>::~map() noexcept {
63 // the tree will be deleted in the `avl_tree::~avl_tree`.
64}
65
66// ==== Observers & Allocator getter ====
67
68template <class TKey, class TValue, class TKeyComp, class TAlloc>
69typename map<TKey, TValue, TKeyComp, TAlloc>::allocator_type
73
74template <class TKey, class TValue, class TKeyComp, class TAlloc>
75typename map<TKey, TValue, TKeyComp, TAlloc>::key_compare
79
80template <class TKey, class TValue, class TKeyComp, class TAlloc>
81typename map<TKey, TValue, TKeyComp, TAlloc>::value_compare
85
86// ==== Access Functions ====
87
88template <class TKey, class TValue, class TKeyComp, class TAlloc>
89typename map<TKey, TValue, TKeyComp, TAlloc>::mapped_type &
90map<TKey, TValue, TKeyComp, TAlloc>::at(const key_type &key) {
91 typename tree_type::node_ptr node = tree.find(key);
92 if (node == nullptr) {
93 throw std::out_of_range("Key not found!");
94 }
95 return node->item.second;
96}
97
98template <class TKey, class TValue, class TKeyComp, class TAlloc>
99const typename map<TKey, TValue, TKeyComp, TAlloc>::mapped_type &
100map<TKey, TValue, TKeyComp, TAlloc>::at(const key_type &key) const {
101 typename tree_type::node_ptr node = tree.find(key);
102 if (node == nullptr) {
103 throw std::out_of_range("Key not found!");
104 }
105 return node->item.second;
106}
107
108template <class TKey, class TValue, class TKeyComp, class TAlloc>
109typename map<TKey, TValue, TKeyComp, TAlloc>::mapped_type &
110map<TKey, TValue, TKeyComp, TAlloc>::operator[](const key_type &key) {
111 auto insert_callback = [&key]() { return value_type(key, mapped_type{}); };
112
113 auto [node, inserted] = tree.insert(key, insert_callback);
114
115 return node->item.second;
116}
117
118template <class TKey, class TValue, class TKeyComp, class TAlloc>
119typename map<TKey, TValue, TKeyComp, TAlloc>::mapped_type &
120map<TKey, TValue, TKeyComp, TAlloc>::operator[](key_type &&key) {
121 auto insert_callback = [&key]() {
122 return value_type(std::move(key), mapped_type{});
123 };
124
125 auto [node, inserted] = tree.insert(key, insert_callback);
126
127 return node->item.second;
128}
129
130template <class TKey, class TValue, class TKeyComp, class TAlloc>
131typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
132map<TKey, TValue, TKeyComp, TAlloc>::find(const key_type &key) noexcept {
133 typename tree_type::node_ptr node = tree.find(key);
134 return iterator(&tree, node);
135}
136
137template <class TKey, class TValue, class TKeyComp, class TAlloc>
138typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
139map<TKey, TValue, TKeyComp, TAlloc>::find(const key_type &key) const noexcept {
140 typename tree_type::node_ptr node = tree.find(key);
141 return iterator(&tree, node);
142}
143
144template <class TKey, class TValue, class TKeyComp, class TAlloc>
145bool map<TKey, TValue, TKeyComp, TAlloc>::contains(
146 const key_type &key) const noexcept {
147 typename tree_type::node_ptr node = tree.find(key);
148 return node != nullptr;
149}
150
151template <class TKey, class TValue, class TKeyComp, class TAlloc>
152typename map<TKey, TValue, TKeyComp, TAlloc>::size_type
153map<TKey, TValue, TKeyComp, TAlloc>::count(const key_type &key) const noexcept {
154 typename tree_type::node_ptr node = tree.find(key);
155 return node != nullptr ? 1 : 0;
156}
157
158template <class TKey, class TValue, class TKeyComp, class TAlloc>
159typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
160map<TKey, TValue, TKeyComp, TAlloc>::lower_bound(const key_type &key) noexcept {
161 typename tree_type::node_ptr node = tree.template bound<true>(key);
162 return iterator(&tree, node);
163}
164
165template <class TKey, class TValue, class TKeyComp, class TAlloc>
166typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
167map<TKey, TValue, TKeyComp, TAlloc>::lower_bound(
168 const key_type &key) const noexcept {
169 typename tree_type::node_ptr node = tree.template bound<true>(key);
170 return iterator(&tree, node);
171}
172
173template <class TKey, class TValue, class TKeyComp, class TAlloc>
174typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
175map<TKey, TValue, TKeyComp, TAlloc>::upper_bound(const key_type &key) noexcept {
176 typename tree_type::node_ptr node = tree.template bound<false>(key);
177 return iterator(&tree, node);
178}
179
180template <class TKey, class TValue, class TKeyComp, class TAlloc>
181typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
182map<TKey, TValue, TKeyComp, TAlloc>::upper_bound(
183 const key_type &key) const noexcept {
184 typename tree_type::node_ptr node = tree.template bound<false>(key);
185 return iterator(&tree, node);
186}
187
188template <class TKey, class TValue, class TKeyComp, class TAlloc>
189std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator,
190 typename map<TKey, TValue, TKeyComp, TAlloc>::iterator>
191map<TKey, TValue, TKeyComp, TAlloc>::equal_range(const key_type &key) noexcept {
192 return std::make_pair(lower_bound(key), upper_bound(key));
193}
194
195template <class TKey, class TValue, class TKeyComp, class TAlloc>
196std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator,
197 typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator>
198map<TKey, TValue, TKeyComp, TAlloc>::equal_range(
199 const key_type &key) const noexcept {
200 return std::make_pair(lower_bound(key), upper_bound(key));
201}
202
203// ==== Iterators ====
204
205template <class TKey, class TValue, class TKeyComp, class TAlloc>
206typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
207map<TKey, TValue, TKeyComp, TAlloc>::begin() noexcept {
208 return iterator(&tree, tree.min_from(tree.get_root()));
209}
210
211template <class TKey, class TValue, class TKeyComp, class TAlloc>
212typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
213map<TKey, TValue, TKeyComp, TAlloc>::begin() const noexcept {
214 return const_iterator(&tree, tree.min_from(tree.get_root()));
215}
216
217template <class TKey, class TValue, class TKeyComp, class TAlloc>
218typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
222
223template <class TKey, class TValue, class TKeyComp, class TAlloc>
224typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
225map<TKey, TValue, TKeyComp, TAlloc>::end() noexcept {
226 return iterator(&tree, nullptr);
227}
228
229template <class TKey, class TValue, class TKeyComp, class TAlloc>
230typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
234
235template <class TKey, class TValue, class TKeyComp, class TAlloc>
236typename map<TKey, TValue, TKeyComp, TAlloc>::const_iterator
240
241template <class TKey, class TValue, class TKeyComp, class TAlloc>
242typename map<TKey, TValue, TKeyComp, TAlloc>::reverse_iterator
246
247template <class TKey, class TValue, class TKeyComp, class TAlloc>
248typename map<TKey, TValue, TKeyComp, TAlloc>::const_reverse_iterator
252
253template <class TKey, class TValue, class TKeyComp, class TAlloc>
254typename map<TKey, TValue, TKeyComp, TAlloc>::const_reverse_iterator
258
259template <class TKey, class TValue, class TKeyComp, class TAlloc>
260typename map<TKey, TValue, TKeyComp, TAlloc>::reverse_iterator
264
265template <class TKey, class TValue, class TKeyComp, class TAlloc>
266typename map<TKey, TValue, TKeyComp, TAlloc>::const_reverse_iterator
270
271template <class TKey, class TValue, class TKeyComp, class TAlloc>
272typename map<TKey, TValue, TKeyComp, TAlloc>::const_reverse_iterator
276
277// ==== Size Queries ====
278
279template <class TKey, class TValue, class TKeyComp, class TAlloc>
280bool map<TKey, TValue, TKeyComp, TAlloc>::empty() const noexcept {
281 return tree.size() == 0;
282}
283
284template <class TKey, class TValue, class TKeyComp, class TAlloc>
285typename map<TKey, TValue, TKeyComp, TAlloc>::size_type
289
290template <class TKey, class TValue, class TKeyComp, class TAlloc>
291int map<TKey, TValue, TKeyComp, TAlloc>::get_height() const noexcept {
292 return tree.get_height();
293}
294
295// ==== Update Operations ====
296
297template <class TKey, class TValue, class TKeyComp, class TAlloc>
301
302template <class TKey, class TValue, class TKeyComp, class TAlloc>
303std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
304map<TKey, TValue, TKeyComp, TAlloc>::insert(const value_type &item) {
305 auto insert_callback = [&item]() { return item; };
306
307 auto [node, inserted] = tree.insert(item.first, insert_callback);
308
309 return std::make_pair(iterator(&tree, node), inserted);
310}
311
312template <class TKey, class TValue, class TKeyComp, class TAlloc>
313std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
314map<TKey, TValue, TKeyComp, TAlloc>::insert(value_type &&item) {
315 auto insert_callback = [&item]() { return std::move(item); };
316
317 auto [node, inserted] = tree.insert(item.first, insert_callback);
318
319 return std::make_pair(iterator(&tree, node), inserted);
320}
321
322template <class TKey, class TValue, class TKeyComp, class TAlloc>
323template <class TMapped>
324std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
325map<TKey, TValue, TKeyComp, TAlloc>::insert_or_assign(const key_type &key,
326 TMapped &&value) {
327 auto assign_callback = [&key, &value](value_type &item) {
328 item.second = std::forward<TMapped>(value);
329 };
330 auto insert_callback = [&key, &value]() {
331 return value_type(key, std::forward<TMapped>(value));
332 };
333
334 auto [node, inserted] = tree.insert(key, insert_callback, assign_callback);
335
336 return std::make_pair(iterator(&tree, node), inserted);
337}
338
339template <class TKey, class TValue, class TKeyComp, class TAlloc>
340template <class TMapped>
341std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
342map<TKey, TValue, TKeyComp, TAlloc>::insert_or_assign(key_type &&key,
343 TMapped &&value) {
344 auto assign_callback = [&key, &value](value_type &item) {
345 item.second = std::forward<TMapped>(value);
346 };
347 auto insert_callback = [&key, &value]() {
348 return value_type(std::move(key), std::forward<TMapped>(value));
349 };
350
351 auto [node, inserted] = tree.insert(key, insert_callback, assign_callback);
352
353 return std::make_pair(iterator(&tree, node), inserted);
354}
355
356template <class TKey, class TValue, class TKeyComp, class TAlloc>
357template <class... Args>
358std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
359map<TKey, TValue, TKeyComp, TAlloc>::try_emplace(const key_type &key,
360 Args &&...args) {
361 auto insert_callback = [&]() {
362 return value_type(std::piecewise_construct, std::forward_as_tuple(key),
363 std::forward_as_tuple(std::forward<Args>(args)...));
364 };
365
366 auto [node, inserted] = tree.insert(key, insert_callback);
367
368 return std::make_pair(iterator(&tree, node), inserted);
369}
370
371template <class TKey, class TValue, class TKeyComp, class TAlloc>
372template <class... Args>
373std::pair<typename map<TKey, TValue, TKeyComp, TAlloc>::iterator, bool>
374map<TKey, TValue, TKeyComp, TAlloc>::try_emplace(key_type &&key,
375 Args &&...args) {
376 auto insert_callback = [&]() {
377 return value_type(std::piecewise_construct,
378 std::forward_as_tuple(std::move(key)),
379 std::forward_as_tuple(std::forward<Args>(args)...));
380 };
381
382 auto [node, inserted] = tree.insert(key, insert_callback);
383
384 return std::make_pair(iterator(&tree, node), inserted);
385}
386
387template <class TKey, class TValue, class TKeyComp, class TAlloc>
388typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
389map<TKey, TValue, TKeyComp, TAlloc>::erase(iterator pos) noexcept {
390 iterator tmp = pos++;
391 tree.erase(tmp.node);
392 return pos;
393}
394
395template <class TKey, class TValue, class TKeyComp, class TAlloc>
396typename map<TKey, TValue, TKeyComp, TAlloc>::iterator
397map<TKey, TValue, TKeyComp, TAlloc>::erase(const_iterator pos) noexcept {
398 const_iterator tmp = pos++;
399 tree.erase(tmp.node);
400 return iterator(&tree, pos.node);
401}
402
403template <class TKey, class TValue, class TKeyComp, class TAlloc>
404typename map<TKey, TValue, TKeyComp, TAlloc>::size_type
405map<TKey, TValue, TKeyComp, TAlloc>::erase(const key_type &key) noexcept {
406 typename tree_type::node_ptr node = tree.find(key);
407
408 if (node == nullptr) {
409 return 0;
410 }
411
412 tree.erase(node);
413
414 return 1;
415}
416
417template <class TKey, class TValue, class TKeyComp, class TAlloc>
418void map<TKey, TValue, TKeyComp, TAlloc>::swap(map &other) noexcept {
419 std::swap(tree, other.tree);
420 std::swap(comparator, other.comparator);
421 std::swap(value_comparator, other.value_comparator);
422}
423
424// ==== Debug Functions ====
425
426template <class TKey, class TValue, class TKeyComp, class TAlloc>
427std::string
428map<TKey, TValue, TKeyComp, TAlloc>::to_dot(bool print_invis) const {
429 return tree.to_dot(print_invis);
430}
431
432} // namespace datastructures
datastructures::detail::avl_iterator
The AVL tree iterator type.
Definition _avl_iterator.hpp:34
datastructures::detail::avl_tree< key_type, value_type, value_compare, allocator_type >::node_ptr
typename base::node_ptr node_ptr
Definition _avl.hpp:83
datastructures::map
A map type using an AVL tree as the underlying structure.
Definition map.hpp:47
datastructures::map::erase
iterator erase(iterator pos) noexcept
Erases an item.
Definition map.ipp:389
datastructures::map::upper_bound
iterator upper_bound(const key_type &key) noexcept
Returns an iterator to the first item which is greater that the given key.
Definition map.ipp:175
datastructures::map::find
iterator find(const key_type &key) noexcept
Finds an item with the given key.
Definition map.ipp:132
datastructures::map::get_height
int get_height() const noexcept
Returns the height of the underlying tree.
Definition map.ipp:291
datastructures::map::rbegin
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the biggest item.
Definition map.ipp:243
datastructures::map::begin
iterator begin() noexcept
Returns an iterator to the smallest item.
Definition map.ipp:207
datastructures::map::key_comp
key_compare key_comp() const noexcept
Returns the function that compares keys.
Definition map.ipp:76
datastructures::map::cbegin
const_iterator cbegin() const noexcept
Returns explicitly a constant iterator to the smallest item.
Definition map.ipp:219
datastructures::map::clear
void clear() noexcept
Erases the whole tree.
Definition map.ipp:298
datastructures::map::operator[]
mapped_type & operator[](const key_type &key)
Access specified item or insert.
Definition map.ipp:110
datastructures::map::at
mapped_type & at(const key_type &key)
Access specified item.
Definition map.ipp:90
datastructures::map::~map
~map() noexcept
Definition map.ipp:62
datastructures::map::swap
void swap(map &other) noexcept
Swaps the content.
Definition map.ipp:418
datastructures::map::crbegin
const_reverse_iterator crbegin() const noexcept
Returns explicitly a constant reverse iterator to the biggest item.
Definition map.ipp:255
datastructures::map::operator=
map & operator=(const map &other)
Definition map.ipp:39
datastructures::map::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition map.hpp:117
datastructures::map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &key, TMapped &&value)
Inserts an item or assigns the value.
datastructures::map::value_type
std::pair< const key_type, mapped_type > value_type
Definition map.hpp:53
datastructures::map::end
iterator end() noexcept
Returns an iterator to the end.
Definition map.ipp:225
datastructures::map::size_type
typename alloc_traits::size_type size_type
Definition map.hpp:99
datastructures::map::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &key, Args &&...args)
Construct an item in-place.
datastructures::map::map
map()
Definition map.ipp:20
datastructures::map::key_compare
TKeyComp key_compare
Definition map.hpp:60
datastructures::map::allocator_type
TAlloc allocator_type
Definition map.hpp:97
datastructures::map::to_dot
std::string to_dot(bool print_invis) const
Returns the dot representation of the tree.
Definition map.ipp:428
datastructures::map::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition map.hpp:116
datastructures::map::get_allocator
allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition map.ipp:70
datastructures::map::cend
const_iterator cend() const noexcept
Returns explicitly a constant iterator to the end.
Definition map.ipp:237
datastructures::map::value_comp
value_compare value_comp() const noexcept
Returns the function that compares keys in the key, value pairs.
Definition map.ipp:82
datastructures::map::key_type
TKey key_type
Definition map.hpp:51
datastructures::map::size
size_type size() const noexcept
Returns the current number of items.
Definition map.ipp:286
datastructures::map::insert
std::pair< iterator, bool > insert(const value_type &item)
Inserts an item.
Definition map.ipp:304
datastructures::map::crend
const_reverse_iterator crend() const noexcept
Returns explicitly a constant reverse iterator to the end.
Definition map.ipp:273
datastructures::map::contains
bool contains(const key_type &key) const noexcept
Checks whether there exists an item with given key in the tree.
Definition map.ipp:145
datastructures::map::mapped_type
TValue mapped_type
Definition map.hpp:52
datastructures::map::empty
bool empty() const noexcept
Checks whether the map contains any values.
Definition map.ipp:280
datastructures::map::lower_bound
iterator lower_bound(const key_type &key) noexcept
Returns an iterator to the first item which is not less than the given key.
Definition map.ipp:160
datastructures::map::count
size_type count(const key_type &key) const noexcept
Returns the number of items with the given key (0 or 1).
Definition map.ipp:153
datastructures::map::equal_range
std::pair< iterator, iterator > equal_range(const key_type &key) noexcept
Returns a range containing all the items with the given key.
Definition map.ipp:191
datastructures::map::rend
reverse_iterator rend() noexcept
Returns a reverse iterator to the end.
Definition map.ipp:261
map.hpp
Declarations of the ethereal map.
datastructures
Declarations of the persistent map.
Definition _avl.hpp:14
datastructures::map::value_compare
Definition map.hpp:67