我在想，在向量::插入（）和的std ::复制（）命令需要额外的分配。不过，如果我的push_back（）新创建的元素的话交换（）它，我认为这将减少任何分配只要包含的类型是不分配的默认构造函数。

I was thinking that the vector::insert() and std::copy() commands require extra allocation. However, if I push_back() a newly created element an then swap() it I think this would reduce any allocations so long as the contained type is not allocating with the default constructor.

我的问题实际上是专门为的std ::矢量 S型的std ::字符串，但应该工作对于其他类型的包含如这里所述：

My question is actually specifically for std::vectors of type std::string, but should work for other contained types as stated here:

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);
    }
}

我是正确的？我缺少什么吗？也许有这样做的更好的方法？

Am I correct? Am I missing anything else? Maybe there's some better way of doing this?

推荐答案

性能免责声明：使用分析

Performance disclaimer: Use profiling.

性能方面的考虑：

的push_back 必须检查每个调用如果向量的容量足以插入的元素。这是不可能的编译器是足够聪明，避免环路内的检查，也就是说，每一个循环迭代这将有检查，也可以禁止进一步的优化。 如果有到储备之前，的push_back 已调整向量的容量在旅途中没有呼叫，循环，这将导致移动已经存储元件内也许多次。 交换略有不同，移动：招少严格保证在移动的物体，这可能允许优化 当 GManNickG 指出，在评论中，向量::插入可保留必要存储器插入之前，因为它得到的整个范围将被插入。这可能需要随机访问迭代器的特化，因为的std ::区别对他们来说是O（1）（它可以适用于所有双向迭代器，但是这可能是慢 - 两个循环迭代 - 比的没有的保留） push_back has to check for each call if the capacity of the vector is sufficient to insert the element. It is unlikely that the compiler is smart enough to avoid that check within the loop, that is, for every loop iteration it'll have to check, which can also prohibit further optimizations. If there's no call to reserve before, push_back has to adjust the capacity of the vector on the go, maybe multiple times within the loop, which would lead to moving the already stored elements. swap is slightly different from move: move has less strict guarantees on the moved objects, which could allow optimizations As GManNickG pointed out in the comments, vector::insert could reserve the necessary memory before inserting, as it gets the whole range to be inserted. This would probably require a specialization on random access iterators because std::difference for them is in O(1) (it could be applied to all bidirectional iterators, but this could be slower - two loop iterations - than not reserving).

最有效的方法我能想到的是要保留必要的能力，然后插入元素（通过的push_back ，或通过插入）没有能力检查。

The most efficient way I can think of is to reserve the necessary capacity and then insert the elements (either via push_back or via insert) without capacity checks.

一个聪明的标准库实现可以做呼叫储备在插入，而不是检查插入过程中的能力。我不能完全肯定这将符合欧盟的标准，虽然。

A smart Standard Library implementation could do the call to reserve inside insert and not check for the capacity during insertion. I'm not entirely sure this would comply to the Standard, though.

如果你的图书馆是足够聪明，安迪警车的版本（见注释）就足够了：

If your library is smart enough, Andy Prowl's version (see comments) is sufficient:

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

否则，您可以在调用之前手动编写调用储备 插入，但你不能（据我所知）插入/元素追加W / O型的内部能力的检查：

Else, you can write the call to reserve manually before invoking insert, but you cannot (AFAIK) insert/append an element w/o internal capacity checks:

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 );
}

这可能是更好地执行追加针对不同的迭代器类型：

It might be better to implement append for different iterator types:

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() );
}

如果是因为循环中的能力检查的性能问题，你可以尝试缺省方式构造的第一所需要的其他元素。当它们的存在（即已经建成），可以使用非检查运算符[] 或简单的迭代器移动SRC对象到其目标：

If a performance problem occurs because of the capacity checks inside the loop, you could try to default-construct the required additional elements first. When they exist (i.e. have been constructed) you can use the non-checked operator[] or simple iterators to move the src objects to their destination:

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
}

便利包装：

Convenience wrapper:

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 );
}