MapVector.h revision 289c39965b1b799a22534d759fdf0a26302430d7 
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
83}
84
85#endif
86