title: C++ std::map creation taking too long?
body: <p>UPDATED:</p>
  
  <p>I am working on a program whose performance is very critical. I have a vector of structs that are NOT sorted. I need to perform many search operations in this vector. So I decided to cache the vector data into a map like this:</p>
  
  <pre><code>        std::map&lt;long, int&gt; myMap;
  
          for (int i = 0; i &lt; myVector.size(); ++i)
          {
              const Type&amp; theType = myVector[i];
              myMap[theType.key] = i;
          }
  </code></pre>
  
  <p>When I search the map, the results of the rest of the program are much faster. However, the remaining bottleneck is the creation of the map itself (it is taking about 0.8 milliseconds on average to insert about 1,500 elements in it). I need to figure out a way to trim this time down. I am simply inserting a long as the key and an int as the value. I don't understand why it is taking this long.</p>
  
  <p>Another idea I had was to create a copy of the vector (can't touch the original one) and somehow perform a faster sort than the std::sort (it takes way too long to sort it).</p>
  
  <p>Edit: </p>
  
  <p>Sorry everyone. I meant to say that I am creating a std::map where the key is a long and the value is an int. The long value is the struct's key value and the int is the index of the corresponding element in the vector.</p>
  
  <p>Also, I did some more debugging and realized that the vector is not sorted at all. It's completely random. So doing something like a stable_sort isn't going to work out.</p>
  
  <p>ANOTHER UPDATE:</p>
  
  <p>Thanks everyone for the responses. I ended up creating a vector of pairs (std::vector of std::pair(long, int)). Then I sorted the vector by the long value. I created a custom comparator that only looked at the first part of the pair. Then I used lower_bound to search for the pair. Here's how I did it all:</p>
  
  <pre><code>  typedef std::pair&lt;long,int&gt; Key2VectorIndexPairT;
    typedef std::vector&lt;Key2VectorIndexPairT&gt; Key2VectorIndexPairVectorT;
  
    bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT&amp; pair1, const Key2VectorIndexPairT&amp; pair2)
    {
        return pair1.first &lt; pair2.first;
    }
  
    ...
  
    Key2VectorIndexPairVectorT sortedVector;
    sortedVector.reserve(originalVector.capacity());
  
    // Assume "original" vector contains unsorted elements.
    for (int i = 0; i &lt; originalVector.size(); ++i)
    {
        const TheStruct&amp; theStruct = originalVector[i];
        sortedVector.insert(Key2VectorIndexPairT(theStruct.key, i));
    }
  
    std::sort(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairComparator);
  
    ...
  
    const long keyToSearchFor = 20;
  
    const Key2VectorIndexPairVectorT::const_iterator cItorKey2VectorIndexPairVector = std::lower_bound(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairT(keyToSearchFor, 0 /* Provide dummy index value for search */), Key2VectorIndexPairComparator);
  
    if (cItorKey2VectorIndexPairVector-&gt;first == keyToSearchFor)
    {
        const int vectorIndex = cItorKey2VectorIndexPairVector-&gt;second;
        const TheStruct&amp; theStruct = originalVector[vectorIndex];
  
        // Now do whatever you want...
    }
    else
    {
        // Could not find element...
    }
  </code></pre>
  
  <p>This yielded a modest performance gain for me. Before the total time for my calculations were 3.75 milliseconds and now it is down to 2.5 milliseconds.</p>