这是在C ++ 11中将一个std :: vector的内容移动到另一个的末尾的最有效方法吗？ [英] Is this the most efficient way of move the contents of one std::vector to the end of another in C++11?

问题描述

我在想 vector :: insert（）和 std :: copy（）命令需要额外的命令分配。但是，如果我 push_back（）一个新创建的元素然后一个 swap（），我认为这会减少任何分配只要所包含的类型未使用默认构造函数分配。

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 :: vector std :: string 的c>，但应适用于此处所述的其他包含类型：

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 必须检查每个通话如果向量的容量足以插入元素。编译器不可能足够聪明地避免在循环内进行检查，也就是说，对于每次循环迭代都必须进行检查，这也可能阻止进一步的优化。


• 如果之前没有调用 reserve 的情况， push_back 不得不随时随地调整向量的容量，也许在其中多次循环，将导致移动已存储的元素。


• 交换与 move ：move对移动的对象没有那么严格的保证，这可能允许优化


• 作为 GManNickG 在评论中指出， vector :: insert 可以在插入之前保留必要的内存，因为它可以插入整个范围。这可能需要对随机访问迭代器进行专门化处理，因为 std :: difference 对于它们在O（1）中（可以应用于所有双向迭代器，但这可能是慢-两次循环迭代-比 not 保留）。

• 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 或通过 insert ）而不进行容量检查。

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.

一个智能的标准库实现可以调用 insert reserve c>并且在插入过程中不检查容量。不过，我不完全确定这会符合标准。

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.

如果您的图书馆足够聪明，那么 Andy Prowl 的版本（请参阅评论）就足够了：

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

否则，您可以将呼叫写到储备在调用插入之前手动进行，但是您不能（AFAIK）插入/附加没有内部容量检查的元素：

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

---

如果出现性能问题由于循环中进行了容量检查，因此您可以尝试首先默认构造所需的其他元素。当它们存在（即已构造）时，可以使用未经检查的 operator [] 或简单的迭代器将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 );
}

这篇关于这是在C ++ 11中将一个std :: vector的内容移动到另一个的末尾的最有效方法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！