How to std::merge two std::vector in-place?

Question

Following code attempts to std::merge v2 into v1.

std::vector<int> v1{1,2,3,0,0,0}; std::vector<int> v2{1,2,3}; std::merge(v1.begin(), v1.begin() + 3, v2.begin(), v2.end(), v1.begin()); for (auto i : v1) { std::cout << i << " "; }

The expected output is: 1 1 2 2 3 3

The actual output by this code is : 1 1 1 1 2 3

A potential fix for this problem, is to create a temporary vector.

std::vector<int> v1{1,2,3,0,0,0}; std::vector<int> v2{1,2,3}; std::vector<int> tmp(v1.size()); std::merge(v1.begin(), v1.begin() + 3, v2.begin(), v2.end(), tmp.begin()); for (auto i : tmp) { std::cout << i << " "; }

I want to avoid this memory overhead and do it in-place in vector v1. Any idea how I can do that with std::merge?

I would say you can no merge inplace in linear time, it would always need many array shift operations. — gerum
– gerum, Commented Mar 6, 2021 at 13:11
std::merge expects destination range doesn't overlap with either of the input ranges — Harry
– Harry, Commented Mar 6, 2021 at 13:13

Aykhan Hagverdili · Accepted Answer · 2021-03-06 13:13:00Z

Checking std::merge reference:

The behavior is undefined if the destination range overlaps either of the input ranges (the input ranges may overlap each other).

Thus, you can't use std::merge for in-place merging. Try writing a merge function and you will know why.

Collectives™ on Stack Overflow

How to std::merge two std::vector in-place?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related