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
|
#pragma once
#include "compact_vector.h"
namespace NYT {
///////////////////////////////////////////////////////////////////////////////
//! A flat map implementation over TCompactVector that tries to keep data inline.
/*!
* Similarly to SmallSet, this is implemented via binary search over a sorted
* vector. Unlike SmallSet, however, this one never falls back to std::map (or
* set) for larger sizes. This means that the flat map is only useful
* - at small sizes, when there's absolutely no chance of it getting big, or
* - when it's filled once and is then only read from.
*
* In return, the flat map provides
* - a smaller size overhead and
* - a guarantee that if data fits into inline storage, it goes there.
*
* Because of the latter, one should be very careful with iterators: virtually
* any call to insert or erase may potentially invalidate all iterators.
*/
template <class K, class V, size_t N>
class TCompactFlatMap
{
public:
// NB: can't make this pair<const K, V> as TCompactVector requires its type
// parameter to be copy-assignable.
using value_type = std::pair<K, V>;
using key_type = K;
using mapped_type = V;
private:
using TStorage = TCompactVector<value_type, N>;
struct TKeyComparer
{
bool operator()(const K& lhs, const value_type& rhs)
{
return lhs < rhs.first;
}
bool operator()(const value_type& lhs, const K& rhs)
{
return lhs.first < rhs;
}
};
public:
using iterator = typename TStorage::iterator;
using const_iterator = typename TStorage::const_iterator;
using size_type = size_t;
TCompactFlatMap() = default;
template <class TInputIterator>
TCompactFlatMap(TInputIterator begin, TInputIterator end);
bool operator==(const TCompactFlatMap& rhs) const;
bool operator!=(const TCompactFlatMap& rhs) const;
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
void reserve(size_type n);
size_type size() const;
int ssize() const;
[[nodiscard]] bool empty() const;
void clear();
void shrink_to_small();
iterator find(const K& k);
const_iterator find(const K& k) const;
iterator lower_bound(const K& k);
const_iterator lower_bound(const K& k) const;
iterator upper_bound(const K& k);
const_iterator upper_bound(const K& k) const;
std::pair<iterator, iterator> equal_range(const K& k);
std::pair<const_iterator, const_iterator> equal_range(const K& k) const;
bool contains(const K& k) const;
std::pair<iterator, bool> insert(const value_type& value);
std::pair<iterator, bool> insert(value_type&& value);
template <class TInputIterator>
void insert(TInputIterator begin, TInputIterator end);
template <class... TArgs>
std::pair<iterator, bool> emplace(TArgs&&... args);
V& operator[](const K& k);
void erase(const K& k);
void erase(iterator pos);
void erase(iterator b, iterator e);
private:
TStorage Storage_;
template <class TArg>
std::pair<iterator, bool> do_insert(TArg&& value);
};
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
#define COMPACT_FLAT_MAP_INL_H_
#include "compact_flat_map-inl.h"
#undef COMPACT_FLAT_MAP_INL_H_
|
