首页 > 代码库 > transform算法

transform算法



transform()的第一版本以仿函数op作用于[first,last)中的每一个元素身上,并以其结果产生出一个新序列。第二版本以仿函数binary_op作用于一双元素身上(其中一个元素来自[first1,last1),另一个元素来自“从first2开始的序列”),并以其结果产生出一个新序列。如果第二序列的元素少于第一序列,执行结果未可预期。
//版本一
template <class InputIterator,class OutputIterator,class UnaryOperation>
OutputIterator transform(InputIterator first,InputIterator last,

OutputIterator result,UnaryOperation op)
{
 for (;first != last;++first,++result)
  *result = op(*first);
 return result;
}
//版本二
template <class InputIterator1,class InputIterator2,class OutputIterator,
class BinaryOperation>
OutputIterator transform(InputIterator1 first1,InputIterator1 last1,
InputIterator2 first2,OutputIterator result,BinaryOperation binary_op)
{
 for (;first1 != last1;++first1,++first2,++result)
  *result = binary_op(*first1,*first2);
 return result;
}


transform通过赋值操作将结果写到写到目标区间中。所以下面的代码将有一个错误:
int transmogrify(int x);
vector<int> values;
...
vector<int> results;
transform(values.begin(),values.end(),results.end(),transmogrify);


在*results.end()中并没有对象,这种transform调用时错误的,因为它导致了对无效对象的赋值操作。如果希望将结果添加到results容器的末尾,我们可以通过调用back_inserter生成一个迭代器来指定目标区间的起始位置:
vector<int> results;
transform(values.begin(),values.end(),back_inserter(results),transmogrify);


在内部,back_inserter返回的迭代器将使得push_back被调用,所以back_inserter可适用于所有提供了push_back方法的容器(vector,list,string,deque)。
如果需要在容器的头部而不是尾部插入对象,则可以使用front_inserter。front_inserter在内部使用了push_front,所以front_inserter仅适用于那些提供了push_front成员函数的容器(如deque和list)。
...
list<int> results;
transform(values.begin(),values.end(),front_inserter(results),transmogrify);


由于front_inserter将通过push_front来加入每个对象,所以这些对象在results中的顺序将与在values中的顺序相反。这正是为什么front_inserter不如back_inserter常用的原因之一。另一个原因是,vector并没有提供push_front方法,所以无法针对vector使用front_inserter。下面是一种解决方法:
list<int> results;
transform(values.rbegin(),values.rend(),front_inserter(results),transmogrify);


如果插入操作的目标容器时vector和string,则可以预先调用reserve,从而提高插入操作的性能,避免因重新分配容器内存而带来的开销。
假设希望transform覆盖results容器中已有的元素,那么就需要确保results中已有的元素至少和values中的元素一样多。否则,就必须使用resize来保证这一点:
vector<int> values;
vector<int> results;
...
if(results.size()<values.size())
{
 results.resize(values.size());
}
transform(values.begin(),values.end(),results.begin(),transmogrify);