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
|
#ifndef ORDERED_HASH_MAP_INL_H_
#error "Direct inclusion of this file is not allowed, include ordered_hash_map.h"
// For the sake of sane code completion.
#include "ordered_hash_map.h"
#endif
#include <library/cpp/yt/assert/assert.h>
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
std::pair<const TKey, TValue>& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TSelectPair::operator()(TItem& item) const
{
return item;
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
const std::pair<const TKey, TValue>& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TSelectPair::operator()(const TItem& item) const
{
return item;
}
////////////////////////////////////////////////////////////////////////////////
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TOrderedHashMap(const TOrderedHashMap& other)
{
*this = other;
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::operator=(const TOrderedHashMap& other) -> TOrderedHashMap&
{
if (this == &other) {
return *this;
}
clear();
Table_.reserve(other.size());
for (const auto& item : other) {
emplace(item.first, item.second);
}
return *this;
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class... TArgs>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::emplace(TArgs&&... args) -> std::pair<iterator, bool>
{
auto [it, success] = Table_.emplace_unique(std::forward<TArgs>(args)...);
if (success) {
List_.PushBack(&*it);
}
return {MakeMappedIterator(TListIterator(&*it), TSelectPair{}), success};
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class TOtherKey>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::find(const TOtherKey& key) -> iterator
{
auto it = Table_.find(key);
if (it == Table_.end()) {
return MakeMappedIterator(List_.end(), TSelectPair{});
}
return MakeMappedIterator(TListIterator(&*it), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class TOtherKey>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::find(const TOtherKey& key) const -> const_iterator
{
auto it = Table_.find(key);
if (it == Table_.end()) {
return MakeMappedIterator(List_.end(), TSelectPair{});
}
return MakeMappedIterator(TListConstIterator(&*it), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class TOtherKey>
bool TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::contains(const TOtherKey& key) const
{
return Table_.find(key) != Table_.end();
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class TOtherKey>
TValue& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::operator[](const TOtherKey& key)
{
typename TTable::insert_ctx ctx = nullptr;
auto it = Table_.find_i(key, ctx);
if (it != Table_.end()) {
return it->second;
}
it = Table_.emplace_direct(ctx, std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple());
List_.PushBack(&*it);
return it->second;
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
template <class TOtherKey>
size_t TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::erase(const TOtherKey& key)
{
return Table_.erase_one(key);
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
void TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::erase(iterator it)
{
erase(it->first);
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::begin() -> iterator
{
return MakeMappedIterator(List_.begin(), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::end() -> iterator
{
return MakeMappedIterator(List_.end(), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::begin() const -> const_iterator
{
return MakeMappedIterator(List_.begin(), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::end() const -> const_iterator
{
return MakeMappedIterator(List_.end(), TSelectPair{});
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
size_t TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::size() const
{
return Table_.size();
}
template <class TKey, class TValue, class THashFunction, class TEqualFunction>
void TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::clear()
{
Table_.clear();
YT_ASSERT(List_.begin() == List_.end());
}
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
|
