1 //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements a map that provides insertion order iteration. The
10 // interface is purposefully minimal. The key is assumed to be cheap to copy
11 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ADT_MAPVECTOR_H
17 #define LLVM_ADT_MAPVECTOR_H
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallVector.h"
25 #include <type_traits>
31 /// This class implements a map that also provides access to all stored values
32 /// in a deterministic order. The values are kept in a std::vector and the
33 /// mapping is done with DenseMap from Keys to indexes in that vector.
34 template<typename KeyT
, typename ValueT
,
35 typename MapType
= DenseMap
<KeyT
, unsigned>,
36 typename VectorType
= std::vector
<std::pair
<KeyT
, ValueT
>>>
42 std::is_integral
<typename
MapType::mapped_type
>::value
,
43 "The mapped_type of the specified Map must be an integral type");
46 using value_type
= typename
VectorType::value_type
;
47 using size_type
= typename
VectorType::size_type
;
49 using iterator
= typename
VectorType::iterator
;
50 using const_iterator
= typename
VectorType::const_iterator
;
51 using reverse_iterator
= typename
VectorType::reverse_iterator
;
52 using const_reverse_iterator
= typename
VectorType::const_reverse_iterator
;
54 /// Clear the MapVector and return the underlying vector.
55 VectorType
takeVector() {
57 return std::move(Vector
);
60 size_type
size() const { return Vector
.size(); }
62 /// Grow the MapVector so that it can contain at least \p NumEntries items
63 /// before resizing again.
64 void reserve(size_type NumEntries
) {
65 Map
.reserve(NumEntries
);
66 Vector
.reserve(NumEntries
);
69 iterator
begin() { return Vector
.begin(); }
70 const_iterator
begin() const { return Vector
.begin(); }
71 iterator
end() { return Vector
.end(); }
72 const_iterator
end() const { return Vector
.end(); }
74 reverse_iterator
rbegin() { return Vector
.rbegin(); }
75 const_reverse_iterator
rbegin() const { return Vector
.rbegin(); }
76 reverse_iterator
rend() { return Vector
.rend(); }
77 const_reverse_iterator
rend() const { return Vector
.rend(); }
80 return Vector
.empty();
83 std::pair
<KeyT
, ValueT
> &front() { return Vector
.front(); }
84 const std::pair
<KeyT
, ValueT
> &front() const { return Vector
.front(); }
85 std::pair
<KeyT
, ValueT
> &back() { return Vector
.back(); }
86 const std::pair
<KeyT
, ValueT
> &back() const { return Vector
.back(); }
93 void swap(MapVector
&RHS
) {
94 std::swap(Map
, RHS
.Map
);
95 std::swap(Vector
, RHS
.Vector
);
98 ValueT
&operator[](const KeyT
&Key
) {
99 std::pair
<KeyT
, typename
MapType::mapped_type
> Pair
= std::make_pair(Key
, 0);
100 std::pair
<typename
MapType::iterator
, bool> Result
= Map
.insert(Pair
);
101 auto &I
= Result
.first
->second
;
103 Vector
.push_back(std::make_pair(Key
, ValueT()));
104 I
= Vector
.size() - 1;
106 return Vector
[I
].second
;
109 // Returns a copy of the value. Only allowed if ValueT is copyable.
110 ValueT
lookup(const KeyT
&Key
) const {
111 static_assert(std::is_copy_constructible
<ValueT
>::value
,
112 "Cannot call lookup() if ValueT is not copyable.");
113 typename
MapType::const_iterator Pos
= Map
.find(Key
);
114 return Pos
== Map
.end()? ValueT() : Vector
[Pos
->second
].second
;
117 std::pair
<iterator
, bool> insert(const std::pair
<KeyT
, ValueT
> &KV
) {
118 std::pair
<KeyT
, typename
MapType::mapped_type
> Pair
= std::make_pair(KV
.first
, 0);
119 std::pair
<typename
MapType::iterator
, bool> Result
= Map
.insert(Pair
);
120 auto &I
= Result
.first
->second
;
122 Vector
.push_back(std::make_pair(KV
.first
, KV
.second
));
123 I
= Vector
.size() - 1;
124 return std::make_pair(std::prev(end()), true);
126 return std::make_pair(begin() + I
, false);
129 std::pair
<iterator
, bool> insert(std::pair
<KeyT
, ValueT
> &&KV
) {
130 // Copy KV.first into the map, then move it into the vector.
131 std::pair
<KeyT
, typename
MapType::mapped_type
> Pair
= std::make_pair(KV
.first
, 0);
132 std::pair
<typename
MapType::iterator
, bool> Result
= Map
.insert(Pair
);
133 auto &I
= Result
.first
->second
;
135 Vector
.push_back(std::move(KV
));
136 I
= Vector
.size() - 1;
137 return std::make_pair(std::prev(end()), true);
139 return std::make_pair(begin() + I
, false);
142 size_type
count(const KeyT
&Key
) const {
143 typename
MapType::const_iterator Pos
= Map
.find(Key
);
144 return Pos
== Map
.end()? 0 : 1;
147 iterator
find(const KeyT
&Key
) {
148 typename
MapType::const_iterator Pos
= Map
.find(Key
);
149 return Pos
== Map
.end()? Vector
.end() :
150 (Vector
.begin() + Pos
->second
);
153 const_iterator
find(const KeyT
&Key
) const {
154 typename
MapType::const_iterator Pos
= Map
.find(Key
);
155 return Pos
== Map
.end()? Vector
.end() :
156 (Vector
.begin() + Pos
->second
);
159 /// Remove the last element from the vector.
161 typename
MapType::iterator Pos
= Map
.find(Vector
.back().first
);
166 /// Remove the element given by Iterator.
168 /// Returns an iterator to the element following the one which was removed,
169 /// which may be end().
171 /// \note This is a deceivingly expensive operation (linear time). It's
172 /// usually better to use \a remove_if() if possible.
173 typename
VectorType::iterator
erase(typename
VectorType::iterator Iterator
) {
174 Map
.erase(Iterator
->first
);
175 auto Next
= Vector
.erase(Iterator
);
176 if (Next
== Vector
.end())
179 // Update indices in the map.
180 size_t Index
= Next
- Vector
.begin();
181 for (auto &I
: Map
) {
182 assert(I
.second
!= Index
&& "Index was already erased!");
183 if (I
.second
> Index
)
189 /// Remove all elements with the key value Key.
191 /// Returns the number of elements removed.
192 size_type
erase(const KeyT
&Key
) {
193 auto Iterator
= find(Key
);
194 if (Iterator
== end())
200 /// Remove the elements that match the predicate.
202 /// Erase all elements that match \c Pred in a single pass. Takes linear
204 template <class Predicate
> void remove_if(Predicate Pred
);
207 template <typename KeyT
, typename ValueT
, typename MapType
, typename VectorType
>
208 template <class Function
>
209 void MapVector
<KeyT
, ValueT
, MapType
, VectorType
>::remove_if(Function Pred
) {
210 auto O
= Vector
.begin();
211 for (auto I
= O
, E
= Vector
.end(); I
!= E
; ++I
) {
213 // Erase from the map.
219 // Move the value and update the index in the map.
221 Map
[O
->first
] = O
- Vector
.begin();
225 // Erase trailing entries in the vector.
226 Vector
.erase(O
, Vector
.end());
229 /// A MapVector that performs no allocations if smaller than a certain
231 template <typename KeyT
, typename ValueT
, unsigned N
>
232 struct SmallMapVector
233 : MapVector
<KeyT
, ValueT
, SmallDenseMap
<KeyT
, unsigned, N
>,
234 SmallVector
<std::pair
<KeyT
, ValueT
>, N
>> {
237 } // end namespace llvm
239 #endif // LLVM_ADT_MAPVECTOR_H