使用back_inserter（）或inserter（）提高std :: copy（）的效率 [英] Improving efficiency of std::copy() with back_inserter() or inserter()
问题描述
back_inserter 和 insert_iterator 非常方便，但效率也非常低！
例如，当你添加 char 时，每个元素都有很大的开销，当你 copy ing，在很多情况下，真的不需要。
有办法让他们更多
是的，您可以定义 std :: copy 的新版本$ c>可以劫持可优化的调用。 :)
下面是一个例子（或者hack，如果你喜欢看到玻璃半空）Visual C ++和GCC。
在我的个人计算机上（我使用VC ++ 2010），以下代码可以更快地调用 十次 br>
GCC的基准也在这里，显示了5倍的差异：旧版本反对新版本
但 it：
请注意，此代码假设容器提供了一个向量 。
如目前写的，这只适用于C ++ 11，因为它使用 type_traits 头的元编程能力仅优化复制操作将保持异常安全的情况。
如果您不需要异常安全在实际这样做之前应该考虑两次），或者如果您有另一种方法检查这样的数据类型，那么您可以更改
typename enable_if< ...，typename insert_iterator< C> > :: type
到：
insert_iterator< C>
，其余的代码也应该适用于C ++ 03。
namespace std
{
template< class FwdIt，class C&
back_insert_iterator< C> copy（
FwdIt begin，FwdIt end，back_insert_iterator< C> it，
forward_iterator_tag * =
static_cast< typename iterator_traits< FwdIt> :: iterator_category *>（0））
{
struct It：public back_insert_iterator< C>
{
使用back_insert_iterator< C> :: container;
static C& deref（C& c）{return c; }
static C& deref（C * c）{return * c; }
};
copy（begin，end，inserter（It :: deref（static_cast< It&>（it）.container），
It :: deref（static_cast< It& .container）.end（）））
return it;
}
template< class FwdIt，class C>
typename enable_if< //只有这样才会是异常安全的！
is_nothrow_copy_constructible< typename C :: value_type> :: value&&&
is_nothrow_copy_assignable< typename C :: value_type> :: value，
insert_iterator< C>
> :: type copy（
FwdIt const& begin，FwdIt const& end，
insert_iterator< C>输出，
forward_iterator_tag * = //只有前向迭代器
static_cast< typename iterator_traits< FwdIt> :: iterator_category *>（0））
{
struct It：public insert_iterator< C&
{
using insert_iterator< C> :: container; // protected - > public
using insert_iterator< C> :: iter; // protected - > public
static C& deref（C& c）{return c; }
static C& deref（C * c）{return * c; }
};
It& it（static_cast< It&>（output））;
typename C :: iterator it_iter_end（It :: deref（it.container）.end（））;
{
//将迭代器转换为偏移量
typename C :: size_type const iter_end_off =
std :: distance（It :: deref（it.container）.begin it_iter_end）;
typename iterator_traits< typename C :: iterator> :: difference_type off
= std :: distance（It :: deref（it.container）.begin（），it.iter）;
//调整容器大小
It :: deref（it.container）.resize（
It :: deref（it.container）.size（）+
static_cast< typename C :: size_type>（std :: distance（begin，end））））;
//重新规范，万一无效的话
it.iter = It :: deref（it.container）.begin（）;
std :: advance（it.iter，off）;
it_iter_end = It :: deref（it.container）.begin（）;
std :: advance（it_iter_end，iter_end_off）;
}
typename C :: iterator result
= copy_backward（it.iter，it_iter_end，It :: deref（it.container）.end（））;
copy_backward（begin，end，result）;
return insertionter（It :: deref（it.container），result）;
}
}
back_inserter and insert_iterator are very handy, but they're also very inefficient!
When you're appending chars, for example, there is a great deal of overhead for every element when you're copying, when in many situations, there really doesn't need to be.
Is there a way to make them more efficient?
Yes, you can define a new version of std::copy which can hijack optimizable calls. :)
Below is an example (or "hack", if you prefer to see the glass half-empty) for Visual C++ and GCC.
On my personal computer (I use VC++ 2010), the code below makes calls ten times faster!
A benchmark for GCC's is also here, showing a 5x difference: old version against new version
But before you use it:
Note that this code assumes the container provides a vector-like interface.
As currently written, this only works for C++11, because it uses the type_traits header's metaprogramming capabilities to only optimize those situations in which the copy operation would stay exception-safe.
If you don't need the exception safety (though you should think twice before actually doing this), or if you have another way of checking for such data types, then you can change
typename enable_if<..., typename insert_iterator<C> >::type
to:
insert_iterator<C>
and the rest of the code should work for C++03 as well.
namespace std
{
template<class FwdIt, class C>
back_insert_iterator<C> copy(
FwdIt begin, FwdIt end, back_insert_iterator<C> it,
forward_iterator_tag * =
static_cast<typename iterator_traits<FwdIt>::iterator_category *>(0))
{
struct It : public back_insert_iterator<C>
{
using back_insert_iterator<C>::container;
static C &deref(C &c) { return c; }
static C &deref(C *c) { return *c; }
};
copy(begin, end, inserter(It::deref(static_cast<It &>(it).container),
It::deref(static_cast<It &>(it).container).end()));
return it;
}
template<class FwdIt, class C>
typename enable_if< // Only do this if it would be exception-safe!
is_nothrow_copy_constructible<typename C::value_type>::value &&
is_nothrow_copy_assignable<typename C::value_type>::value,
insert_iterator<C>
>::type copy(
FwdIt const &begin, FwdIt const &end,
insert_iterator<C> output,
forward_iterator_tag * = // only forward iterators
static_cast<typename iterator_traits<FwdIt>::iterator_category *>(0))
{
struct It : public insert_iterator<C>
{
using insert_iterator<C>::container; // protected -> public
using insert_iterator<C>::iter; // protected -> public
static C &deref(C &c) { return c; }
static C &deref(C *c) { return *c; }
};
It &it(static_cast<It &>(output));
typename C::iterator it_iter_end(It::deref(it.container).end());
{
// Convert iterators to offsets
typename C::size_type const iter_end_off =
std::distance(It::deref(it.container).begin(), it_iter_end);
typename iterator_traits<typename C::iterator>::difference_type off
= std::distance(It::deref(it.container).begin(), it.iter);
// Resize container
It::deref(it.container).resize(
It::deref(it.container).size() +
static_cast<typename C::size_type>(std::distance(begin, end)));
// Renormalize, in case invalidated
it.iter = It::deref(it.container).begin();
std::advance(it.iter, off);
it_iter_end = It::deref(it.container).begin();
std::advance(it_iter_end, iter_end_off);
}
typename C::iterator result
= copy_backward(it.iter, it_iter_end, It::deref(it.container).end());
copy_backward(begin, end, result);
return inserter(It::deref(it.container), result);
}
}
这篇关于使用back_inserter（）或inserter（）提高std :: copy（）的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
