Я бы и не задумывался, если бы не условия вполне себе прикладной задачи.

А как иначе, если на входе она и только она?

"ID" имеется ввиду тип? Да я во сне уже вижу, как я тип на входе получил и прыгаю от радости. К сожалению, только строка.

Ну как чего? Условия задачи говорят о том, что поиск будет выполняться зверски часто. 10000 сетевых запросов в секунду как минимум должно обрабатываться. И получение из фабрики объекта, ассоциированного со строкой, полученной в свою очередь по HTTP-протоколу, есть тот код, который существенно влияет на весь процесс. Другие подзадачи, которые входят в это же, критичное по времени исполнения место, я точно также буду "долбить" до потери пульса (надеюсь, что только своего). Пока же остановился на этой задаче.

Я уже имею вполне работоспособный код приложения. Сейчас занимаюсь оптимизацией. Постепенно и шаг за шагом.

Как я и сказал, я занимаюсь вполне конкретной задачей. Конкретнее некуда. Да, мне нравятся абстракции, это Вы верно подметили, и в коде своего приложения, возможно где-то перехимичил, но ничего, проект я уже раз двадцать переписывал, перепишу снова, если будет необходимость. И если алгоритм, реализацию которого я предложил, хорошо известен, то наверняка существует код, кем-то уже опубликованный. У Вас есть что-нибудь на заметке? Или натолкните на идею, которая подскажет, как можно выполнить поиск по строке быстрее, чем то, что я предложил.

Да, я видел эту тему. Вроде даже понял выдвинутую Вами там идею. Но не могу пока сообразить, как это я могу использовать у себя.

По сути, я взял идею паттерна композит, который представляет из себя дерево элементов. Просто у меня каждый элемент такого дерева - символ (char). Да, Вы описали похоже.

А чего их "мутить"? По моему вполне просто любой длины строка вписывается в такое дерево. "Двигаясь" по его веткам, можно легко восстановить строку. При этом, если символы одинаковы на одном порядковом уровне, то хранятся в контейнере они в единичном экземпляре. Но это само собой понятно.

"sizeof(letter)", где letter является элементом контейнера и содержит только char, плюс список указателей на такие же, но дочерние letter'ы. Значение же, которое является искомым, содержится лишь на самом верху в иерархии дерева. Поэтому не такой уж и большой перерасход.

Есть вариант лучше? Или Вы имеете в виду, что не стоит овчинка выделки? Тест показал, что стоит. Даже если бы я выиграл здесь 1 мс, то и тогда стоило бы. Это важно, потому что критично именно в той части задачи, о которой я сказал выше. В любом другом случае я конечно бы озадачился вопросом целесообразности столь длительных потугов на поиск наиболее оптимального решения.

Это так, но при условии, что не потребуется снова вычислять ID. А почему его потребуется вычислять? Просто потому, что от сетевого клиента придёт строка, содержащая команду, и из которой и надо будет снова вычислить этот ID. Другими словами, ID, как бы я его не использовал, время жизни его ограничено одним сетевым запросом одного из сетевых клиентов. Новый запрос - новое вычисление ID, хотя по сути, оно практически одно и то же и может иметь лишь значение в пределах известных заранее вариантов (для простоты примера пока исключим возможность отсылки заведомо ложных команд вредителей).

Ага Спасибо, теперь буду знать, что это trie (странное написание, если tree - дерево; хотя гугл даёт перевод для trie как "синтаксическое дерево").

Разница в том что Вы тратите время на цикл for

У человека не знакомого с задачей это вызывает большие сомнения. Что это за обработка если ее время соразмеримо с обращением в хеш по ключу? Не теряется ли больше времени напр на перегонку QString в char *? Или просто на создание QString? Впрочем Вам виднее

DmitryM привёл ссылку на статью, где перечисляются методы по оптимизации подобных деревьев. Они могут значительно сократить количество итераций в циклах (зависит конечно от содержимого ключей, но в моей задаче это как раз присутствует). Попытаюсь реализовать.

Высоконагруженный HTTP-сервер. Необходима поддержка большого количества запросов сетевых клиентов (10000 в секунду - программа-минимум). Поскольку условия задачи предполагают постоянное обращение к хешу по ключу (о невозможности использования ранее вычисленных указателей на элементы хеша я расписал выше), то естественно желание (если такая возможность существует, а она существует) оптимизировать данную часть кода.

Конечно, если бы это было, например, 100 - 1000 запросов, то намерения мои были бы не оправданы. Но временные потери становятся явно ощутимы при многократном увеличении одновременно поступающих сетевых запросов. Для реализации хотя бы просто поддержки такого количества сетевых соединений (не говоря уже о передачи данных) пришлось отказаться от того же QTcpServer, заменив его epoll'ом (меня, всё же, сервер интересует именно под Linux).

Только не говорите, что я снова ударился в специфику. У меня конкретная задача, и как мне обозначить её условия по другому, то есть не переходя к её специфике, я не представляю.

QString уже ликвидирован во многих частях кода. И будет убран полностью постепенно. На входе из сети я получаю char*. Именно его я называл "строкой".

Это какое-то альтернативное дереву решение? Можно подробнее?

Спасибо. Мне интересна в общем-то любая замена для кьют-классов, если она будет гарантированно быстрее, и конечно, если эта часть кода выполняется в обработчике сетевых запросов. Но так как мне сразу всё не охватить, я разбил оптимизацию на подзадачи. Но всё же к тредам, думаю, вернусь очень скоро.

С dev-решениями от Intel ещё не приходилось работать. Хотел у них для Linux профилировщик бесплатно заполучить, отправил кучу запросов с их сайта, но что-то нет ответа. Помню, когда-то это прокатило, прислали письмо со ссылкой на программу, но не сохранилась её копия. Жаль.

Ну то самое что я писал. Напр первый шаг (первый символ строки) - имея на руках все возможные строки Вы знаете диапазон, пусть 'a'..'t'. Делаете таблицу указателей на ноды, для того чтобы прыгать на нужный элемент сразу (без for), индекс получаете просто отняв 'a' (минимальный возможный) от первого символа. Если индекс < 0 или больше размера таблицы или указатель ноль - ну значит такого нет. Потом все то же для второго символа (уже используя данные нода на который перешли). На первый взгляд это ужасно - море таблиц, но на деле число вариантов невелико. 

Сделайте просто контейнер и читайте/пишите его под защитой QMutex. Или просто читайте - только зациклите защищенное чтение. Сравните время на 1 и напр 4 нитках. Этот тест займет полчаса но, во всяком случае на posix, возможно Вы будете удивлены (не скажу что "приятно удивлены")