-
Notifications
You must be signed in to change notification settings - Fork 1
/
ordered_map.hpp
176 lines (160 loc) · 7.01 KB
/
ordered_map.hpp
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
/// _______ __ __ __ _____ __ __ __
/// | __| |_/ | \_/ |/ _ \ / \/ \| | fkYAML: A C++ header-only YAML library
/// | __| _ < \_ _/| ___ | _ | |___ version 0.3.9
/// |__| |_| \__| |_| |_| |_|___||___|______| https://github.com/fktn-k/fkYAML
///
/// SPDX-FileCopyrightText: 2023-2024 Kensuke Fukutani <fktn.dev@gmail.com>
/// SPDX-License-Identifier: MIT
///
/// @file
#ifndef FK_YAML_ORDERED_MAP_HPP_
#define FK_YAML_ORDERED_MAP_HPP_
#include <functional>
#include <initializer_list>
#include <memory>
#include <utility>
#include <vector>
#include <fkYAML/detail/macros/version_macros.hpp>
#include <fkYAML/detail/meta/type_traits.hpp>
#include <fkYAML/exception.hpp>
FK_YAML_NAMESPACE_BEGIN
/// @brief A minimal map-like container which preserves insertion order.
/// @tparam Key A type for keys.
/// @tparam Value A type for values.
/// @tparam IgnoredCompare A placeholder for key comparison. This will be ignored.
/// @tparam Allocator A class for allocators.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/
template <
typename Key, typename Value, typename IgnoredCompare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, Value>>>
class ordered_map : public std::vector<std::pair<const Key, Value>, Allocator> {
public:
/// A type for keys.
using key_type = Key;
/// A type for values.
using mapped_type = Value;
/// A type for internal key-value containers.
using Container = std::vector<std::pair<const Key, Value>, Allocator>;
/// A type for key-value pairs.
using value_type = typename Container::value_type;
/// A type for non-const iterators.
using iterator = typename Container::iterator;
/// A type for const iterators.
using const_iterator = typename Container::const_iterator;
/// A type for size parameters used in this class.
using size_type = typename Container::size_type;
/// A type for comparison between keys.
using key_compare = std::equal_to<Key>;
public:
/// @brief Construct a new ordered_map object.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/constructor/
ordered_map() noexcept(noexcept(Container()))
: Container() {
}
/// @brief Construct a new ordered_map object with an initializer list.
/// @param init An initializer list to construct the inner container object.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/constructor/
ordered_map(std::initializer_list<value_type> init)
: Container {init} {
}
public:
/// @brief A subscript operator for ordered_map objects.
/// @tparam KeyType A type for the input key.
/// @param key A key to the target value.
/// @return mapped_type& Reference to a mapped_type object associated with the given key.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/operator[]/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
mapped_type& operator[](KeyType&& key) noexcept {
return emplace(std::forward<KeyType>(key), mapped_type()).first->second;
}
public:
/// @brief Emplace a new key-value pair if the new key does not exist.
/// @tparam KeyType A type for the input key.
/// @param key A key to be emplaced to this ordered_map object.
/// @param value A value to be emplaced to this ordered_map object.
/// @return std::pair<iterator, bool> A result of emplacement of the new key-value pair.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/emplace/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
std::pair<iterator, bool> emplace(KeyType&& key, const mapped_type& value) noexcept {
for (auto itr = this->begin(); itr != this->end(); ++itr) {
if (m_compare(itr->first, key)) {
return {itr, false};
}
}
this->emplace_back(key, value);
return {std::prev(this->end()), true};
}
/// @brief Find a value associated to the given key. Throws an exception if the search fails.
/// @tparam KeyType A type for the input key.
/// @param key A key to find a value with.
/// @return mapped_type& The value associated to the given key.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/at/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
mapped_type& at(KeyType&& key) {
for (auto itr = this->begin(); itr != this->end(); ++itr) {
if (m_compare(itr->first, key)) {
return itr->second;
}
}
throw fkyaml::exception("key not found.");
}
/// @brief Find a value associated to the given key. Throws an exception if the search fails.
/// @tparam KeyType A type for the input key.
/// @param key A key to find a value with.
/// @return const mapped_type& The value associated to the given key.
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/at/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
const mapped_type& at(KeyType&& key) const {
for (auto itr = this->begin(); itr != this->end(); ++itr) {
if (m_compare(itr->first, key)) {
return itr->second;
}
}
throw fkyaml::exception("key not found.");
}
/// @brief Find a value with the given key.
/// @tparam KeyType A type for the input key.
/// @param key A key to find a value with.
/// @return iterator The iterator for the found value, or the result of end().
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/find/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
iterator find(KeyType&& key) noexcept {
for (auto itr = this->begin(); itr != this->end(); ++itr) {
if (m_compare(itr->first, key)) {
return itr;
}
}
return this->end();
}
/// @brief Find a value with the given key.
/// @tparam KeyType A type for the input key.
/// @param key A key to find a value with.
/// @return const_iterator The constant iterator for the found value, or the result of end().
/// @sa https://fktn-k.github.io/fkYAML/api/ordered_map/find/
template <
typename KeyType,
detail::enable_if_t<detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
const_iterator find(KeyType&& key) const noexcept {
for (auto itr = this->begin(); itr != this->end(); ++itr) {
if (m_compare(itr->first, key)) {
return itr;
}
}
return this->end();
}
private:
/// The object for comparing keys.
key_compare m_compare {};
};
FK_YAML_NAMESPACE_END
#endif /* FK_YAML_ORDERED_MAP_HPP_ */