Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум на Исходниках.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 |
Если у тебя не магабайтные строки, то не должно особо влиять. А так принципиально, чтобы внутри unordered_map был только std::string? Добавлено Точнее у него не компаратор, а хэш-функция. |
Автор: XandoX 13.12.16, 09:02 |
Ну некоторые системные аллокторы настолько тупые, что влияет сам факт аллоцирования, а вот размер не сильно важен. Да причем тут компаратор или хэш-функция. Меня и стандартные вполне устраивают. Вот это главный вопрос. Вообще не принципиально, но писать свой string_view, очень лень, а вот других вариантов я пока не особо вижу. |
Автор: shm 13.12.16, 11:13 |
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> struct my_string { std::string str; std::string::const_iterator begin; std::string::const_iterator end; } Их нужно переопределять для своего типа. |
Автор: 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 Спасибо. Действительно выглядит пока что единственным вариантом, но кривоватым. |