title: C++ STL Map vs Vector speed
body: <p>In the interpreter for my experimental programming language I have a symbol table. Each symbol consists of a name and a value (the value can be e.g.: of type string, int, function, etc.).</p>
  
  <p>At first I represented the table with a vector and iterated through the symbols checking if the given symbol name fitted. </p>
  
  <p>Then I though using a map, in my case <code>map&lt;string,symbol&gt;</code>, would be better than iterating through the vector all the time <strong>but</strong>: </p>
  
  <p>It's a bit hard to explain this part but I'll try.</p>
  
  <p>If a variable is retrieved the first time in a program in my language, of course its position in the symbol table has to be found (using vector now). If I would iterate through the vector every time the line gets executed (think of a loop), it would be terribly slow (as it currently is, nearly as slow as microsoft's batch).</p>
  
  <p>So I could use a map to retrieve the variable: <code>SymbolTable[ myVar.Name ]</code></p>
  
  <p>But think of the following: If the variable, still using vector, is found the first time, I can store its exact integer position in the vector with it. That means: The next time it is needed, my interpreter knows that it has been "cached" and doesn't search the symbol table for it but does something like <code>SymbolTable.at( myVar.CachedPosition )</code>.</p>
  
  <p>Now my (rather hard?) question:</p>
  
  <ul>
  <li><p>Should I use a vector for the symbol table together with caching the position of the variable in the vector?</p></li>
  <li><p>Should I rather use a map? Why? <strong>How fast is the [] operator?</strong></p></li>
  <li><p>Should I use something completely different?</p></li>
  </ul>