title: C++ - how to buffer calc results faster than using unordered_map
body: <p>I read a lot about unordered_map not being very fast but I wonder what's the best alternative to do this:</p>
  <p>I need to buffer calculation results for a function of an integer argument. I don't know ahead of time what range or interval will be requested. Storing in a vector with maximal resolution would cost way too much memory.
  So I'm using
  <code>unordered_map&lt;unsigned long, pair&lt;T, long&gt;&gt;</code>
  Where the key is the argument of the function to be computed, the first of the pair the result of the computation of type T, and the second of the pair a version information for that computation.
  Only if the unordered_map does <em>not</em> contain the element <em>or</em> it contains it but the version is outdated, the computation is carried out and then added to the unordered_map. The lookup function looks something like this:</p>
  <pre><code>template&lt;typename T&gt; class BufferClass{
    long MyVersion;
    unordered_map&lt;unsigned long, pair&lt;T,long&gt;&gt; Buffer;
  public:
    BufferClass(): MyVersion{1} {};
  
    T* GetIfValid(unsigned long index)
    {
      if (!Buffer.count(index)) return nullptr;
      pair &lt;T,long&gt; &amp;x{Buffer.at(index)};
      if (x.second!=MyVersion) return nullptr;
      return &amp;x.first;
    }
  /* ...Functions to set elements...*/
  }
  </code></pre>
  <p>As you can see, I combined element validity check and retrieval in one function, so that I only need one lookup for both.</p>
  <p>The profiler shows most of the computation time is used up in the hash function __constrain_hash related to unordered_map.</p>
  <p>What would be the fastest way to store and retrieve values like that? The list of stored indices is expected to be non-continuous (there will be a lot of &quot;holes&quot;) and first and last index are also mostly unknown.</p>
  <p>T will generally be a &quot;small&quot; data type (like double or complex).</p>
  <p>Thanks!</p>
  <p>Martin</p>