Трудно найти быстрое решение без каких-либо знаний о реальной проблеме.В частности, насколько велик ваш набор данных, где хранятся реальные данные (хранятся ли они в контейнере или где-то еще?).Какие еще операции вам нужно выполнить над контейнером?Вам нужно удалить элементы из контейнера?
В качестве комментария к одному из других вопросов вы заявляете, что ключи должны быть скопированы в std::unordered_map ... если ключи уже хранятся где-то еще,Я бы посоветовал вам использовать карту, но избегайте копирования строк.Используйте указатели в качестве ключей и пользовательский компаратор для разыменования и работы в результате:
// Assuming that the data is stored in std::string somewhere else
struct custom_compare {
bool operator()( std::string* lhs, std::string* rhs ) const {
return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare( *rhs ) < 0);
}
};
std::map< std::string*, data, custom_compare > mymap;
Хранение указателей вместо фактических строк избавит от копирования.Пользовательский компаратор в основном такой же быстрый, как и тот, который вы внедрили в список, и дерево будет уравновешивать содержимое, что позволяет выполнять O (log n) поисков.В зависимости от размера набора (если имеется много элементов), тогда это будет улучшение по сравнению с линейным поиском, в то время как при небольшом размере будет лучше линейный поиск.
Кроме того, в зависимости от разнообразияданные, вы можете следовать линейному поиску, но разделить пространство поиска в зависимости от некоторых критериев, которые можно быстро рассчитать и в то же время разделить набор как можно более равномерно.Например, вы можете использовать линейный поиск, но вместо одного списка сохраняйте разные списки в зависимости от длины ключа.
Если критерий фактически основан на содержимом строки (буквы, а не размер)тогда вы приближаетесь к определению дерева.Если вы получаете библиотеку, которая уже реализует ее, или вы готовы потратить время, необходимое для этого, trie, вероятно, будет одним из самых быстрых контейнеров для этого типа поиска, поскольку он преобразует переменную «size» из числаэлементы в длину строки.