17 #ifndef WPIUTIL_WPI_MAPVECTOR_H 18 #define WPIUTIL_WPI_MAPVECTOR_H 20 #include "wpi/DenseMap.h" 21 #include "wpi/SmallVector.h" 26 #include <type_traits> 35 template<
typename KeyT,
typename ValueT,
36 typename MapType = DenseMap<KeyT, unsigned>,
37 typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
43 std::is_integral<typename MapType::mapped_type>::value,
44 "The mapped_type of the specified Map must be an integral type");
47 using value_type =
typename VectorType::value_type;
48 using size_type =
typename VectorType::size_type;
50 using iterator =
typename VectorType::iterator;
51 using const_iterator =
typename VectorType::const_iterator;
52 using reverse_iterator =
typename VectorType::reverse_iterator;
53 using const_reverse_iterator =
typename VectorType::const_reverse_iterator;
58 return std::move(Vector);
61 size_type size()
const {
return Vector.size(); }
66 Map.reserve(NumEntries);
67 Vector.reserve(NumEntries);
70 iterator begin() {
return Vector.begin(); }
71 const_iterator begin()
const {
return Vector.begin(); }
72 iterator end() {
return Vector.end(); }
73 const_iterator end()
const {
return Vector.end(); }
75 reverse_iterator rbegin() {
return Vector.rbegin(); }
76 const_reverse_iterator rbegin()
const {
return Vector.rbegin(); }
77 reverse_iterator rend() {
return Vector.rend(); }
78 const_reverse_iterator rend()
const {
return Vector.rend(); }
81 return Vector.empty();
84 std::pair<KeyT, ValueT> &front() {
return Vector.front(); }
85 const std::pair<KeyT, ValueT> &front()
const {
return Vector.front(); }
86 std::pair<KeyT, ValueT> &back() {
return Vector.back(); }
87 const std::pair<KeyT, ValueT> &back()
const {
return Vector.back(); }
95 std::swap(Map, RHS.Map);
96 std::swap(Vector, RHS.Vector);
99 ValueT &operator[](
const KeyT &Key) {
100 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
101 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
102 auto &I = Result.first->second;
104 Vector.push_back(std::make_pair(Key, ValueT()));
105 I = Vector.size() - 1;
107 return Vector[I].second;
111 ValueT lookup(
const KeyT &Key)
const {
112 static_assert(std::is_copy_constructible<ValueT>::value,
113 "Cannot call lookup() if ValueT is not copyable.");
114 typename MapType::const_iterator Pos = Map.find(Key);
115 return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
118 std::pair<iterator, bool> insert(
const std::pair<KeyT, ValueT> &KV) {
119 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
120 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
121 auto &I = Result.first->second;
123 Vector.push_back(std::make_pair(KV.first, KV.second));
124 I = Vector.size() - 1;
125 return std::make_pair(std::prev(end()),
true);
127 return std::make_pair(begin() + I,
false);
130 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
132 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
133 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
134 auto &I = Result.first->second;
136 Vector.push_back(std::move(KV));
137 I = Vector.size() - 1;
138 return std::make_pair(std::prev(end()),
true);
140 return std::make_pair(begin() + I,
false);
143 size_type count(
const KeyT &Key)
const {
144 typename MapType::const_iterator Pos = Map.find(Key);
145 return Pos == Map.end()? 0 : 1;
148 iterator find(
const KeyT &Key) {
149 typename MapType::const_iterator Pos = Map.find(Key);
150 return Pos == Map.end()? Vector.end() :
151 (Vector.begin() + Pos->second);
154 const_iterator find(
const KeyT &Key)
const {
155 typename MapType::const_iterator Pos = Map.find(Key);
156 return Pos == Map.end()? Vector.end() :
157 (Vector.begin() + Pos->second);
162 typename MapType::iterator Pos = Map.find(Vector.back().first);
174 typename VectorType::iterator
erase(
typename VectorType::iterator Iterator) {
175 Map.erase(Iterator->first);
176 auto Next = Vector.erase(Iterator);
177 if (Next == Vector.end())
181 size_t Index = Next - Vector.begin();
182 for (
auto &I : Map) {
183 assert(I.second != Index &&
"Index was already erased!");
184 if (I.second > Index)
194 auto Iterator = find(Key);
195 if (Iterator == end())
205 template <
class Predicate>
void remove_if(Predicate Pred);
208 template <
typename KeyT,
typename ValueT,
typename MapType,
typename VectorType>
209 template <
class Function>
211 auto O = Vector.begin();
212 for (
auto I = O, E = Vector.end(); I != E; ++I) {
222 Map[O->first] = O - Vector.begin();
227 Vector.erase(O, Vector.end());
232 template <
typename KeyT,
typename ValueT,
unsigned N>
234 :
MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
235 SmallVector<std::pair<KeyT, ValueT>, N>> {
240 #endif // LLVM_ADT_MAPVECTOR_H This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
size_type erase(const KeyT &Key)
Remove all elements with the key value Key.
Definition: MapVector.h:193
namespace to hold default to_json function
Definition: json_binary_writer.cpp:39
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
void pop_back()
Remove the last element from the vector.
Definition: MapVector.h:161
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
VectorType takeVector()
Clear the MapVector and return the underlying vector.
Definition: MapVector.h:56
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
Definition: MapVector.h:174
void reserve(size_type NumEntries)
Grow the MapVector so that it can contain at least NumEntries items before resizing again...
Definition: MapVector.h:65