bitcoin 里面的limitedmap 基本上是在std::map 上实现了优先队列的功能, 主要用在记录向对等节点索取inv 对应的时间记录。 以前不了解, stl 容器可以如此灵活使用， 把多个容器组合一起，完成更强大的功能。limitedmap 的主要技巧是，使用一个multimap(limitedmap 中多个不同的key可能映射到同一个value)， 记录map里面value及其在map的位置(迭代器)， bitcoin 里面有不少这种用法， 一个容器的元素是另一个容器的迭代器。

template 
    
     class limitedmap{public:    typedef K key_type;    typedef V mapped_type;    typedef std::pair
     
       value_type;    typedef typename std::map
      
       ::const_iterator const_iterator;    typedef typename std::map
       
        ::size_type size_type;protected:    std::map
        
          map;    typedef typename std::map
         
          ::iterator iterator; std::multimap
          
            rmap; typedef typename std::multimap
           
            ::iterator rmap_iterator; size_type nMaxSize;public: // 构造器建立class 的不变量，元素size 不超过nMaxSizeIn explicit limitedmap(size_type nMaxSizeIn) { assert(nMaxSizeIn > 0); nMaxSize = nMaxSizeIn; } //迭代器，只读方法都代理给底层的std::map const_iterator begin() const { return map.begin(); } const_iterator end() const { return map.end(); } size_type size() const { return map.size(); } bool empty() const { return map.empty(); } const_iterator find(const key_type& k) const { return map.find(k); } size_type count(const key_type& k) const { return map.count(k); } //这里插入采用了先插入新元素， 然后再检测个数超限，超限后再删除最小的元素(破坏了不变量，然后再恢复回来) //为什么不插入前，先检测个数是否超限， 已经超限就返回，不用再后来删除了 //每次往底层map成功地添加一个元素，就更新multimap, 记录新的值在map中的位置 void insert(const value_type& x) { std::pair
            
              ret = map.insert(x); if (ret.second) { if (map.size() > nMaxSize) { map.erase(rmap.begin()->second); rmap.erase(rmap.begin()); } rmap.insert(make_pair(x.second, ret.first)); } } //按key删除对应的元素，首先再map中查找k对应的value //然后拿value，作为multimap 中的key， 在multimap中定位key是value的区间 //在区间内搜索哪个条目是记录map 中k 的记录 void erase(const key_type& k) { iterator itTarget = map.find(k); if (itTarget == map.end()) return; std::pair
             
               itPair = rmap.equal_range(itTarget->second); for (rmap_iterator it = itPair.first; it != itPair.second; ++it) if (it->second == itTarget) { rmap.erase(it); map.erase(itTarget); return; } // Shouldn't ever get here assert(0); } //类似insert 的逻辑 void update(const_iterator itIn, const mapped_type& v) { // Using map::erase() with empty range instead of map::find() to get a non-const iterator, // since it is a constant time operation in C++11. For more details, see // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator iterator itTarget = map.erase(itIn, itIn); if (itTarget == map.end()) return; std::pair
              
                itPair = rmap.equal_range(itTarget->second); for (rmap_iterator it = itPair.first; it != itPair.second; ++it) if (it->second == itTarget) { rmap.erase(it); itTarget->second = v; rmap.insert(make_pair(v, itTarget)); return; } // Shouldn't ever get here assert(0); } size_type max_size() const { return nMaxSize; } //overload max_size 成员， 调整max limit 数目 size_type max_size(size_type s) { assert(s > 0); while (map.size() > s) { map.erase(rmap.begin()->second); rmap.erase(rmap.begin()); } nMaxSize = s; return nMaxSize; }};