在std::unordered_map中查找对应同一值的所有键

Question

我有一个unordered_map，看起来像这样：

std::unordered_map<int, std::string> theMap2 = {{1,"a"}, {2,"b"}, {3,"c"}, {4,"a"}};

我想找出所有值相同的键，比如说"a"。除了明显的方法，你有什么建议吗？

std::vector<int> arrKeys;
std::string value = "a";
for (const auto& element : theMap)
   if (element.second == value)
        arrKeys.push_back(element.first); 

- Dimitar Mirchev

---

答案中的copy_if去哪了？ 你所要做的就是将lambda更改为通过&捕获值，并将auto参数更改为const auto&。 - KABoissonneault

@KABoissonneault 不，你还需要适应输出迭代器，因为 copy_if 将尝试复制键-值 对。 - dyp

@dyp 它能够轻松地进行适应吗？如果可以，您能否发布一个答案？ - KABoissonneault

@KABoissonneault 编写适配器比编写 transform_if 算法更难；最好都通过现有库来完成（例如 boost 可以方便地编写新的迭代器）。但是，您可能可以找到一个直接解决 OP 问题的库。 - dyp

从许多角度来看，你自己的解决方案是最好的。 - Tomilov Anatoliy

Answer 1

我认为“显而易见”的方法非常出色：它简单、短小且易于阅读。

另一个选择是使用 STL 算法。你需要的是 transform_if 算法，这样你就可以这样说:

std::transform_if(std::begin(theMap), std::end(theMap),  std::back_inserter(arrKeys), check_value, get_value);

但是在STL中没有这个功能。我可以建议的是：

std::vector<int> arrKeys;
std::string value = "a";

auto check_value = [&](std::pair<const int, std::string> const& p)->bool
{
    return (p.second == value);
};

auto end = std::end(theMap);
auto it = find_if(std::begin(theMap), end, check_value);
while (it != end)
{
    arrKeys.push_back(it->first);
    it = find_if(std::next(it), end, check_value);
}

- aahzbg

---

我认为你建议使用copy_if创建仅包含所需值的新映射，然后使用transform填充arrKeys。你有什么想法？ - aahzbg

抱歉，我被谓词分心了，没有注意将键值对转换为值的问题。虽然可以通过迭代器适配器仍然使用copy_if，但可能更合理的是使用transform_if。 - dyp

@dyp 你需要像 back_first_inserter 一样编写类似于 copy_if 的函数吗？ - Barry

@Barry 是的，需要某种适配器，无论是用于映射迭代器还是输出迭代器。range v3 包含 view::values，但我没有使用过该库，因此很难想出一个合适（惯用）的解决方案。 - dyp

@dyp @Barry 我尝试编写一个 back_first_inserter，希望能得到任何反馈。 - TartanLlama

std::unordered_map 的值类型是 std::pair<const Key, T>，但如果没有 const 限定符，它将构造一个临时的 std::pair<Key, T> 传递给您的函数，该函数需要一个 const &，这可能不是您想要或预期的。 - sjdowling

Answer 2

仅出于兴趣，我编写了一个基本的包装器，可用于copy_if。它类似于std::back_inserter，但它不仅仅插入给定的对象，而是插入std::get<N>(obj)。这使其可用于std::array、std::tuple和std::pair。

要插入pair.first，就像我们在这个例子中想要的那样，我们使用back_n_inserter<0>。

template< std::size_t N, class Container >
class back_n_insert_iterator : public std::iterator< std::output_iterator_tag,
                                                         void, void, void, void >
{
public:
    back_n_insert_iterator (Container& c) : c{c} {};

    //could protect this by checking that the get call is_convertible to the value_type
    template <typename T>
    decltype(auto) operator= (T&& collec) 
    {
        c.push_back(std::get<N>(std::forward<T>(collec)));
        return *this;
    }

    decltype(auto) operator* () { return *this; }
    decltype(auto) operator++ () { return *this; }
    decltype(auto) operator++ (int) { return *this; }
private:
    Container& c;
};

template< std::size_t N, class Container >
back_n_insert_iterator<N,Container> back_n_inserter( Container& c )
{
    return {c};
}

现在我们可以在copy_if调用中使用我们的适配器：

std::copy_if(theMap.begin(), theMap.end(), 
             back_n_inserter<0>(arrKeys),
             [&value](const auto& el){return el.second == value;});

感谢 @dyp 提供的所有建议。

- TartanLlama

---

如果您通过模式匹配取消函数参数的限制，则可以将back_first_inserter改进为back_n_inserter。 template <typename T> void operator =（T && t）{c.push_back（std :: get <N>（std :: forward <T>（t）））;}（可能受到SFINAE保护）。顺便说一句，我仍然不相信这比编写transform_if更好。使用Niebler的range v3，应该可以编写类似于std::vector<int> arrKeys = theMap | view :: remove_if（[&]（auto const＆ p）{return p.second！= value; }）| view :: keys;的代码（未经测试） - dyp