C++:高效地复制容器

Question

你如何复制STL容器？

// big containers of POD
container_type<pod_type> source;
container_type<pod_type> destination

// case 1
destination = source;

// case 2
destination.assign(source.begin(), source.end());

// case 3 assumes that destination.size() >= source.size()
copy(source.begin(), source.end(), destination.size());

我尽可能使用案例1.案例2适用于不同类型的容器.当目标大于源并且您想要保留其余元素时,需要使用案例3.

但是具有非零构造/破坏成本的非POD元素呢？案例3可以胜过案例2吗？如果目标大于源,则实现可能会发生意外情况.这就是Visual Studio 2008在案例2中所做的工作.

1. 目的地的所有元素都被销毁.
2. 然后复制构造函数被调用多次作为目标的大小.为什么？
3. 源的所有元素都分配给目标的相应元素.
4. 目的地的额外元素被销毁.

GCC 4.5做得更好.源的所有元素都通过赋值复制,然后销毁目标的额外元素.使用case 3然后调整大小在两个平台上做同样的事情(除了一个调整大小需要的默认构造函数).这是玩具程序,它显示了我的意思.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

struct A {
    A() { cout << "A()\n"; }
    A(const A&) { cout << "A(const A&)\n"; }
    A& operator=(const A&) {
        cout << "operator=\n";
        return *this;
    }
    ~A() { cout << "~A()\n"; }
};

int main() {
    list<A> source(2);
    vector<A> desrination1(3);
    vector<A> desrination2(3);

    cout << "Use assign method\n";
    desrination1.assign(source.begin(), source.end());

    cout << "Use copy algorithm\n";
    copy(source.begin(), source.end(), desrination2.begin());
    desrination2.resize(2);

    cout << "The End" << endl;
    return 0;
}

Answer 1

目的地的所有元素都被销毁.然后复制构造函数被调用多次作为目标的大小.为什么？

不确定你在说什么.assign通常实现为:

 template<class Iterator>
 void assign(Iterator first, Iterator last)
 {
      erase(begin(), end()); // Calls the destructor for each item
      insert(begin(), first, last); // Will not call destructor since it should use placemenet new
 }

与副本你会做类似的事情:

assert(source.size() <= destination.size());
destination.erase(copy(source.begin(), source.end(), destination.begin()), destination.end());

这应该是几乎相同的事情.我会使用copy如果我确定源将适合目的地(由于assign/insert需要检查容器的容量,有点快)否则我将使用assign,因为它是最简单的.此外,如果您使用副本并且目标太小,则调用resize()效率很低,因为resize()将构造所有将被覆盖的元素.

GCC 4.5做得更好.源的所有元素都通过赋值复制,然后销毁目标的额外元素.使用case 3然后调整大小在两个平台上做同样的事情(除了一个调整大小需要的默认构造函数).这是玩具程序,它显示了我的意思.

这是同一件事.分配是根据复制构造实现的.

class A
{
     A& operator=(A other)
     {
         std::swap(*this, other);
         return *this;
     }

     // Same thing but a bit more clear
     A& operator=(const A& other)
     {
         A temp(other); // copy assignment
         std::swap(*this, temp);
         return *this;
     }
}