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 class 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
  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   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