title: How to change the key in an unordered_map?
body: <p>I need to use a data structure which supports constant time lookups on average. I think that using a <code>std::unordered_map</code> is a good way to do it. My data is a "collection" of numbers.</p>
  
  <pre><code>|115|190|380|265|
  </code></pre>
  
  <p>These numbers do not have to be in a particular order. I need to have about <code>O(1)</code> time to determine whether or not a given number exists in this data structure. I have the idea of using a <code>std::unordered_map</code>, which is actually a hash table (am I correct?). So the numbers will be keys, and then I would just have dummy values.</p>
  
  <p>So basically I first need to determine if the key matching a given number exists in the data structure, and I run some algorithm based on that condition. And independently of that condition I also want to update a particular key. Let's say <code>190</code>, and I want to add <code>20</code> to it, so now the key would be <code>210</code>.
  And now the data structure would look like this:</p>
  
  <pre><code>|115|210|380|265|
  </code></pre>
  
  <p>The reason I want to do this is because I have a recursive algorithm which traverses a binary search tree. Each node has an <code>int value</code>, and two pointers to the left and right nodes. When a leaf node is reached, I need to create a new field in the "hash table" data structure holding the <code>current_node-&gt;value</code>. Then when I go back up the tree in the recursion, I need to successively add each of the node's value to the previous sum stored in the key. And the reason why my data structure (which I suggest should be a <code>std::unordered_map</code>) has multiple fields of numbers is because each one of them represents a unique path going from a leaf node up the tree to a certain node in the middle. I check if the sum of all the values of the nodes on the path from the leaf going up to a given node is equal to the value of that node. So basically into each key is added the current value of the node, storing the sum of all the nodes on that path. I need to scan that data structure to determine if any one of the fields or keys is equal to the value of the current node. Also I want to insert new values into the data structure in near constant time. This is for competitive programming, and I would hesitate to use a <code>std::vector</code> because looking up an element and inserting an element takes linear time, I think. That would screw up my time complexity. Maybe I should use another data structure other than a <code>std::unordered_map</code>?</p>