c++ - 有没有办法限制 STL Map 的大小？

Question

我想在 C++ 中实现某种查找表，用作缓存。它旨在模拟我正在模拟的一个硬件。

键是非整数，所以我猜散列是有序的。我无意发明轮子，所以我打算为此使用 std::map (尽管欢迎提出替代方案的建议)。

问题是，有没有办法限制散列的 size 以模拟我的硬件大小有限的事实？我希望哈希的 insert 方法在达到限制时返回错误消息或抛出异常。

如果没有这样的方法，我会在尝试插入之前简单地检查它的大小，但这似乎是一种不雅的方法。

Answer 1

首先，map 结构不是哈希表，而是平衡的二叉树。这会影响查找时间 O(log N) 而不是 O(1) 以获得最佳哈希实现。这可能会或不会影响您的问题(如果实际键和操作的数量很少就足够了，但是缓存的模拟可能不是最理想的。

您可以做的最简单的解决方案是将实际数据结构封装到一个类中，该类检查每次插入的大小(在所有 STL 实现中，大小查找应该在恒定时间内实现)，如果出现以下情况则失败您尝试添加的元素过多。

class cache {
public:
   static const int max_size = 100;
   typedef std::map<key_t, value_t> cache_map_t;
   void add( key_t key, value_t value ) {
      cache_map_t::const_iterator it = m_table.find( key );
      if ( it != m_table.end() && m_table.size() == max_size ) { 
         // handle error, throw exception...
      } else {
         m_table.insert( it, std::make_pair(key,value) );
      }
   }
private:
   cache_map_t m_table;
};
// Don't forget, in just one translation unit:
const int cache::max_size;