Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > C/C++: Общие вопросы > поиск в unordered_map


Автор: XandoX 12.12.16, 17:28
Привет

Есть код
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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.

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

Автор: XandoX 12.12.16, 18:00
Цитата
а что, это создание подстроки так влияет на скорость?


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

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

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

Автор: shm 12.12.16, 18:09
Цитата XandoX @
1000 раз в секунду

Если у тебя не магабайтные строки, то не должно особо влиять.
Цитата XandoX @
то find принимает только std::string, в данном случаи?

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

Добавлено
Цитата shm @
Как вариант можно запилить свой компаратор в unordered_map.

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

Автор: XandoX 13.12.16, 09:02
Цитата shm @
Если у тебя не магабайтные строки, то не должно особо влиять.

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

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

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

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

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

Автор: shm 13.12.16, 11:13
Цитата XandoX @
а вот других вариантов я пока не особо вижу.

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    struct my_string
    {
       std::string str;
       std::string::const_iterator begin;
       std::string::const_iterator end;
    }

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

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

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

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

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

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #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, дергаться память не должна.

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

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)