   Is a Hashtable appropriate here?
  What I need to do is have a module that supports random access to an image sequence; the sequence is stored on disk, there is a current frame, and several thousands times per frame queries can be run to pull the image from the current frame, as well as an arbitrary number of frames ahead. The problem is, in addition to querying the frame, a difference map with the previous frame must be computed, as well as an edge detection run on the frame; this is quite a bit of computing, so this data has to be cached. We also know that we will never query any frame < current frame.Since we don't know ahead of time how many frames in advance an object might query this image sequence (needing the image, as well as the diffmap and filtered version) my idea was to use a Hashtable, keying by frame number. Every once in a while a 'garbage collection' cycle could be run where everything < current frame is discarded; but anything > current frame that has been accessed before will have the image preloaded from disk and all of the computations for the pre-processing steps available.Performance during this cache-clearing isn't really a big deal, the preprocessing step is already a 150-300ms process so it's not like adding another 100-200ms or so is going to effect performance since the lengthy part is what gets done after this data would be fetched. What is more of a worry to me is any overhead introduced by the Hash lookup; though because I'll be using ints as keys should be marginal. There could be up to 50,000 lookups per frame... (this is not a realtime process) currently, for 26,000 queries that don't use this 'seekahead' mechanism the process, minus preprocessing takes 113 seconds, and I'm hoping to get this feature working with a 'budget' of 10 seconds. (Obviously these measurements are relative to performance of the hardware, but I think the gist is obvious...)   
  I'm not sure exactly how a hash table would benefit you here; since you have a numbered sequence of frames, why not just use a flat array/vector and index directly using the frame sequence number itself?   ;Quote:Original post by ApochPiQI'm not sure exactly how a hash table would benefit you here; since you have a numbered sequence of frames, why not just use a flat array/vector and index directly using the frame sequence number itself?Say the current frame is 14, we may have lookups to 14, 17, 18 but not necessarily 15 & 16, so I could do something like this:if( Cache.ContainsKey(lookup_frame) ){    //get the cached data}else{    //Build the cache entry here}But it would make just as much sense to doif( Cache[lookup_frame] == null ){    //get the cached data}else{    Cache[lookup_frame] = new CacheEntry();    //Build the cache entry here}However, the input image stream could be 172800 frames (for a two hour movie) and I was hoping to avoid creating a big-array; but now that I think about it I'm not exactly sure why I wanted to avoid that....  since I know the maximum possible lookahead, even though it's variable I can just dynamically create the List at runtime and it would be max 50-100 frames; and every time current_frame advances just remove the index at 0.Thanks! sometimes I just need to talk things out :)   ;  Be sure to use a double-ended queue, since you'll be pushing to the back and popping from the front. I believe both operations are O(1) for std::deque, whereas erasing from a std::vector would be O(n). If you were going to use a deque and not a vector, carry on and ignore the above :)[EDIT]Oh yeah, I believe access (operator[] or deque::at) is also constant time, which will satisfy your random access requirements too.   