title: std::vector is faster than std::map for a key lookup?
body: <p>I've been using std::vector mostly and was wondering if I should use std::map for a key lookup to improve performance.</p>
  
  <p>And here's my full test code.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;map&gt;
  #include &lt;vector&gt;
  #include &lt;ctime&gt;
  #include &lt;chrono&gt;
  
  using namespace std;
  
  vector&lt;string&gt; myStrings = {"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj", "kkk", "lll", "mmm", "nnn", "ooo", "ppp", "qqq", "rrr", "sss", "ttt", "uuu", "vvv", "www", "xxx", "yyy", "zzz"};
  
  struct MyData {
  
      string key;
      int value;
  };
  
  int findStringPosFromVec(const vector&lt;MyData&gt; &amp;myVec, const string &amp;str) {
  
      auto it = std::find_if(begin(myVec), end(myVec),
                             [&amp;str](const MyData&amp; data){return data.key == str;});
      if (it == end(myVec))
          return -1;
      return static_cast&lt;int&gt;(it - begin(myVec));
  }
  
  int main(int argc, const char * argv[]) {
  
      const int testInstance = 10000; //HOW MANY TIMES TO PERFORM THE TEST
  
      //----------------------------std::map-------------------------------
      clock_t map_cputime = std::clock(); //START MEASURING THE CPU TIME
  
      for (int i=0; i&lt;testInstance; ++i) {
  
          map&lt;string, int&gt; myMap;
  
          //insert unique keys
          for (int i=0; i&lt;myStrings.size(); ++i) {
  
              myMap[myStrings[i]] = i;
          }
          //iterate again, if key exists, replace value;
          for (int i=0; i&lt;myStrings.size(); ++i) {
  
              if (myMap.find(myStrings[i]) != myMap.end())
                  myMap[myStrings[i]] = i * 100;
          }
      }
      //FINISH MEASURING THE CPU TIME
      double map_cpu = (std::clock() - map_cputime) / (double)CLOCKS_PER_SEC;
      cout &lt;&lt; "Map Finished in " &lt;&lt; map_cpu &lt;&lt; " seconds [CPU Clock] " &lt;&lt; endl;
  
  
      //----------------------------std::vector-------------------------------
      clock_t vec_cputime = std::clock(); //START MEASURING THE CPU TIME
  
      for (int i=0; i&lt;testInstance; ++i) {
  
          vector&lt;MyData&gt; myVec;
  
          //insert unique keys
          for (int i=0; i&lt;myStrings.size(); ++i) {
  
              const int pos = findStringPosFromVec(myVec, myStrings[i]);
  
              if (pos == -1)
                  myVec.push_back({myStrings[i], i});
          }
          //iterate again, if key exists, replace value;
          for (int i=0; i&lt;myStrings.size(); ++i) {
  
              const int pos = findStringPosFromVec(myVec, myStrings[i]);
  
              if (pos != -1)
                  myVec[pos].value = i * 100;
          }
      }
      //FINISH MEASURING THE CPU TIME
      double vec_cpu = (std::clock() - vec_cputime) / (double)CLOCKS_PER_SEC;
      cout &lt;&lt; "Vector Finished in " &lt;&lt; vec_cpu &lt;&lt; " seconds [CPU Clock] " &lt;&lt; endl;
      return 0;
  }
  </code></pre>
  
  <p>And this is the result I got.</p>
  
  <pre><code>Map Finished in 0.38121 seconds [CPU Clock] 
  Vector Finished in 0.346863 seconds [CPU Clock] 
  Program ended with exit code: 0
  </code></pre>
  
  <p>I mostly store less than 30 elements in a container.</p>
  
  <p>Does this mean it is better to use std::vector instead of std::map in my case?</p>
  
  <p><strong>EDIT: when I move <code>map&lt;string, int&gt; myMap;</code> before the loop, std::map was faster than std::vector.</strong></p>
  
  <pre><code>Map Finished in 0.278136 seconds [CPU Clock] 
  Vector Finished in 0.328548 seconds [CPU Clock] 
  Program ended with exit code: 0
  </code></pre>
  
  <p>So If this is the proper test, I guess std::map is faster.</p>
  
  <p><strong>But, If I reduce the amount of elements to 10, std::vector was faster so I guess it really depends on the number of elements.</strong></p>