C++: Copy containers efficiently
How do you copy your STL containers?
// 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());
I use case 1 whenever possible. Case 2 is for containers of different types. Case 3 is needed开发者_如何学JAVA when the destination is larger than the source and you want to keep the remaining elements.
But how about non-POD elements with non-zero construction/destruction cost? Can case 3 be better than case 2? If the destination is larger than the source, the implementation can do rather unexpected things. This is what Visual Studio 2008 does in case 2.
- All elements of the destination are destroyed.
- Then the copy constructor is called as many times as the destination's size. Why?
- All elements of the source are assigned to the corresponding elements of the destination.
- The extra elements of the destination are destroyed.
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.
#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;
}
All elements of the destination are destroyed. Then the copy constructor is called as many times as the destination's size. Why?
Not sure what you are talking about. assign is usually implemented something as:
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
}
with copy you would do something like:
assert(source.size() <= destination.size());
destination.erase(copy(source.begin(), source.end(), destination.begin()), destination.end());
Which should be pretty much the same thing. I would use copy if i knew for sure that the source will fit into the destination (a bit faster since assign/insert needs to check the capacity of the container) otherwise i would use assign since it's simplest. Also if you use copy and the destination is too small, calling resize() is inefficient since resize() will construct all elements which will be overwritten eitherway.
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.
It's the same thing. Assignment is implemented in terms of copy construction.
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;
}
}
If you copy a whole container, you should rely on the container copy constructor or assignment operator. But if you copy only the container content from one to another, the best is to use std::copy
.
You can't save the copy constructor call for each instance if you use more than a POD object.
You should consider using shared/smart pointers which will only increment their reference counters on copying and use copy on write when you modify your instance.
精彩评论