STL复制功能的效率

Question

我正在尝试从条目列表构造一组唯一的单词,每个条目都有一个字符串向量.

所以我创建了一个名为Insert的函数,它会为每个条目调用,如下所示:

for( auto & e : _Entries )
    _Dictionary.Insert( begin( e.getNameWords( ) ), end( e.getNameWords( ) ) );

类_Dictionary内部有一个set(STL容器),我编写了函数Insert,如下所示:

template< typename InputIterator >
void Insert( InputIterator first, InputIterator last )
{
    for( auto it = first ; it != last ; ++it )
        _AllWords.insert( *it );
 }

在我的例子中,为_Entries中的所有条目调用Insert平均花费570毫秒.

然后我认为我应该使用STL已经具有的函数来执行与Insert中的for循环相同的操作,因此我将函数Insert更改为以下内容:

template< typename InputIterator >
void Insert( InputIterator first, InputIterator last )
{
    copy( first, last, inserter( _AllWords, begin( _AllWords ) ) );

}

我期待着这一点

1. 更正确,并且
2. 至少同样快,如果不是更快

(以让STL为您尽可能多的理念为指导).但是,我惊讶地发现这种实施实际上需要更长时间; 没有多少,但比以前的基于for循环的实现多200毫秒.

我知道这是一个基本上微不足道的速度差异,但我仍然感到惊讶.

所以我的问题是:为什么我的实施更快？

注意:我正在使用clang的3.5.2版本和libc ++标准库以及-O3标志在Ubuntu 14.04下进行编译.

Answer 1

问题是这样的:

copy( first, last, inserter( _AllWords, begin( _AllWords ) ) );

最终调用此版本insert:

iterator insert( iterator hint, const value_type& value );

与begin()作为提示.也就是说,通常情况下,不是您想要插入每个值的位置.其结果是,你要做的仅仅是容器做更多的工作,试图找出在哪里添加你的价值观,因为你hint是尽可能坏.

但请注意,还存在以下重载insert:

template< class InputIt >
void insert( InputIt first, InputIt last );

你应该使用^†:

template< typename InputIterator >
void Insert( InputIterator first, InputIterator last )
{
    _AllWords.insert(first, last);
}

并注意,_AllWords是一个保留的标识符.

^†虽然基于这个说明:

重载(5-6)通常实现为一个循环,用end()提示调用重载(3); 它们被优化用于附加排序的序列(例如另一个集合),其最小元素大于最后一个元素*this

这似乎是一个非常具体的目标来优化,你可能会或可能不会满足,所以可能你不应该使用这个重载,你的初始循环就好了.