src/mruset.h

   1 // Copyright (c) 2012 The Bitcoin developers
   2 // Distributed under the MIT/X11 software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #ifndef BITCOIN_MRUSET_H
   6 #define BITCOIN_MRUSET_H
   7
   8 #include <deque>
   9 #include <set>
  10 #include <utility>
  11
  12 /** STL-like set container that only keeps the most recent N elements. */
  13 template <typename T> class mruset
  14 {
  15 public:
  16     typedef T key_type;
  17     typedef T value_type;
  18     typedef typename std::set<T>::iterator iterator;
  19     typedef typename std::set<T>::const_iterator const_iterator;
  20     typedef typename std::set<T>::size_type size_type;
  21
  22 protected:
  23     std::set<T> set;
  24     std::deque<T> queue;
  25     size_type nMaxSize;
  26
  27 public:
  28     mruset(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; }
  29     iterator begin() const { return set.begin(); }
  30     iterator end() const { return set.end(); }
  31     size_type size() const { return set.size(); }
  32     bool empty() const { return set.empty(); }
  33     iterator find(const key_type& k) const { return set.find(k); }
  34     size_type count(const key_type& k) const { return set.count(k); }
  35     void clear() { set.clear(); queue.clear(); }
  36     bool inline friend operator==(const mruset<T>& a, const mruset<T>& b) { return a.set == b.set; }
  37     bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
  38     bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
  39     std::pair<iterator, bool> insert(const key_type& x)
  40     {
  41         std::pair<iterator, bool> ret = set.insert(x);
  42         if (ret.second)
  43         {
  44             if (nMaxSize && queue.size() == nMaxSize)
  45             {
  46                 set.erase(queue.front());
  47                 queue.pop_front();
  48             }
  49             queue.push_back(x);
  50         }
  51         return ret;
  52     }
  53     size_type max_size() const { return nMaxSize; }
  54     size_type max_size(size_type s)
  55     {
  56         if (s)
  57             while (queue.size() > s)
  58             {
  59                 set.erase(queue.front());
  60                 queue.pop_front();
  61             }
  62         nMaxSize = s;
  63         return nMaxSize;
  64     }
  65 };
  66
  67 #endif