MapVector.h revision c312f098999d4640cf91934632ccecfc9ef30b85 
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>
30class MapVector {
31  typedef llvm::DenseMap<KeyT, unsigned> MapType;
32  typedef std::vector<std::pair<KeyT, ValueT> > VectorType;
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  ValueT &operator[](const KeyT &Key) {
67    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
68    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
69    unsigned &I = Result.first->second;
70    if (Result.second) {
71      Vector.push_back(std::make_pair(Key, ValueT()));
72      I = Vector.size() - 1;
73    }
74    return Vector[I].second;
75  }
76};
77
78}
79
80#endif
81