Получить карту с карты по вектору ключей - PullRequest
Новая
       28

Получить карту с карты по вектору ключей

2 голосов
/ 25 октября 2019

Мне было интересно, есть ли функция std :: map для получения подкарты, определенной как std :: vector ключей. Так же, как функция std::map.at(key), но с ключом std :: vector. Я знаю, что могу перебирать карту и добавлять пары карт на новую карту, но мне было интересно, есть ли встроенная функция или, возможно, более быстрый способ получить подкарту.

примерcode: 

std::map<std::string, int> map = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};
std::vector<std::string> keys = {"a", "c", "d"};
// using iteration:
std::map<std::string, int> new_map;
for(auto it = map.begin(); it != map.end(); ++it){
    if(std::find(keys.begin(), keys.end(), it->first) != keys.end()){
        new_map.insert(*it);
    }
}
// new_map should be {{"a",1}, {"c",3}, {"d",4}}

// What I am hoping to find is something like:
new_map = map.at(keys);

//resulting in the same new_map {{"a",1}, {"c",3}, {"d",4}}.

Существует ли такая функция или вообще более умный способ, чем перебирать всю карту и каждый раз использовать функцию поиска (я знаю, что могу перебирать вектор, но это не такиметь большое значение, или это?).

Ответы [ 3 ]

3 голосов
/ 25 октября 2019

Я знаю, что мог бы перебирать вектор, но это не имеет большого значения или делает это?

Это действительно имеет значение, потому что перебор по порядкуобычно быстрее для вектора, чем для карты (данные векторов локальны в памяти, а элементы карт - нет), и поиск элемента на карте быстрее, чем в векторе (O(log(N)) против O(N) для несортированного вектора).

Допустим, у вас есть M элементов на карте и N ключей в векторе, тогда ваш подход будет O( M * N), тогда как обмен итерацией и поиск будет только O( N * log(M)). Это учитывает только сложность для find. Принимая во внимание, что итерация более сложна, так как она очень сильно зависит от кеша.

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

PS вы могли бы рассматривать это как придирку к формулировкам, но так как это случается слишком часто, когда кто-то задумывается надЯ упомяну проблему: «умнее» не всегда «лучше». Не пытайтесь быть слишком умным. Большинство алгоритмов можно заменить простым циклом, но часто они считаются более выразительными и удобочитаемыми, чем рукописный цикл. Попытка втиснуть что-то в алгоритмы, когда нет алгоритма для решения проблемы, часто приводит к менее читаемому и менее выразительному коду. Если кто-то найдет алгоритм, который можно использовать здесь, я верну все в этом PS: P

2 голосов
/ 25 октября 2019

Я бы также рассмотрел использование алгоритма std::copy_if. Здесь не сохраняется слишком много символов в исходном коде, но это более явно: 

std::map<std::string, int> map = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};
std::unordered_set<std::string> keys = {"a", "c", "d"};
std::map<std::string, int> new_map;

std::copy_if(map.begin(), map.end(),
             std::inserter(new_map, new_map.end()),
             [&keys](const auto& e){ return keys.find(e.first) != keys.end(); });

Live демо здесь .

В C ++20, мы сможем написать это еще более компактно: 

std::copy_if(map.begin(), map.end(),
             std::inserter(new_map, new_map.end()),
             [&keys](const auto& e){ return keys.contains(e.first); });
1 голос
/ 25 октября 2019

Начиная с ответа ранее известного as_463035818 (итерируя по keys вместо map), мне кажется, что «путь алгоритма» (то есть: использование стандартных алгоритмов в заголовке <algorithm>) может быть использованием std::transform()

std::transform(keys.cbegin(), keys.cend(),
               std::inserter(new_map, new_map.end()),
               [&](auto const & k) -> std::pair<std::string, int>
                { return {k, map[k]}; });

но (ИМХО) гораздо удобнее читать старый добрый способ петли 

for ( auto const & k : keys )
   new_map[k] = map[k];

Не по теме Необязательное предложение: не используйте "map" (то же имякласса, игнорируя пространство имен) для переменной "std::map". Может, работает и никто не добавляет using std; ... но зачем бросать вызов судьбе?

...