title: Searching fast through a sorted list of strings in C++
body: <p>I have a list of about a hundreds unique strings in C++, I need to check if a value exists in this list, but preferrably lightning fast.</p>
  
  <p>I am currenly using a hash_set with std::strings (since I could not get it to work with const char*) like so:</p>
  
  <pre><code>stdext::hash_set&lt;const std::string&gt; _items;
  _items.insert("LONG_NAME_A_WITH_SOMETHING");
  _items.insert("LONG_NAME_A_WITH_SOMETHING_ELSE");
  _items.insert("SHORTER_NAME");
  _items.insert("SHORTER_NAME_SPECIAL");
  
  stdext::hash_set&lt;const std::string&gt;::const_iterator it = _items.find( "SHORTER_NAME" ) );
  
  if( it != _items.end() ) {
     std::cout &lt;&lt; "item exists" &lt;&lt; std::endl;
  }
  </code></pre>
  
  <p>Does anybody else have a good idea for a faster search method without building a complete hashtable myself?</p>
  
  <hr>
  
  <p>The list is a fixed list of strings which will not change. It contains a list of names of elements which are affected by a certain bug and should be repaired on-the-fly when opened with a newer version.</p>
  
  <p>I've built hashtables before using Aho-Corasick but I'm not really willing to add too much complexity.</p>
  
  <hr>
  
  <p>I was amazed by the number of answers. I ended up testing a few methods for their performance and ended up using a combination of kirkus and Rob K.'s answers. I had tried a binary search before but I guess I had a small bug implementing it (how hard can it be...).</p>
  
  <p>The results where shocking... I thought I had a fast implementation using a hash_set... well, ends out I did not. Here's some statistics (and the eventual code):</p>
  
  <blockquote>
    <p><strong>Random lookup of 5 existing keys and 1 non-existant key, 50.000 times</strong></p>
    
    <p>My original algorithm took on average <strong>18,62</strong> seconds<br>
    A lineair search took on average <strong>2,49</strong> seconds<br>
    A binary search took on average <strong>0,92</strong> seconds.<br>
    A search using a perfect hashtable generated by gperf took on average <strong>0,51</strong> seconds.</p>
  </blockquote>
  
  <p>Here's the code I use now:</p>
  
  <pre><code>bool searchWithBinaryLookup(const std::string&amp; strKey) {
     static const char arrItems[][NUM_ITEMS] = { /* list of items */ };
  
     /* Binary lookup */
     int low, mid, high;
  
     low = 0;
     high = NUM_ITEMS;
     while( low &lt; high ) {
        mid = (low + high) / 2;
        if(arrAffectedSymbols[mid] &gt; strKey) {
           high = mid;
        }
        else if(arrAffectedSymbols[mid] &lt; strKey) {
           low = mid + 1;
        }
        else {
           return true;
        }
     }
  
     return false;
  }
  </code></pre>
  
  <p><em>NOTE: This is Microsoft VC++ so I'm not using the std::hash_set from SGI.</em></p>
  
  <hr>
  
  <p>I did some tests this morning using gperf as <a href="https://stackoverflow.com/users/10958/vardhandotnet">VardhanDotNet</a> suggested and this is quite a bit faster indeed.</p>