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;
56 VectorType takeVector() {
58 return std::move(Vector);
61 size_type
size()
const {
return Vector.size(); }
65 void reserve(size_type NumEntries) {
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)
193 size_type erase(
const KeyT &Key) {
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
friend reverse_iterator rbegin(StringRef path, Style style)
Get reverse begin iterator over path.
friend reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
friend const_iterator end(StringRef path)
Get end iterator over path.
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:896
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:999
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:941
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:915