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
177
178
179
180
181
182
183
184
|
// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef BASE_CONTAINERS_FLAT_SET_H_
#define BASE_CONTAINERS_FLAT_SET_H_
#include <algorithm>
#include <functional>
#include <vector>
#include "base/containers/flat_tree.h"
namespace base {
// flat_set is a container with a std::set-like interface that stores its
// contents in a sorted container, by default a vector.
//
// Its implementation mostly tracks the corresponding standardization proposal
// https://wg21.link/P1222.
//
// Please see //base/containers/README.md for an overview of which container
// to select.
//
// PROS
//
// - Good memory locality.
// - Low overhead, especially for smaller sets.
// - Performance is good for more workloads than you might expect (see
// overview link above).
// - Supports C++14 set interface.
//
// CONS
//
// - Inserts and removals are O(n).
//
// IMPORTANT NOTES
//
// - Iterators are invalidated across mutations.
// - If possible, construct a flat_set in one operation by inserting into
// a container and moving that container into the flat_set constructor.
// - For multiple removals use base::EraseIf() which is O(n) rather than
// O(n * removed_items).
//
// QUICK REFERENCE
//
// Most of the core functionality is inherited from flat_tree. Please see
// flat_tree.h for more details for most of these functions. As a quick
// reference, the functions available are:
//
// Constructors (inputs need not be sorted):
// flat_set(const flat_set&);
// flat_set(flat_set&&);
// flat_set(InputIterator first, InputIterator last,
// const Compare& compare = Compare());
// flat_set(const container_type& items,
// const Compare& compare = Compare());
// flat_set(container_type&& items,
// const Compare& compare = Compare()); // Re-use storage.
// flat_set(std::initializer_list<value_type> ilist,
// const Compare& comp = Compare());
//
// Constructors (inputs need to be sorted):
// flat_set(sorted_unique_t,
// InputIterator first, InputIterator last,
// const Compare& compare = Compare());
// flat_set(sorted_unique_t,
// const container_type& items,
// const Compare& compare = Compare());
// flat_set(sorted_unique_t,
// container_type&& items,
// const Compare& compare = Compare()); // Re-use storage.
// flat_set(sorted_unique_t,
// std::initializer_list<value_type> ilist,
// const Compare& comp = Compare());
//
// Assignment functions:
// flat_set& operator=(const flat_set&);
// flat_set& operator=(flat_set&&);
// flat_set& operator=(initializer_list<Key>);
//
// Memory management functions:
// void reserve(size_t);
// size_t capacity() const;
// void shrink_to_fit();
//
// Size management functions:
// void clear();
// size_t size() const;
// size_t max_size() const;
// bool empty() const;
//
// Iterator functions:
// iterator begin();
// const_iterator begin() const;
// const_iterator cbegin() const;
// iterator end();
// const_iterator end() const;
// const_iterator cend() const;
// reverse_iterator rbegin();
// const reverse_iterator rbegin() const;
// const_reverse_iterator crbegin() const;
// reverse_iterator rend();
// const_reverse_iterator rend() const;
// const_reverse_iterator crend() const;
//
// Insert and accessor functions:
// pair<iterator, bool> insert(const key_type&);
// pair<iterator, bool> insert(key_type&&);
// void insert(InputIterator first, InputIterator last);
// iterator insert(const_iterator hint, const key_type&);
// iterator insert(const_iterator hint, key_type&&);
// pair<iterator, bool> emplace(Args&&...);
// iterator emplace_hint(const_iterator, Args&&...);
//
// Underlying type functions:
// container_type extract() &&;
// void replace(container_type&&);
//
// Erase functions:
// iterator erase(iterator);
// iterator erase(const_iterator);
// iterator erase(const_iterator first, const_iterator& last);
// template <typename K> size_t erase(const K& key);
//
// Comparators (see std::set documentation).
// key_compare key_comp() const;
// value_compare value_comp() const;
//
// Search functions:
// template <typename K> size_t count(const K&) const;
// template <typename K> iterator find(const K&);
// template <typename K> const_iterator find(const K&) const;
// template <typename K> bool contains(const K&) const;
// template <typename K> pair<iterator, iterator> equal_range(K&);
// template <typename K> iterator lower_bound(const K&);
// template <typename K> const_iterator lower_bound(const K&) const;
// template <typename K> iterator upper_bound(const K&);
// template <typename K> const_iterator upper_bound(const K&) const;
//
// General functions:
// void swap(flat_set&);
//
// Non-member operators:
// bool operator==(const flat_set&, const flat_set);
// bool operator!=(const flat_set&, const flat_set);
// bool operator<(const flat_set&, const flat_set);
// bool operator>(const flat_set&, const flat_set);
// bool operator>=(const flat_set&, const flat_set);
// bool operator<=(const flat_set&, const flat_set);
//
template <class Key,
class Compare = std::less<>,
class Container = std::vector<Key>>
using flat_set = typename ::base::internal::
flat_tree<Key, std::identity, Compare, Container>;
// Utility function to simplify constructing a flat_set from a fixed list
// of keys. The keys are obtained by applying the projection |proj| to the
// |unprojected_elements|. The set's keys are sorted by |comp|.
//
// Example usage (creates a set {16, 9, 4, 1}):
// auto set = base::MakeFlatSet<int>(
// std::vector<int>{1, 2, 3, 4}, [](int i, int j) { return i > j; },
// [](int i) { return i * i; });
template <class Key,
class Compare = std::less<>,
class Container = std::vector<Key>,
class InputContainer,
class Projection = std::identity>
constexpr flat_set<Key, Compare, Container> MakeFlatSet(
const InputContainer& unprojected_elements,
const Compare& comp = Compare(),
const Projection& proj = Projection()) {
Container elements;
internal::ReserveIfSupported(elements, unprojected_elements);
std::ranges::transform(unprojected_elements, std::back_inserter(elements),
proj);
return flat_set<Key, Compare, Container>(std::move(elements), comp);
}
} // namespace base
#endif // BASE_CONTAINERS_FLAT_SET_H_
|
