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 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/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/STLExtras.h"
27 /// This class implements a map that also provides access to all stored values
28 /// in a deterministic order. The values are kept in a std::vector and the
29 /// mapping is done with DenseMap from Keys to indexes in that vector.
30 template<typename KeyT, typename ValueT,
31 typename MapType = llvm::DenseMap<KeyT, unsigned>,
32 typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
34 typedef typename VectorType::size_type SizeType;
40 typedef typename VectorType::iterator iterator;
41 typedef typename VectorType::const_iterator const_iterator;
43 SizeType size() const {
48 return Vector.begin();
51 const_iterator begin() const {
52 return Vector.begin();
59 const_iterator end() const {
64 return Vector.empty();
67 std::pair<KeyT, ValueT> &front() { return Vector.front(); }
68 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
69 std::pair<KeyT, ValueT> &back() { return Vector.back(); }
70 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); }
77 ValueT &operator[](const KeyT &Key) {
78 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
79 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
80 unsigned &I = Result.first->second;
82 Vector.push_back(std::make_pair(Key, ValueT()));
83 I = Vector.size() - 1;
85 return Vector[I].second;
88 ValueT lookup(const KeyT &Key) const {
89 typename MapType::const_iterator Pos = Map.find(Key);
90 return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
93 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
94 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
95 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
96 unsigned &I = Result.first->second;
98 Vector.push_back(std::make_pair(KV.first, KV.second));
99 I = Vector.size() - 1;
100 return std::make_pair(llvm::prior(end()), true);
102 return std::make_pair(begin() + I, false);
105 unsigned count(const KeyT &Key) const {
106 typename MapType::const_iterator Pos = Map.find(Key);
107 return Pos == Map.end()? 0 : 1;
110 iterator find(const KeyT &Key) {
111 typename MapType::const_iterator Pos = Map.find(Key);
112 return Pos == Map.end()? Vector.end() :
113 (Vector.begin() + Pos->second);
116 const_iterator find(const KeyT &Key) const {
117 typename MapType::const_iterator Pos = Map.find(Key);
118 return Pos == Map.end()? Vector.end() :
119 (Vector.begin() + Pos->second);
122 /// \brief Remove the last element from the vector.
124 typename MapType::iterator Pos = Map.find(Vector.back().first);