10

In C++, if I have two vectors of int:

A = [1, 2, 3 ,4]; 
B = [1, 2, 3, 4];

How can I merge them into one vector of pairs:

[(1,1), (2,2), (3,3), (4, 4)]

Of course I can do that with a loop. But can we do that using suitable STL functions and iterators?

justin
  • 104,054
  • 14
  • 179
  • 226
David Ren
  • 117
  • 2
  • 7

2 Answers2

20

You can use an algorithm for this:

std::vector<std::pair<int, int>> target;
target.reserve(A.size());
std::transform(A.begin(), A.end(), B.begin(), std::back_inserter(target),
               [](int a, int b) { return std::make_pair(a, b); });
Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 2
    Note it doesn't actually help get rid of a loop. The loop will just be hidden in `std::transform()`. Also an explicit loop would be shorter and clearer in this particular case. – Karadur Aug 28 '13 at 02:53
  • 16
    @Karadur: You cannot apply an operation to N elements without somehow iterating over the elements, that is just plain obvious: zipping two sequences cannot be done in O(1). The question is also quite clear as to what is desired: *can we do that using suitable STL functions and iterators?*. This answer does exactly that. – David Rodríguez - dribeas Aug 28 '13 at 03:38
  • 1
    You could even leave out the lambda and use `make_pair` directly, no? – jrok Aug 28 '13 at 06:35
  • @jrok: I don't think so as `make_pair` would not be a valid functor, `make_pair` on the other hand may actually work… This won't work either as the implementation of `make_pair` is based on "universal references" which become rvalue references if you take out type deduction… – MFH Aug 28 '13 at 07:33
  • @MFH Yes, I didn't mean without template parameters. Something like `make_pair` ought to work, altough it's a bit strange to look at. – jrok Aug 28 '13 at 07:43
  • @jrok: that does work indeed (thanks to reference collapsing). Personally I'd prefer the lambda version… – MFH Aug 28 '13 at 08:20
  • @jrok: Using a lambda makes the operation easy to inline while using a function pointer, i.e., `std::make_pair()` directly, does not. – Dietmar Kühl Aug 28 '13 at 09:19
  • @Karadur: Although it probably isn't, `std::transform()` could be implemented recursively or using suitable magic. However, yes, any solution will use a loop or an equivalent construct. – Dietmar Kühl Aug 28 '13 at 09:21
7

I agree that Dietmar Kühl's answer does exactly what was asked in the question, but I also agree with Kakadur's comment. A loop is hidden in std::transform() so the complexity is the same. Some people will judge, but if there is no direct proof of one way being better than the other, I tend to choose the most readable and least verbose version:

// create a vector of length of the smaller vector
std::vector<std::pair<int, int>> target( A.size() < B.size() ? A.size() : B.size() );

for (unsigned i = 0; i < target.size(); i++)
    target[i] = std::make_pair(A[i], B[i]);

P.S. The code above allocates just enough space for the target vector, so that the potential overhead of push_back (in case of reallocation) can be avoided.

Oleksiy
  • 37,477
  • 22
  • 74
  • 122
  • you know, there's a potential loop hidden in `push_back` as well – David Brown Aug 28 '13 at 04:38
  • Well, yes, but If a reallocation happens. Thanks for the hint, I will update my answer – Oleksiy Aug 28 '13 at 04:49
  • *"However, for most people this version is a lot more readable and clear"* - Yeah, to those not acquainted with the standard library (and thus C++). And it doesn't really answer the question at all, does it? – Christian Rau Aug 28 '13 at 10:39
  • @ChristianRau Your assumption does not make sense. I am acquainted with the standard library and C++, yet I find this code a lot more readable and clear. At least 3 other people upvoted, so I'm not alone. This code does answer the question (I am using "suitable STL functions" - `std::make_pair` for example.) I just refuse to use the STL code unless it has an reduced complexity and better readability. I will not use STL blindly, especially if it looks more verbose and ugly. Simplicity is the key here, my friend :) – Oleksiy Aug 28 '13 at 11:21
  • Well, at least you removed the assertion that *"most people"* would find it more readable and clear. But unfortunately it doesn't change anything in the unansweredness of the post. Answers are not there to disqualify the initial question as ill-posed, that's what comments are for. You may very well find his approach inappropriate and provide good reason for that, but this doesn't change anything in the validity and answerability of his question. Certainly *he* wants to use a standard library algorithm instead of a loop, no matter if *you* want it, too. – Christian Rau Sep 17 '13 at 11:28