查找 std::vector 中也存在于 std::map 中的元素

Question

我想得到 std::vector 中每个元素 的 迭代器，它也存在于 std::map 中（如 .first或者作为 key).

我怎样才能最有效地解决这个问题？

Answer 1

我会做如下事情，这将有一个 O( N log(n) )，其中 N = 向量的大小，n = 地图的大小。 这不需要双循环。

   std::vector<int> vec{1,2,3,4,5,6,7,8};
   std::map<int, int> myMp{{1,2}, {2,2}, {5,2}, {6,2} };

   std::vector<std::vector<int>::iterator> v_itr;  // iterators

   for(auto itr = vec.begin(); itr != vec.end(); ++itr)
   {
      auto mp_find = myMp.find(*itr);   // log(n) where n = myMp.size()
      if(mp_find != myMp.cend())  v_itr.emplace_back(itr);
   }