Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697736 Wed, 14 Dec 2016 09:07:37 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697736 JoeUser Спасибо. Действительно выглядит пока что единственным вариантом, но кривоватым.]]> XandoX C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697612 Tue, 13 Dec 2016 15:40:12 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697612 Цитата 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 C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697568 Tue, 13 Dec 2016 11:13:59 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697568 Цитата 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 C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697549 Tue, 13 Dec 2016 09:02:06 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697549 Цитата 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 C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697472 Mon, 12 Dec 2016 18:09:08 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697472 Цитата 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 C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697471 Mon, 12 Dec 2016 18:00:04 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697471 Цитата

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

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

Цитата

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

И как обойти проблему - что find принимает только std::string, в данном случаи?]]> XandoX C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697470 Mon, 12 Dec 2016 17:55:27 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697470 XandoX,а что, это создание подстроки так влияет на скорость? Как вариант можно запилить свой компаратор в unordered_map.]]> shm C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697466 Mon, 12 Dec 2016 17:28:49 +0000 поиск в unordered_map https://forum.sources.ru/index.php?showtopic=410042&view=findpost&p=3697466
Есть код

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 C/C++: Общие вопросы