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 做得更好。通过分配复制源的所有元素，然后销毁目标的额外元素。使用案例 3 后跟 resize 在两个平台上做同样的事情(除了 resize 需要的一个默认构造函数)。这是显示我的意思的玩具程序。

#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

All elements of the destination are destroyed. Then the copy constructor is called as many times as the destination's size. Why?

不知道你在说什么。 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());

这应该是差不多的事情。如果我确定源将适合目标(更快一点，因为分配/插入需要检查容器的容量)，我会使用复制，否则我会使用分配，因为它最简单。此外，如果您使用复制并且目标太小，则调用 resize() 是低效的，因为 resize() 将构造所有将被覆盖的元素。

GCC 4.5 does it better. All elements of the source are copied via assignment and then the extra elements of the destination are destroyed. Using case 3 followed by resize does the same thing on both platforms (except one default constructor which resize needs). Here is the toy program which shows what I mean.

其实是一样的。赋值是根据复制构造来实现的。

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