C ++ std :: map создание занимает слишком много времени?

Question

ОБНОВЛЕНО:

Я работаю над программой, производительность которой очень важна.У меня есть вектор структур, которые НЕ отсортированы.Мне нужно выполнить много поисковых операций в этом векторе.Поэтому я решил кешировать векторные данные в карту следующим образом:

        std::map<long, int> myMap;

        for (int i = 0; i < myVector.size(); ++i)
        {
            const Type& theType = myVector[i];
            myMap[theType.key] = i;
        }

Когда я ищу карту, результаты остальной части программы намного быстрее.Однако остальным узким местом является создание самой карты (для вставки в нее около 1500 элементов в среднем требуется около 0,8 миллисекунды).Мне нужно найти способ сократить это время.Я просто вставляю long как ключ и int как значение.Я не понимаю, почему это занимает так много времени.

Еще одна идея, которая у меня была, - создать копию вектора (не может коснуться оригинала) и каким-то образом выполнить более быструю сортировку, чем std ::сортировать (сортировка занимает слишком много времени).

Редактировать:

Извините всех.Я хотел сказать, что я создаю std :: map, где ключ long, а значение int.Длинное значение - это ключевое значение структуры, а int - это индекс соответствующего элемента в векторе.

Кроме того, я сделал еще одну отладку и понял, что вектор вообще не отсортирован.Это совершенно случайно.Так что делать что-то вроде stable_sort не получится.

ДРУГОЕ ОБНОВЛЕНИЕ:

Спасибо всем за ответы.В итоге я создал вектор пар (std :: vector из std :: pair (long, int)).Затем я отсортировал вектор по длинному значению.Я создал собственный компаратор, который смотрел только на первую часть пары.Затем я использовал lower_bound для поиска пары.Вот как я все это сделал:

  typedef std::pair<long,int> Key2VectorIndexPairT;
  typedef std::vector<Key2VectorIndexPairT> Key2VectorIndexPairVectorT;

  bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT& pair1, const Key2VectorIndexPairT& pair2)
  {
      return pair1.first < pair2.first;
  }

  ...

  Key2VectorIndexPairVectorT sortedVector;
  sortedVector.reserve(originalVector.capacity());

  // Assume "original" vector contains unsorted elements.
  for (int i = 0; i < originalVector.size(); ++i)
  {
      const TheStruct& 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->first == keyToSearchFor)
  {
      const int vectorIndex = cItorKey2VectorIndexPairVector->second;
      const TheStruct& theStruct = originalVector[vectorIndex];

      // Now do whatever you want...
  }
  else
  {
      // Could not find element...
  }

Это принесло мне скромный прирост производительности.Раньше общее время моих вычислений составляло 3,75 миллисекунды, а теперь оно сократилось до 2,5 миллисекунд.

Answer 1

Я не эксперт по C ++, но, похоже, ваша проблема связана с копированием экземпляров Type вместо ссылки / указателя на экземпляры Type.

std::map<Type> myMap; // <-- this is wrong, since std::map requires two template parameters, not one

Если вы добавляете элементы на карту, а они не являются указателями, то я считаю, что вызывается конструктор копирования, и это, безусловно, приведет к задержкам с большой структурой данных. Вместо этого используйте указатель:

std::map<KeyType, ObjectType*> myMap;

Кроме того, ваш пример немного сбивает с толку, поскольку вы «вставляете» значение типа int в карту, когда ожидаете значение типа Type. Я думаю, что вы должны назначить ссылку на элемент, а не на индекс.

myMap[theType.key] = &myVector[i];

Обновление:

Чем больше я смотрю на ваш пример, тем больше смущаюсь. Если вы используете std :: map, тогда он должен принимать два типа шаблона:

map<T1,T2> aMap;

Так что вы ДЕЙСТВИТЕЛЬНО наносите на карту? map<Type, int> или что-то еще?

Похоже, что вы используете Type.key поле члена в качестве ключа к карте (это правильная идея), но если ключ того же типа, что и Type, то вы не можете использовать его как ключ к карте. Так что key является экземпляром Type ??

Кроме того, вы отображаете текущий векторный индекс на ключ на карте, что указывает на то, что вы просто хотите, чтобы индекс был вектором, чтобы впоследствии вы могли быстро получить доступ к этому местоположению индекса. Это то, что вы хотите сделать?

Обновление 2.0:

После прочтения вашего ответа кажется, что вы используете std::map<long,int>, и в этом случае копирование структуры не выполняется. Кроме того, вам не нужно делать локальную ссылку на объект в векторе. Если вам просто нужен доступ к ключу, то получите к нему доступ, позвонив по номеру myVector[i].key.