1 //===- llvm/ADT/MapVector.h - Map with 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 also provides access to all stored values
11 // in a deterministic order via the getValues method. Note that the iteration
12 // order itself is just the DenseMap order and not deterministic. The interface
13 // is purposefully minimal.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ADT_MAPVECTOR_H
18 #define LLVM_ADT_MAPVECTOR_H
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
26 /// This class implements a map that also provides access to all stored values
27 /// in a deterministic order. The values are kept in a std::vector and the
28 /// mapping is done with DenseMap from Keys to indexes in that vector.
29 template<typename KeyT, typename ValueT>
31 typedef llvm::DenseMap<KeyT, unsigned> MapType;
32 typedef std::vector<ValueT> VectorType;
33 typedef typename VectorType::size_type SizeType;
39 // The keys and values are not stored close to each other, so the iterator
40 // operator->() cannot return a pointer to a std::pair like a DenseMap does.
41 // Instead it returns a FakePair that contains references to Key and Value.
42 // This lets code using this to look the same as if using a regular DenseMap.
43 template<bool IsConst>
45 typedef typename conditional<IsConst, const ValueT, ValueT>::type VT;
48 FakePair(const KeyT &K, VT &V) : first(K), second(V) {
50 FakePair *operator->() {
55 template<bool IsConst>
56 class IteratorTemplate {
57 typedef typename MapType::const_iterator WrappedIteratorType;
58 WrappedIteratorType WrappedI;
60 typename conditional<IsConst, const VectorType, VectorType>::type VT;
62 typedef FakePair<IsConst> PairType;
63 friend class IteratorTemplate<true>;
66 IteratorTemplate(WrappedIteratorType I, VT &V) :
67 WrappedI(I), VecRef(V) {
70 // If IsConst is true this is a converting constructor from iterator to
71 // const_iterator and the default copy constructor is used.
72 // Otherwise this is a copy constructor for iterator.
73 IteratorTemplate(const IteratorTemplate<false>& I) :
74 WrappedI(I.WrappedI), VecRef(I.VecRef) {
77 bool operator!=(const IteratorTemplate &RHS) const {
78 return WrappedI != RHS.WrappedI;
81 IteratorTemplate &operator++() { // Preincrement
86 PairType operator->() {
87 unsigned Pos = WrappedI->second;
88 PairType Ret(WrappedI->first, VecRef[Pos]);
93 typedef IteratorTemplate<false> iterator;
94 typedef IteratorTemplate<true> const_iterator;
96 SizeType size() const {
101 return iterator(Map.begin(), this->Vector);
104 const_iterator begin() const {
105 return const_iterator(Map.begin(), this->Vector);
109 return iterator(Map.end(), this->Vector);
112 const_iterator end() const {
113 return const_iterator(Map.end(), this->Vector);
120 typedef typename VectorType::iterator value_iterator;
121 typedef typename VectorType::const_iterator const_value_iterator;
123 value_iterator value_begin() {
124 return Vector.begin();
127 const_value_iterator value_begin() const {
128 return Vector.begin();
131 value_iterator value_end() {
135 const_value_iterator value_end() const {
139 ValueT &operator[](const KeyT &Key) {
140 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
141 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
142 unsigned &I = Result.first->second;
144 Vector.push_back(ValueT());
145 I = Vector.size() - 1;