CardinalityQueue.cpp

template <typename T>
class CardinalityQueue {
 public:
  CardinalityQueue() : cardinality_(0) {}

  void Push(const T& value) {
    queue_.push(value);
    if (map_[value]++ == 0) ++cardinality_;
  }

  void Pop() {
    if (--map_[queue_.front()] == 0) --cardinality_;
    queue_.pop();
  }

  // number of non-zero keys
  size_t Cardinality() const { return cardinality_; }

 private:
  std::queue<T> queue_;
  std::map<T, size_t> map_;
  size_t cardinality_;
};