Как найти все элементы, соответствующие вектору ключей?

Question

У меня есть std::vector<std::string> k; с ключами значений ведьмы, к которой я стремился. У меня есть std::map<std::string, void*> table; Я ищу. Я хочу получить значения std::vector<void*> v; для всех ключей, которые находятся в k (если такие значения существуют в table, не все ключи могут быть представлены в table, и этот факт для меня не важен, в то время как важно то, что может быть гораздо больше ключей, чем в k). Как найти все значения, соответствующие ключам?

Использование table[k_element] из table.find(k_element) для каждого элемента в k кажется очень плохой способ сделать это и я не мог find any algorithm in STL, которые могли бы сделать это в групповом порядке ... (

Answer 1

с помощью таблицы [k_element] или table.find (k_element) для каждого элемента к кажется очень плохо

Я не уверен, почему это чувствует себя плохо. Даже если были aglorithm в STL, чтобы сделать это для вам придется либо перебирать каждое значение в k - это не решение этой проблемы, которая быстрее, чем линейное время. Я думаю, иногда люди думают, что одна строка кода всегда быстрее цикла, даже если одна строка кода вызывает функцию, содержащую цикл.

Есть способы сделать это в линии с lambdas, картой и т. Д., Но это не «лучше» или быстрее, а менее читаемо.

Answer 2

Есть Differents решение вашей проблемы, некоторые из них:

• Поместите все ключи в k в unordered_set, итерацию по таблице и поиску для каждого ключа в наборе, вы получите O(n). Вы можете рассмотреть возможность изменения таблицы для структуры данных, в которой хранятся элементы в непрерывной памяти (возможно, карта с использованием распределителя пулов или структуры данных с std::vector за занавесками), таким образом алгоритм будет более дружественным к кэшу (таким образом, вероятно, значительный быстрее), хотя время ввода в эту структуру данных будет медленным.
• Идите по k и найдите каждую клавишу в таблице, вы получите O(k*log(n)), если вы измените таблицу на unordered_map, вы можете получить O(k). Хотя, вы должны учесть, что вычисление хэша строки может быть очень медленным, иногда лучше сравнивать строки и иметь время журнала для поиска, чем вычислять хэш ключа и иметь постоянное время для поиска. Выбор зависит от расширения и характера ключей.
• Вы можете отсортировать элементы в k и перебрать упорядоченный набор, после каждого поиска вы узнаете отправную точку для следующего поиска, таким образом, каждый поиск будет быстрее предыдущего. Поскольку std::map не позволяет вам указать начальную точку поиска, вы можете реализовать свое собственное дерево двоичного поиска с этой функциональностью.

И многое другое, лучшее решение зависит от размера ваших наборов данных, характера ваших ключей и других факторов. Изучите проблему, выберите одно или два решения, внесите их, протестируйте и, при необходимости, выполните итерацию.