title: STL structures: "insert if not present" operation?
body: <p>I'm working on a program right now dealing with some exponential time algorithms. Because of this, a main loop of my program is being run many times, and I'm trying to optimize it as much as possible.</p>
  
  <p>Profiling shows that a large portion of the time is spent in look-up and hash calculation for <code>std::unordered_map</code>.</p>
  
  <p>I'm wondering:</p>
  
  <ol>
  <li><p>Is there a way to cache the hash value of a key for <code>std::unordered_map</code>, and then provide it as an argument to insert later on?</p></li>
  <li><p>Is there a way that I can do the following in a single operation: given an key and value <code>{x,y}</code>, check if key <code>x</code> is in the map, if it isn't, insert it and return <code>{x,y}</code>, otherwise return <code>{x,z}</code> for whatever <code>z</code> is already in the map.</p></li>
  </ol>
  
  <p>I'm doing something like this right now, but it's inefficient, because I have to calculate the hash for the key and check if it's in the map. But if it isn't in the map, I do a completely separate insert operation. In theory, checking if it is present in the map should find where it would go in the map if inserted.</p>
  
  <p>I'm open to trying other data structures, like <code>std::map</code> or something from Boost, if they would reduce the time for this operation.</p>