Структура данных для сортировки / поиска строк

Question

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

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

. Я мог бы эффективно извлекать элементы из очереди приоритетов, но это означает, что мне понадобится вспомогательное пространство перед тем, как отправить их обратно в очередь приоритетов

Было бы идеально, если бы вектор допускал функцию сравнения.Будет ли работать STL?У меня есть фиксированное количество элементов (около 450).

Редактировать: Подтверждение того, что набор STL работает .. даже без определения моей собственной функции сравнения для строк.

Answer 1

Я не совсем уверен, что вам нужно.Я предполагаю, что под «мне нужно перебирать строки» вы имеете в виду, что вам нужно перебирать оставшиеся (не «всплывающие») строки в несортированном порядке и, кроме того, обращаться к ним, используя очередь с приоритетами (через «pop»),Если вам нужно перебрать отсортированную последовательность, вы должны отсортировать входные строки заранее (например, через std::set) и не использовать приоритетную очередь (приоритетные очереди не обязательно сразу сортируют все элементы, это сортируетпоследовательность «по требованию»).

std::priority_queue использует базовый контейнер (по умолчанию std::vector).Унаследовав этот класс, вы можете получить доступ к контейнеру.Переменная защищенного члена определена в стандарте , и это теоретически должно быть безопасно (хотя и не спорим, что это в реальной жизни).Однако наследование контейнеров STL хмурится на .

Альтернативой является создание собственной очереди приоритетов, например, на основе std::vector и std :: make_heap , std :: pop_heap и std :: push_heap .std::priority_queue использует эти функции внутри.

Answer 2

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

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