如何将map中符合条件的元素复制到vector中？

Question

我希望能够从一个 map<string,int> 中复制满足谓词（相等的整数）的值到一个vector<int> 中。

这是我的尝试：

#include <map>
#include <vector>
#include <algorithm>

int main()
{
    std::vector< int > v;
    std::map< std::string, int > m;

    m[ "1" ] = 1;
    m[ "2" ] = 2;
    m[ "3" ] = 3;
    m[ "4" ] = 4;
    m[ "5" ] = 5;

    std::copy_if( m.begin(), m.end(), v.begin(),
                  [] ( const std::pair< std::string,int > &it )
                  {
                    return ( 0 == ( it.second % 2 ) );
                  }
                  );
}

g++ 4.6.1的错误消息是：

error: cannot convert 'std::pair<const std::basic_string<char>, int>' to 'int' in assignment

有没有一种方法可以调整示例以执行上述复制操作？

- BЈовић

---

这是一个非常好的问题，我很惊讶为什么没有更多人问到它。 - John Dibling

Answer 1

使用boost::range非常简单：

boost::push_back(
    v,
    m | boost::adaptors::map_values 
      | boost::adaptors::filtered([](int val){ return 0 == (val % 2); }));

- Mankarse

---

boost::range 需要更多的关注。简单的管道概念在编程中太好用了，不容错过。 - Matthieu M.

boost::copy + std::back_inserter 很丑陋。如果您使用 boost.range，那么 boost::push_back(v, m | map_values | filtered([](int val){ return 0 == (val % 2); })); 在我看来更清晰、更短。 - Arzar

这似乎也是最优解（就速度而言）。 - BЈовић

@ThomasPetit：是的，我忘记了那个！已修复。 - Mankarse

只是一个小问题：应该是boost::mpl::push_back，对吧？ - BЈовић

找到了。所以，你正在使用这个：http://www.boost.org/doc/libs/1_47_0/libs/range/doc/html/range/reference/algorithms/new/push_back.html - BЈовић

Answer 2

问题

复制失败是因为你正在从一个遍历pair<string const,int>的 map::iterator到一个遍历int的vector::iterator。

解决方案

使用for_each替换copy_if并对您的向量执行push_back操作。

示例

std::for_each( m.begin(), m.end(),
    [&v] ( std::pair< std::string const,int > const&it ) {
        if ( 0 == ( it.second % 2 ) ) {
            v.push_back(it.second);
        }
    }
);

- Kleist

---

使用transform而不是手动编写循环并一个一个地将每个元素推入。这就是它的作用。 - John Dibling

@JohnDibling：使用transform如何进行偶数过滤？据我所知，它是一对一的，因此输入和输出中始终获得相同数量的元素。 - Kleist

@Kleist：使用transform_if。请看我的回答。 - John Dibling

你需要修改lambda捕获子句为[&v]，以便在封闭作用域中访问向量。 - Blastfurnace

“复制失败是因为你正在从一个遍历pair<string,int>的map::iterator进行复制。” 不，它正在遍历pair<string const, int> - 关联容器的键类型始终是const。 - ildjarn

Answer 3

编译器错误实际上非常简洁：

error: cannot convert 'std::pair<const std::basic_string<char>, int>' to 'int' in assignment

这正是问题所在。你复制的map有迭代器，可以解引用成一个pair<KEY,VALUE>，但无法隐式地将pair<KEY,VALUE>转换成只有VALUE。

因此，你不能使用copy或copy_if将map复制到vector中；但标准库提供了一种算法，叫做transform。 transform与copy非常相似，都需要两个源迭代器和一个目标迭代器。不同之处在于，transform还需要一个一元函数来实际进行转换。使用C++11 lambda表达式，你可以像这样将整个map的内容复制到vector中：

transform( m.begin(), m.end(), back_inserter(v), [] (const MyMap::value_type& vt)
{
  return vt.second;
});

如果您不想复制整个map的内容，而只想复制满足某些条件的元素怎么办？简单呀，只需使用transform_if。

你说什么？标准库中没有transform_if？好吧，你说得没错。令人沮丧的是，标准库中没有transform_if。但是，编写一个非常简单。下面是代码：

template<class InputIterator, class OutputIterator, class UnaryFunction, class Predicate>
OutputIterator transform_if(InputIterator first, 
                            InputIterator last, 
                            OutputIterator result, 
                            UnaryFunction f, 
                            Predicate pred)
{
    for (; first != last; ++first)
    {
        if( pred(*first) )
            *result++ = f(*first);
    }
    return result; 
}

正如你所预期的那样，使用 transform_if 就像将 copy_if 和 transform 结合在一起。以下是一些伪代码来演示：

transform_if( m.begin(), m.end(), back_inserter(v),
  [] (const MyMap::value_type& vt) // The UnaryFunction takes a pair<K,V> and returns a V
  {
    return vt.second;
  }, [] (const MyMap::value_type& vt) // The predicate returns true if this item should be copied
  {
     return 0 == (vt.second%2);
  } );

- John Dibling

---

它更短。从映射元素到映射值的转换通过命名库调用进行，过滤是在该转换的结果上完成的（而不是重复转换）。整个代码由简单的正交元素组成，而不是使用一次性执行多个操作的单块transform_if函数。它避免了为单个输入范围指定多个迭代器的需要。 - Mankarse

这就是我们非常需要“视图”的地方。如果我们有一个“filter_view”，那么连接过滤和转换操作就会变得非常简单。 - Matthieu M.

Answer 4

我不明白为什么这个问题中，简单的for循环解决方案不是首选方法。

for (std::map< std::string, int >::iterator it = m.begin(); it != m.end(); ++it )
{
   if ((it->second % 2) == 0)
      v.push_back(it->second);
}

除了使代码更易读之外，它还能提高性能。我编写了一个简单的基准测试来比较for循环与其他提出的解决方案的性能：

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <sstream>

int main(int argc, char *argv[])
{
    std::map< std::string, int > m;
    std::vector<int> v;

    // Fill the map with random values...
    srand ( time(NULL) );

    for (unsigned i=0; i<10000; ++i)
    {
      int r = rand();
      std::stringstream out;
      out << r;
      std::string s = out.str();

      m[s] = r;
    } 

    /////////// FOR EACH ////////////////////

    clock_t start1 = clock();
    for (unsigned k=0; k<10000; k++)
    {
      v.clear();
      std::for_each( m.begin(), m.end(),
      [&v] ( const std::pair< std::string,int > &it ) {
      if ( 0 == ( it.second % 2 ) ) {
          v.push_back(it.second);
      }
      }
      );
    }
    clock_t end1=clock();
    std::cout << "Execution Time for_each : " << (end1-start1) << std::endl;

    /////////// TRANSFORM ////////////////////

    clock_t start2 = clock();
    for (unsigned k=0; k<10000; k++)
    {
      v.clear();
      std::transform(m.begin(), m.end(), std::back_inserter(v),
            [] ( const std::pair< std::string,int > &it )
            {
              return it.second;
            });
      v.erase(
    std::remove_if(
        v.begin(), v.end(), [](const int value){ return (value % 2) != 0; }),
    v.end());
    }
    clock_t end2 = clock();
    std::cout << "Execution Time transform : " << (end2-start2) << std::endl;


     /////////// SIMPLE FOR LOOP ////////////////////
    clock_t start3 = clock();
    for (unsigned k=0; k<10000; k++)
    {
      v.clear();
      for (std::map< std::string, int >::iterator it = m.begin(); it != m.end(); ++it )
      {
    if ((it->second % 2) == 0)
      v.push_back(it->second);
      }
    }
    clock_t end3=clock();
    std::cout << "Execution Time Simple For Loop : " << (end3-start3) << std::endl;

}

我得到的结果如下：

Execution Time for_each : 7330000
Execution Time transform : 11090000
Execution Time Simple For Loop : 6530000

- pnezis

---

这并不执行过滤操作(( 0 == ( it.second % 2 ) )). - larsmoa

你没有启用优化。你的数字在默认设置下是正确的，但一旦启用优化，这些数字就会相当可比。如果你正在使用g++，请使用“-O3”。启用优化后，我得到了使用transform的最快版本。 - BЈовић

使用优化后，我仍然得到更好的结果： for_each循环：3890000 transform函数：4000000 普通for循环：2940000 - pnezis

Answer 5

std::copy_if不能让你将一种类型转换为另一种类型，只能过滤要复制的内容。

您可以使用std::transform来去除键，然后使用std::remove_if：

  std::vector<int> v;
  std::transform(m.begin(), m.end(), std::back_inserter(v),
                  [] ( const std::pair< std::string,int > &it )
                  {
                    return it.second;
                  });
  v.erase(
      std::remove_if(
          v.begin(), v.end(), [](const int value){ return (value % 2) != 0; }),
      v.end());

然而，使用普通的for循环将更加高效且易于阅读。

- larsmoa

---

更好了，但是transform_if会更好。请看我的回答。 - John Dibling

Answer 6

你可能只想从map中检索相关的值，而不是键。

STL的SGI版本有select1st和select2nd迭代器来处理这种任务。

然而，个人认为这不应该使用复制来完成--你正在转换数据，而不是复制它。因此，我建议使用一个函数对象来返回对中的第二个项目，使用std::transform。

- Jerry Coffin