поиск в unordered_map , Можно ли быстрее

Привет

Есть код

std::unordered_map<std::string, something_t> map;
std::string bigString;
std::string::const_iterator subKeyBegin, subKeyEnd;
std::tie(subKeyBegin, subKeyEnd) = findSubKey(bigString);
 
if (map.find(std::string(subKeyBegin, subKeyEnd)) != map.end()) // overhead
{
   doThen();
}
else
{
   doElse();
}

В общем-то вопрос в том, можно ли как-то обойтись без выделения памяти под новую std::string в стоке //overhead
Проблема в том, что unordered_map, да и просто map в find принимают только Key и нельзя туда передать что-то что на этот Key похоже и с ним умеет как-то сравниваться. А std::string, зараза, всегда аллоцирует.
Большой надежды нет, но может я еще чего-то недоглядел?

Еще как вариант можно string для ключа один раз создать, а потом его assign каждый раз, что бы туда-сюда не выделять/освобождать память, но это как-то половинчато.

Компиляторы - все, максимальный стандарт - 14.

XandoX,а что, это создание подстроки так влияет на скорость? Как вариант можно запилить свой компаратор в unordered_map.

Цитата

а что, это создание подстроки так влияет на скорость?

Ну в конкретном примере, конечно же не сильно важно, но вот если 1000 раз в секунду пытаться это сделать, то - да, да и дефрагментация памяти.

Цитата

Как вариант можно запилить свой компаратор в unordered_map.

И как обойти проблему - что find принимает только std::string, в данном случаи?

Цитата XandoX @ 12.12.16, 18:00

1000 раз в секунду

Если у тебя не магабайтные строки, то не должно особо влиять.

Цитата XandoX @ 12.12.16, 18:00

то find принимает только std::string, в данном случаи?

А так принципиально, чтобы внутри unordered_map был только std::string?

Добавлено 12.12.16, 18:11

Цитата shm @ 12.12.16, 17:55

Как вариант можно запилить свой компаратор в unordered_map.

Точнее у него не компаратор, а хэш-функция.

Сообщение отредактировано: shm - 12.12.16, 19:20

Цитата shm @ 12.12.16, 18:09

Если у тебя не магабайтные строки, то не должно особо влиять.

Ну некоторые системные аллокторы настолько тупые, что влияет сам факт аллоцирования, а вот размер не сильно важен.

Цитата shm @ 12.12.16, 18:09

Точнее у него не компаратор, а хэш-функция.

Да причем тут компаратор или хэш-функция. Меня и стандартные вполне устраивают.

Цитата shm @ 12.12.16, 18:09

А так принципиально, чтобы внутри unordered_map был только std::string?

Вот это главный вопрос. Вообще не принципиально, но писать свой string_view, очень лень, а вот других вариантов я пока не особо вижу.

Цитата XandoX @ 13.12.16, 09:02

а вот других вариантов я пока не особо вижу.

struct my_string
{
   std::string str;
   std::string::const_iterator begin;
   std::string::const_iterator end;
}

Цитата XandoX @ 13.12.16, 09:02

Да причем тут компаратор или хэш-функция.

Их нужно переопределять для своего типа.

Сообщение отредактировано: shm - 13.12.16, 11:14

Цитата XandoX @ 12.12.16, 17:28

В общем-то вопрос в том, можно ли как-то обойтись без выделения памяти под новую std::string в стоке //overhead

1) Заранее создать временную строку, и reserve ее в "максимальный размер из всех больших строк". Если максимальный размер не может быть заранее рассчитан выделить побольше, пусть 64к, и на каждой итерации сравнивать, и если надо перевыделять больше. Но лучче рассчитать всеж заранее.
2) Во временную строку делать assign

Ну вот как-то так, но я итерации по "большим строкам" не делал:

#include <iostream>
#include <vector>
#include <unordered_map>
 
typedef std::pair<std::string::const_iterator,std::string::const_iterator> FindType;
 
FindType findSubKey(std::string &S) {
  auto a = S.find_first_of('a');  
  auto b = S.find_last_of('f');
  std::cout << a << ":" << b <<std::endl;  
  return {S.begin()+a,S.begin()+b};    
}
 
int main () {
    std::unordered_map<std::string, int> map = {
      {"123",3},
      {"123456abcdefx",2},
      {"abcde",7},  
      {"6abcdef",1}
    };
    std::string bigString = "123abcdefjhk";
    std::string::const_iterator subKeyBegin, subKeyEnd;
    std::tie(subKeyBegin, subKeyEnd) = findSubKey(bigString);
    //////////////////////////////////////////////////////////////////
    std::string Tmp = "";
    Tmp.reserve(bigString.size());
    //////////////////////////////////////////////////////////////////
    Tmp.assign(subKeyBegin,subKeyEnd);
    std::cout << "\"" << Tmp << "\"" << std::endl;
    std::cout << (map.find(Tmp)!=map.end() ? "Нашли":"Не нашли") << std::endl;
  return 0;
}

По идее будет только копирование в Tmp, дергаться память не должна.

JoeUser Спасибо. Действительно выглядит пока что единственным вариантом, но кривоватым.