1 //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a map that provides insertion order iteration. The
11 // interface is purposefully minimal. The key is assumed to be cheap to copy
12 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ADT_MAPVECTOR_H
18 #define LLVM_ADT_MAPVECTOR_H
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallVector.h"
26 #include <type_traits>
32 /// This class implements a map that also provides access to all stored values
33 /// in a deterministic order. The values are kept in a std::vector and the
34 /// mapping is done with DenseMap from Keys to indexes in that vector.
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;
55 /// Clear the MapVector and return the underlying vector.
56 VectorType takeVector() {
58 return std::move(Vector);
61 size_type size() const { return Vector.size(); }
63 /// Grow the MapVector so that it can contain at least \p NumEntries items
64 /// before resizing again.
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(); }
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;
110 // Returns a copy of the value. Only allowed if ValueT is copyable.
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) {
131 // Copy KV.first into the map, then move it into the vector.
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);
160 /// Remove the last element from the vector.
162 typename MapType::iterator Pos = Map.find(Vector.back().first);
167 /// Remove the element given by Iterator.
169 /// Returns an iterator to the element following the one which was removed,
170 /// which may be end().
172 /// \note This is a deceivingly expensive operation (linear time). It's
173 /// usually better to use \a remove_if() if possible.
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())
180 // Update indices in the map.
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)
190 /// Remove all elements with the key value Key.
192 /// Returns the number of elements removed.
193 size_type erase(const KeyT &Key) {
194 auto Iterator = find(Key);
195 if (Iterator == end())
201 /// Remove the elements that match the predicate.
203 /// Erase all elements that match \c Pred in a single pass. Takes linear
205 template <class Predicate> void remove_if(Predicate Pred);
208 template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
209 template <class Function>
210 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
211 auto O = Vector.begin();
212 for (auto I = O, E = Vector.end(); I != E; ++I) {
214 // Erase from the map.
220 // Move the value and update the index in the map.
222 Map[O->first] = O - Vector.begin();
226 // Erase trailing entries in the vector.
227 Vector.erase(O, Vector.end());
230 /// A MapVector that performs no allocations if smaller than a certain
232 template <typename KeyT, typename ValueT, unsigned N>
233 struct SmallMapVector
234 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
235 SmallVector<std::pair<KeyT, ValueT>, N>> {
238 } // end namespace llvm
240 #endif // LLVM_ADT_MAPVECTOR_H