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
|
#pragma once
#include <library/cpp/iterator/mapped.h>
#include <util/generic/hash_table.h>
#include <util/generic/intrlist.h>
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
//! A hash map where the iteration order is the insertion order.
template <
class TKey,
class TValue,
class THashFunction = THash<TKey>,
class TEqualFunction = TEqualTo<TKey>
>
class TOrderedHashMap
{
private:
struct TItem
: public std::pair<const TKey, TValue>
, public TIntrusiveListItem<TItem>
{
using std::pair<const TKey, TValue>::pair;
};
struct TSelectPair
{
std::pair<const TKey, TValue>& operator()(TItem& item) const;
const std::pair<const TKey, TValue>& operator()(const TItem& item) const;
};
using TList = TIntrusiveList<TItem>;
using TListIterator = TList::iterator;
using TListConstIterator = TList::const_iterator;
public:
using iterator = TMappedIterator<TListIterator, TSelectPair>;
using const_iterator = TMappedIterator<TListConstIterator, TSelectPair>;
public:
TOrderedHashMap() = default;
TOrderedHashMap(const TOrderedHashMap& other);
TOrderedHashMap(TOrderedHashMap&& other) = default;
TOrderedHashMap& operator=(const TOrderedHashMap& other);
TOrderedHashMap& operator=(TOrderedHashMap&& other) = default;
template <typename... TArgs>
std::pair<iterator, bool> emplace(TArgs&&... args);
template <class TOtherKey>
iterator find(const TOtherKey& key);
template <class TOtherKey>
const_iterator find(const TOtherKey& key) const;
template <class TOtherKey>
bool contains(const TOtherKey& key) const;
template <class TOtherKey>
TValue& operator[](const TOtherKey& key);
template <class TOtherKey>
size_t erase(const TOtherKey& key);
void erase(iterator it);
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
size_t size() const;
void clear();
private:
using TTable = THashTable<TItem, TKey, THashFunction, TSelect1st, TEqualFunction, std::allocator<TKey>>;
private:
TList List_;
TTable Table_;
};
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
#define ORDERED_HASH_MAP_INL_H_
#include "ordered_hash_map-inl.h"
#undef ORDERED_HASH_MAP_INL_H_
|
