title: Choice Between std::vector and std::unordered_map For Searching In Few Items Case?
body: <p>There are a few items to iterate and search by the key. And I already form a <code>std::vector</code> for iteration. Do I need to form a <code>struct</code> for searching such as <code>std::unordered_map</code>?  </p>
  
  <p>I do know searching in <code>std::vector</code> resulted in <code>O(N)</code> and searching in <code>std::unordered_map</code> resulted in <code>O(1)</code>. But the items inside are about 10. No insert or update happened after initialization. I may search for many times. Maybe 1 millions, 1 billions, or even more, I can't make sure of it.  </p>
  
  <p>I am concerned that hashing may be costlier than iteration.  </p>
  
  <p>Here is a sample:</p>
  
  <pre><code>class Item
  {
  public:
      int key;
      const char* value;
  };
  
  class Items
  {
  public:
      Items(const std::vector&lt;const Item&gt; items) 
      : _vector(items)
      , _map(generateMap()){
      }
  
      const char* getValueByKey(int key) const {
          //which one to choose
          //map
  //        const auto&amp; iter = _map.find(key);
  //        if (iter!=_map.end()) {
  //            return iter-&gt;second;
  //        }
  //        return nullptr;
          //vector
          for (const auto&amp; iter : _vector) {
              if (iter.key==key) {
                  return iter.value;
              }
          }
          return nullptr;
      }
  
  protected:
      const std::unordered_map&lt;int, const char*&gt; generateMap() const{
          std::unordered_map&lt;int, const char*&gt; map;
          for (const auto&amp; item : _vector) {
              map.insert({item.key, item.value});//I can make sure that no same key will exists
          }
          return map;
      }
  
      const std::vector&lt;const Item&gt; _vector;
      const std::unordered_map&lt;int, const char*&gt; _map;//Is it necessary?
  };
  
  int main() 
  {   
      const std::vector&lt;const Item&gt; items ={
          {1, "value_1"},
          {20, "value_2"},
          {10, "value_3"},
          {55, "value_4"},
      }; 
      Items theItems = items;
      srand(time(nullptr));
      for (int i = 0; i &lt; 1000000; i++) {
          int key = rand();
          printf("%d %s exists\n", key, theItems.getValueByKey(key)==nullptr?"is not":"is");
      }
      return 0;
  }
  </code></pre>
  
  <p>Here is an <code>int</code> key case, maybe no hashing happened. But what about other cases, a <code>std::string</code>, a user-defined <code>struct</code> and so on?  </p>
  
  <p>So how should I make my decision for this kind of case theoretically?  </p>