How to concatenate/merge vectors

Question

I'm trying to figure out a way to merge 2 vectors and an integer into one vector. ie

return data.push_back(fn(data1), mid, fn(data2));

NB This is a recursive function. The vector data has values stored in it before it reaches the return statement. I need the values in data to be updated with the values in the return statement.

I have absolutely no idea how to go about doing this. I've been searching for a couple of hours, but nothing seems to work!

Any guidance is very much appreciated.

Have you considered first pushing back all the items (using a loop) from fn(data1), then mid, then all the items from fn(data2)? — Cameron, Oct 09 '12 at 18:30
What do you mean by "updated" - change some existing values or just add all values from `data1`, `data2` and `mid` into `data`? — Kiril Kirov, Oct 09 '12 at 18:30
@Cameron - it's even better to use `insert`, instead of a loop with `push_back` - it's more effective, less code, better style. — Kiril Kirov, Oct 09 '12 at 18:31
@Cameron - I thought about push back, but fn(data1) is not just 1 value. It is a call to the same function. Eventually it will just return 1 single value. — CocaCola, Oct 09 '12 at 18:32
@Sandra - "eventually?" You mean, it may throw or what? And can it return more than one element? — Kiril Kirov, Oct 09 '12 at 18:33
@KirilKirov - I mean that I want to basically discard the old values in the data vector, and instead store the values which will come from the following recursive function calls. — CocaCola, Oct 09 '12 at 18:34
@KirilKirov - What I mean is, it will get to a base case and the recursive calls will stop. Similar to a recursive fibonacci function. At this point, it will only return 1 element. Prior to reaching this base case, there will be multiple elements in both data1 and data2 vectors. — CocaCola, Oct 09 '12 at 18:37
@Sandra - could you post the source of `fn`? Or it's too long? — Kiril Kirov, Oct 09 '12 at 19:04

Jon Purdy · Accepted Answer · 2015-02-11T11:00:50.477

11

std::vector::insert() accepts an iterator range:

std::vector<int> left(fn(data1));
std::vector<int> right(fn(data2));
data.insert(data.end(), left.begin(), left.end());
data.push_back(mid);
data.insert(data.end(), right.begin(), right.end());
return data;

You can also use std::copy() from <algorithm> and std::back_inserter() from <iterator>:

std::copy(left.begin(), left.end(), std::back_inserter(data));
data.push_back(mid);
std::copy(right.begin(), right.end(), std::back_inserter(data));

However, insert() can know the size of its input range in advance and reserve() the appropriate amount of memory, while back_insert_iterator is opaque—it just repeatedly calls push_back(). They both run in linear time, but insert() will probably make fewer allocations.

If the elements of your vectors are more efficient to move than to copy, you can use the C++11 std::make_move_iterator() from <iterator> to adapt the input ranges:

data.insert(data.end(),
    std::make_move_iterator(left.begin()),
    std::make_move_iterator(left.end()));
data.push_back(mid);
data.insert(data.end(),
    std::make_move_iterator(right.begin()),
    std::make_move_iterator(right.end()));

Though I doubt this would make a difference for int.

edited Feb 11 '15 at 11:00

answered Oct 09 '12 at 18:32

Jon Purdy

53,300
8
96
166

1

In C++11, consider a `std::move_iterator` on top of this – Mooing Duck Oct 09 '12 at 18:37
Second `data.insert(data.end(), left.begin(), left.end());` in first code block should be `data.insert(data.end(), right.begin(), right.end());` – Can Bal Feb 11 '15 at 02:45
@CanBal: Wow. It only took over two years for someone to notice. It was wrong in the third block as well. Fixed! – Jon Purdy Feb 11 '15 at 11:02
Thanks for the answer. Would the move iterator corrupt the original data? What are the disadvantages of using the `make_move_iterator`? – AturSams Oct 15 '15 at 10:47
@zehelvion: Not “corrupt”, but it would leave the elements of the input vectors in [moved-from](http://stackoverflow.com/a/7028318/246886) state. A possible disadvantage is that the input vectors cannot be `const` if you want to move from them. – Jon Purdy Oct 15 '15 at 18:55
@JonPurdy Thanks! So in other words, corrupt is wrong, possibly mutated (modified) but valid is correct. – AturSams Oct 16 '15 at 03:40

score 1 · Answer 2 · answered Oct 09 '12 at 18:33

Use std::back_inserter along with std::copy. For example:

void foo(vector<int> lhs, vector<int>& rhs)
{
  vector<int> result;
  copy( lhs.begin(), lhs.end(), back_inserter(result));
  copy( rhs.begin(), rhs.end(), back_inserter(result));
  result push_back(42);
  return result;
}

score 0 · Answer 3 · answered Oct 09 '12 at 18:32

0

You want to use the insert member function that takes 3 iterator arguments.

answered Oct 09 '12 at 18:32

paquetp

1,639
11
19

How to concatenate/merge vectors

3 Answers3