Fastest way to convert from vector of pairs to two

问题:

lets say I have a vector of pair<int,int>. Now I want to extract the pair.first and pair.second as independent vectors. I can iterate on the vector and do that but is there a better/faster way?

回答1:

In C++11, if you don't need the old vector anymore, you could perhaps get a tiny bit of extra efficiency from move semantics:

for (auto it = std::make_move_iterator(v.begin()),
         end = std::make_move_iterator(v.end()); it != end; ++it)
{
    v1.push_back(std::move(it->first));
    v2.push_back(std::move(it->second));
}

Other than that, you certainly cannot do better than one loop. You will have to touch every element at least once, so this is as efficient as it gets.

Note that moving can only make a difference if the element types themselves have move semantics that are better than copying. This is not the case for ints, or any PODs. But it can't hurt to write your code generically so that you can take advantage of this in future situations.

If copying/moving is a problem, though, you should consider whether some view adapter for your original vector might be a better approach.

回答2:

No there is not. The one thing to take care of is to use reserve on the two resulting vectors to prevent unnecessary reallocations.

回答3:

You won't be able to avoid the iteration. As to the fastest solution, it depends on what is in the pair, and on the actual implementation. Depending on these, it may be better to create the target vectors with the correct size, and assign to them; or to create them empty, and use reserve and then push_back. You might also want to compare indexing with using iterators; if you're using pre-sized vectors, using only one control variable instead of three might be an improvement. (With g++, the last time I measured, creating vectors of the correct size and assigning was faster than using reserve and push_back, at least for double. Despite the fact that it meant looping twice internally, and initializing the values to 0.0.)

You might also want to try creating functional objects to extract the first and second elements of the pair (supposing you don't have them already), and use two calls to transform. Again, either with a predimensionned vector or using a back inserter as target. Off hand, I wouldn't expect this to provide better performance, but you never know.

回答4:

You have to iterate over the vector anyway, so in terms of Complexity, this is as good as you can get.