title: Why is vector faster than unordered_map?
body: <p>I am solving a problem on LeetCode, but nobody has yet been able to explain my issue.</p>
  <h2>The problem is as such:</h2>
  <p>Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.</p>
  <p>Each letter in the magazine string can only be used once in your ransom note.</p>
  <p>Note:
  You may assume that both strings contain only lowercase letters.</p>
  <pre><code>canConstruct(&quot;a&quot;, &quot;b&quot;) -&gt; false
  canConstruct(&quot;aa&quot;, &quot;ab&quot;) -&gt; false
  canConstruct(&quot;aa&quot;, &quot;aab&quot;) -&gt; true
  </code></pre>
  <h3>My code (which takes 32ms):</h3>
  <pre><code>class Solution {
  public:
      bool canConstruct(string ransomNote, string magazine) {
          if(ransomNote.size() &gt; magazine.size()) return false;
          unordered_map&lt;char, int&gt; m;
          
          for(int i = 0; i &lt; magazine.size(); i++)
              m[magazine[i]]++;
              
          for(int i = 0; i &lt; ransomNote.size(); i++)
          {
              if(m[ransomNote[i]] &lt;= 0) return false;
              m[ransomNote[i]]--;
          }
          return true;
      }
  };
  </code></pre>
  <h3>The code (which I dont know why is faster - takes 19ms):</h3>
  <pre><code>bool canConstruct(string ransomNote, string magazine) {
          int lettersLeft = ransomNote.size(); // Remaining # of letters to be found in magazine
          int arr[26] = {0};
          for (int j = 0; j &lt; ransomNote.size(); j++) {
              arr[ransomNote[j] - 'a']++; // letter - 'a' gives a value of 0 - 25 for each lower case letter a-z
          }
          
          int i = 0;
          while (i &lt; magazine.size() &amp;&amp; lettersLeft &gt; 0) {
              if (arr[magazine[i] - 'a'] &gt; 0) {
                  arr[magazine[i] - 'a']--;
                  lettersLeft--;
              }
              i++;
          }
          if (lettersLeft == 0) {
              return true;
          } else {
              return false;
          }
      }
  </code></pre>
  <p>Both of these have the same complexity and use the same structure to solve the problem, but I don't understand why one takes almost twice as much time than the other. The time to query a vector is O(1), but its the same for an unordered_map. Same story with adding an entry/key to either of them.</p>
  <p>Please, could someone explain why the run time varies so much?</p>