有没有办法限制STL地图的大小？

Question

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

密钥是非整数的,所以我猜测哈希是有序的.我无意发明轮子所以我打算用std::map它(尽管建议替代品是受欢迎的).

问题是,有没有办法限制哈希的大小来模拟我的硬件有限大小的事实？我希望哈希的insert方法返回错误消息,或者如果达到限制则抛出异常.

如果没有这种方式,我会在尝试插入之前检查它的大小,但这似乎是一种不太优雅的方式.

Answer 1

首先,map结构不是一个结构hash table,而是一个平衡的二叉树.这会对查找时间产生影响,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;

Answer 2

没有办法“自动”限制 an 的大小std::map，仅仅是因为“limited std::map”不再是 anstd::map了。

将 包装std::map在您自己的类中，该类仅在插入之前根据常量检查 的大小std::map，并在达到最大大小时执行您想要的任何操作。