Самый быстрый способ найти ключи карты в векторе - PullRequest
Новая
       8

Самый быстрый способ найти ключи карты в векторе

0 голосов
/ 21 мая 2018

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

Ниже стандартного кода: 

    std::unordered_map<uint32, user> map;
    std::vector<uint32> to_find; 
    std::vector<user> results;

    auto it = map.begin();

    while (it != map.end())
    {
        if (std::find(to_find.begin(), to_find.end(), it->first) == to_find.end())
            results.push_back(it->second);
        it++;
    }

Ответы [ 2 ]

0 голосов
/ 23 мая 2018

Если оба ваших контейнера отсортированы, линейный способ - использовать алгоритм, аналогичный std::merge: 

template <typename KEY, typename VALUE>
std::vector<VALUE>
collect_absents(const std::map<KEY, VALUE>& map, const std::vector<KEY>& present)
{
    std::vector<VALUE> res;

    auto mit = map.begin();
    auto vit = present.begin();

    while (mit != map.end() && vit != present.end())
    {
        if (*vit < mit->first) {
            ++vit;   
        } else if (mit->first < *vit) {
            res.push_back(mit->second);
            ++mit;   
        } else { // equal
            ++vit;
            ++mit;
        }
    }
    for (; mit != map.end(); ++mit) {
        res.push_back(mit->second);
    }
    return res;
}

Демо

0 голосов
/ 21 мая 2018

Вы можете использовать std :: binary_search () , который имеет временную сложность O (log n) , где n - размер вектора to_find.Это может быть намного лучше, чем использовать std::find(), который имеет линейную сложность по времени.

DEMO 

#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>

using user = int;
using uint32 = unsigned long int;

int main()
{
    std::unordered_map<uint32, user> myMap = {{1,2},{3,5},{2,9},{4,7}};
    std::vector<uint32> to_find = {1,3};
    std::vector<user> results;

    if(to_find.size() == 0)  // if you have to_find vec size = 0
        std::for_each(myMap.cbegin(), myMap.cend(), [&results](const auto& ele)->void
                                                    {
                                                        results.emplace_back(ele.second);
                                                    });
    else
    {
        for(const auto& it: myMap)// binary_search; if not found add the value
            if(!std::binary_search(to_find.begin(), to_find.end(), it.first))
                results.emplace_back(it.second);
    }

    for(const auto& it: results) std::cout << it << std::endl;
}
...