代码之家 › 专栏 › 技术社区 › Nathan Fellman

有没有办法限制STL映射的大小?

map stl c++

Nathan Fellman · 技术社区 · 16 年前

我想在C++中实现某种查找表,它将充当缓存。它是用来模拟我正在模拟的硬件。

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

问题是,有没有办法限制大小为了模拟我的硬件是有限大小这一事实,散列值是多少?我希望杂烩是方法返回错误消息或在达到限制时引发异常。

如果没有这样的方法,我将在尝试插入之前检查它的大小,但这似乎是一种不雅观的方法。

3 回复 | 直到 16 年前

David Rodríguez - dribeas 16 年前

第一件事是 map hash table ,而是一个平衡的二叉树。这会影响查找时间 O(log N) 而不是 O(1)

您可以做的最简单的解决方案是将实际的数据结构封装到一个类中,该类检查每个插入中的大小(大小查找) 应该

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;