22

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.

Michael Aaron Safyan
  • 93,612
  • 16
  • 138
  • 200
Nathan Fellman
  • 122,701
  • 101
  • 260
  • 319
  • What you can do is to throw `bad_alloc`, and that can be done by implementing your own allocator. Here is all what you need: http://stackoverflow.com/questions/1591591/can-one-leverage-stdbasic-string-to-implement-a-string-having-a-length-limitati/1591758#1591758 – Khaled Alshaya Apr 26 '10 at 07:29
  • 5
    A map is a tree, not a hash table structure. It will allow for lookups but will search in `O(log N)` (as compared to `O(1)` for an optimal hash) – David Rodríguez - dribeas Apr 26 '10 at 07:30
  • @David: A map can be implemented however the author chose, so long as that implementation satisfies the STL complexity requirements for the type. It's best not to imagine a given STL type implemented in any particular way - the complexity requirements are all that are guaranteed. – Nick Bastin Apr 26 '10 at 07:37
  • 2
    @Nick, I know that the standard does not require a concrete data structure, but the requirements in time complexity in the comment hold: lookup operations in a map are `O(log N)` in the standard. It is also a fact that all existing STL implementations do use trees internally for maps (so even if from a theoretical point of view the implication map => tree does not hold, from a pragmatic point of view it does). Part of the reason is that it is hard to come up with a different data structure for which all requirements in all operations that the standard makes hold. – David Rodríguez - dribeas Apr 26 '10 at 07:46
  • The namespace is "std" not "stl", so I have edited the question to say "std::map" instead of "stl::map". – Michael Aaron Safyan Apr 26 '10 at 07:55
  • 2
    @Nick: A hash table requires that keys are hashable; trees require that keys are ordered. The C++ standard does require that `std::map` keys are sortable, but does not require them to be hashable. Also, itertion over a `std::map` has to iterate over all keys in that precise sort order. Hence, we can say for certain that the standard doesn't allow `std::map` to be a hashtable. – MSalters Apr 26 '10 at 11:35

4 Answers4

13

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
  • 204,818
  • 23
  • 294
  • 489
  • 2
    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 Apr 26 '10 at 07:40
  • 1
    @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 Apr 26 '10 at 07:50
  • 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 Apr 26 '10 at 07:51
  • 2
    @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.) – GManNickG Apr 26 '10 at 07:54
6

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
  • 22,454
  • 9
  • 63
  • 116
2

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.

Jonathan Lidbeck
  • 1,555
  • 1
  • 14
  • 15
timday
  • 24,582
  • 12
  • 83
  • 135
0

I have the same use case. Though it might not align completely with the question but the concept seems similar.

#include <array>

int main() {
    std::array<std::pair<int, int>, 5> myMap;
    myMap[0] = std::make_pair(1, 10);
    myMap[1] = std::make_pair(2, 20);
    myMap[2] = std::make_pair(3, 30);
    myMap[3] = std::make_pair(4, 40);
    myMap[4] = std::make_pair(5, 50);
    return 0;
}
raz
  • 482
  • 1
  • 5
  • 17