include/llvm/ADT/MapVector.h

   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
  24 namespace 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.
  29 template<typename KeyT, typename ValueT,
  30          typename MapType = llvm::DenseMap<KeyT, unsigned>,
  31          typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
  32 class MapVector {
  33   typedef typename VectorType::size_type SizeType;
  34
  35   MapType Map;
  36   VectorType Vector;
  37
  38 public:
  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