tags:

views:

177

answers:

3

I want to implement some sort of lookup table in C++ that will act as a cache. It is meant to emulate a piece of hardware I'm simulating.

The keys are non-integer, so I'm guessing a hash is in order. I have no intention of inventing the wheel so I intend to use std::map for this (though suggestions for alternatives are welcome).

The question is, is there any way to limit the size of the hash to emulate the fact that my hardware is of finite size? I'd expect the hash's insert method to return an error message or throw an exception if the limit is reached.

If there is no such way, I'll simply check its size before trying to insert, but that seems like an inelegant way to do it.

+5  A: 

First thing is that a map structure is not a hash table, but rather a balanced binary tree. This has an impact in the lookup times O(log N) instead of O(1) for an optimal hash implementation. This may or not affect your problem (if the number of actual keys and operations is small it can suffice, but the emulation of the cache can be somehow suboptimal.

The simplest solution that you can do is encapsulate the actual data structure into a class that checks the size in each insertion (size lookups should be implemented in constant time in all STL implementations) and fails if you are trying to add one too many elements.

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;
David Rodríguez - dribeas
The implementation details of a given std::map are outside the scope of the C++ specification. There's no guarantee a map is a tree.
Nick Bastin
@Nick: true, but the complexity requirements for std::map in the standard don't leave much choice for the implementation. I challenge you to find a standard-conformant std::map implementation that's not a tree :)
sbk
I have already answered the equivalent to the comment in the question. Take all requirements from the standard and try to come up with a different implementation (i.e. try to implement an ever growing map for which insertions take `O(log N)` with a hash) or alternatively, mention one STL implementation for which maps are not balanced trees.
David Rodríguez - dribeas
@Nick: As far as I know, only a tree or skip list can satisfy the constraints the standard places on a `map`/`set`. In any case, it is *not* a hash map. (And was always intended to be a tree.)
GMan
+3  A: 

There is no way to "automatically" limit the size of an std::map, simply because a "limited std::map" would not be an std::map anymore.

Wrap the std::map in a class of your own which just checks the size of the std::map against a constant before inserting, and does whatever you want in case the maximum size has been reached.

Daniel Daranas
+1  A: 

If you're implementing LRU caches or similar, I've found boost::bimap to be invaluable. Use one index to be the primary "object ID" key (which can be an efficient vector view if you have a simple enumeration of objects), and the other index can be an ordered timestamp.

timday