MapVector.h revision 009cf9e9a3a386f89db2686a105736481aed10ca 
1//===- llvm/ADT/MapVector.h - Map with deterministic value order *- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
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
13// a std::vector.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_MAPVECTOR_H
18#define LLVM_ADT_MAPVECTOR_H
19
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/DenseMap.h"
22#include <vector>
23
24namespace llvm {
25
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.
29template<typename KeyT, typename ValueT,
30         typename MapType = llvm::DenseMap<KeyT, unsigned>,
31         typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
32class MapVector {
33  typedef typename VectorType::size_type SizeType;
34
35  MapType Map;
36  VectorType Vector;
37
38public:
39  typedef typename VectorType::iterator iterator;
40  typedef typename VectorType::const_iterator const_iterator;
41
42  SizeType size() const {
43    return Vector.size();
44  }
45
46  iterator begin() {
47    return Vector.begin();
48  }
49
50  const_iterator begin() const {
51    return Vector.begin();
52  }
53
54  iterator end() {
55    return Vector.end();
56  }
57
58  const_iterator end() const {
59    return Vector.end();
60  }
61
62  bool empty() const {
63    return Vector.empty();
64  }
65
66  void clear() {
67    Map.clear();
68    Vector.clear();
69  }
70
71  ValueT &operator[](const KeyT &Key) {
72    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
73    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
74    unsigned &I = Result.first->second;
75    if (Result.second) {
76      Vector.push_back(std::make_pair(Key, ValueT()));
77      I = Vector.size() - 1;
78    }
79    return Vector[I].second;
80  }
81
82  unsigned count(const KeyT &Key) const {
83    typename MapType::const_iterator Pos = Map.find(Key);
84    return Pos == Map.end()? 0 : 1;
85  }
86
87  iterator find(const KeyT &Key) {
88    typename MapType::const_iterator Pos = Map.find(Key);
89    return Pos == Map.end()? Vector.end() :
90                            (Vector.begin() + Pos->second);
91  }
92
93  const_iterator find(const KeyT &Key) const {
94    typename MapType::const_iterator Pos = Map.find(Key);
95    return Pos == Map.end()? Vector.end() :
96                            (Vector.begin() + Pos->second);
97  }
98};
99
100}
101
102#endif
103