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(); }
94 void swap(MapVector &RHS) {
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