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"
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,
30 typename MapType = llvm::DenseMap<KeyT, unsigned>,
31 typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
33 typedef typename VectorType::size_type SizeType;
39 typedef typename VectorType::iterator iterator;
40 typedef typename VectorType::const_iterator const_iterator;
42 SizeType size() const {
47 return Vector.begin();
50 const_iterator begin() const {
51 return Vector.begin();
58 const_iterator end() const {
63 return Vector.empty();
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;
76 Vector.push_back(std::make_pair(Key, ValueT()));
77 I = Vector.size() - 1;
79 return Vector[I].second;
82 unsigned count(const KeyT &Key) const {
83 typename MapType::const_iterator Pos = Map.find(Key);
84 return Pos == Map.end()? 0 : 1;