小编典典

这是在C ++ 11中将一个std :: vector的内容移动到另一个的末尾的最有效方法吗?

algorithm

我当时以为vector::insert()and
std::copy()命令需要额外的分配。但是,如果我push_back()是一个新创建的元素,那么swap()我认为这将减少任何分配,只要所包含的类型未使用默认构造函数分配即可。

我的问题实际上是专门针对std::vectorstd::string,但应该适用于此处所述的其他包含的类型:

template <typename T>
void appendMove(std::vector<T>& dst, std::vector<T>& src)
{
    dst.reserve(dst.size() + src.size())
    for(std::vector<T>::iterator it = src.begin(); it != src.end(); ++it)
    {
        dst.push_back(std::vector<T>());
        std::swap(dst.end()[-1], *it);
    }
}

我对么?我还有其他东西吗?也许有更好的方法可以做到这一点?


阅读 593

收藏
2020-07-28

共1个答案

小编典典

性能免责声明:使用性能分析。

性能注意事项:

  • push_back必须为每个调用检查向量的容量是否足以插入元素。编译器不可能足够聪明地避免在循环内进行检查,也就是说,对于每次循环迭代都必须进行检查,这也可能阻止进一步的优化。
  • 如果reserve之前没有调用,push_back则必须在循环中调整向量的容量,可能在循环内多次调整,这将导致移动已存储的元素。
  • swap与以下内容略有不同move:move对移动的对象没有严格的保证,这可能允许优化
  • 正如GManNickG在评论中指出的那样,vector::insert可以在插入之前保留必要的内存,因为它可以插入整个范围。这可能需要对随机访问迭代器进行专门化处理,因为std::difference它们在O(1)中(它可以应用于所有双向迭代器,但是这样做可能更慢-两个循环迭代-比 保留)。

我能想到的最有效的方法是保留必要的容量,然后在不进行容量检查的情况下(通过push_back或通过insert)插入元素。

一个智能的标准库实现可以对reserve内部进行调用,insert而无需在插入过程中检查容量。不过,我不太确定这是否符合标准。

如果您的图书馆足够聪明,那么Andy Prowl的版本(请参阅注释)就足够了:

dst.insert( dst.end(),
            std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end())    );

否则,您可以在调用reserve之前手动将调用写入insert,但是您不能(AFAIK)在不进行内部容量检查的情况下插入/附加元素:

template < typename T, typename FwdIt >
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst)
{
    dst.reserve( dst.size() + std::distance(src_begin, src_end) );
    // capacity checks might slow the loop inside `insert` down
    dst.insert(dst.end(), src_begin, src_end);
}

例:

int main()
{
    std::vector<int> dst = { 0, 1, 2 };
    std::vector<int> src = { 3, 42 };

    append( std::make_move_iterator(src.begin()),
            std::make_move_iterator(src.end()),
            dst );
}

最好append为不同的迭代器类型实现:

template < typename T, typename FwdIt >
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst,
            std::forward_iterator_tag)
{
    // let the vector handle resizing
    dst.insert(dst.end(), src_begin, src_end);
}

template < typename T, typename RAIt >
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst,
            std::random_access_iterator_tag)
{
    dst.reserve( dst.size() + (src_end - src_begin) );
    dst.insert(dst.end(), src_begin, src_end);
}

template < typename T, typename FwdIt >
void append(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst)
{
    append( src_begin, src_end, dst,
            typename std::iterator_traits<FwdIt>::iterator_category() );
}

如果由于循环内的容量检查而导致性能问题,则可以尝试首先默认构造所需的其他元素。当它们存在(即已构造)时,您可以使用非选中operator[]或简单的迭代器将src对象移动到其目的地:

template < typename T, typename RAIt >
void append(RAIt src_begin, RAIt src_end, std::vector<T>& dst,
            std::random_access_iterator_tag)
{
    auto src_size = src_end - src_begin;

    dst.resize( dst.size() + src_size );

    // copy is not required to invoke capacity checks
    std::copy( src_begin, src_end, dst.end() - src_size );
    // ^this^ should move with the example provided above
}

便利包装:

template < typename T, typename FwdIt >
void append_move(FwdIt src_begin, FwdIt src_end, std::vector<T>& dst)
{
    append( std::make_move_iterator(src_begin),
            std::make_move_iterator(src_end),
            dst );
}
2020-07-28