Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A sketch of inplace_merge
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>
template <typename ForwardIt>
void my_inplace_merge(ForwardIt first, ForwardIt middle, ForwardIt last)
{
if (first == middle || middle == last) return;
using T = typename std::iterator_traits<ForwardIt>::value_type;
// call the range [first, middle) x, and the range [middle, last) y
// make a buffer big enough to hold the smaller range
auto d1 = std::distance(first, middle);
auto d2 = std::distance(middle, last);
// we're going to write to the range in place
ForwardIt out = first;
// we're going to read from each range
ForwardIt readx = first;
ForwardIt ready = middle;
// and we're going to read and write from tmp. tmp is a buffer than can hold
// values, but we don't know that T is default constructible, so make a char
// buffer big enough
auto n = std::min(d1, d2);
auto tmp = std::make_unique<char[]>(n * sizeof(T));
// we're going to use tmp as a ring buffer
T* begint = reinterpret_cast<T*>(tmp.get());
T* endt = begint + n;
T* readt = begint;
T* writet = begint;
bool tmp_full = false;
// loop until we reach the end of either x or y
while (readx != middle && ready != last)
{
if (readt != writet)
{
// the next lowest x value is in tmp
if (*ready < *readt)
{
// x -> tmp, y -> out
*writet++ = std::move(*readx);
if (writet == endt) writet = begint;
*out = std::move(*ready);
++ready;
tmp_full = writet == readt;
}
else
{
// x -> tmp, tmp -> out
*writet++ = std::move(*readx);
if (writet == endt) writet = begint;
*out = std::move(*readt);
++readt;
if (readt == endt) readt = begint;
}
}
else
{
// tmp is currently empty, we're comparing the x with y directly
if (*ready < *readx)
{
// x -> tmp, y -> out
*writet++ = std::move(*readx);
if (writet == endt) writet = begint;
*out = std::move(*ready);
++ready;
tmp_full = writet == readt;
}
}
++readx;
++out;
// if the temporary buffer is full, we must have exhausted either x or y
assert(!tmp_full || readx == middle || ready == last);
}
if (out == middle)
{
// any remaining values of x are now in tmp, so do a "normal" merge from tmp
// and y to out
while (readt != writet || tmp_full)
{
if (ready != last && *ready < *readt)
{
*out++ = std::move(*ready);
++ready;
}
else
{
*out++ = std::move(*readt);
++readt;
if (readt == endt) readt = begint;
tmp_full = false;
}
}
}
else if (ready == last)
{
// all the values of y are accounted for, and we know that all the values of
// x in tmp are less than the remaining ones, so swap tmp with x repeatedly
// until we reach the middle, then output the remaining tmp
using std::swap;
T* p = readt;
while (out != middle)
{
swap(*p, *out);
++p, ++out;
if (p == endt) p = begint;
if (p == writet) p = readt;
}
while (out != last)
{
*out = std::move(*p);
++p, ++out;
if (p == endt) p = begint;
if (p == writet) p = readt;
}
}
}
#include <algorithm>
template <typename ForwardIt>
void naive_inplace_merge(ForwardIt first, ForwardIt middle, ForwardIt last)
{
while (first != middle && middle != last)
{
if (*middle < *first)
{
std::iter_swap(middle, first);
auto i = middle;
std::rotate(++first, i, ++middle);
}
else
{
++first;
}
}
}
template <typename BidirIt>
void naive_inplace_merge2(BidirIt first, BidirIt middle, BidirIt last)
{
using T = typename std::iterator_traits<BidirIt>::value_type;
auto d1 = std::distance(first, middle);
auto d2 = std::distance(middle, last);
auto n = std::min(d1, d2);
auto tmp = std::make_unique<char[]>(n * sizeof(T));
T* begint = reinterpret_cast<T*>(tmp.get());
T* endt = begint + n;
if (d1 <= d2)
{
std::move(first, middle, begint);
std::merge(begint, endt, middle, last, first);
}
else
{
std::move(middle, last, begint);
auto i = std::move_backward(first, middle, last);
std::merge(i, last, begint, endt, first);
}
}
#include <forward_list>
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
// some tests
// split at 5
// vector<int> v{0,2,4,6,8,1,3,5,7,9};
// vector<int> v{0,1,2,3,4,5,6,7,8,9};
// vector<int> v{5,6,7,8,9,0,1,2,3,4};
// forward_list<int> v{5,6,7,8,9,0,1,2,3,4};
// typename decltype(v)::difference_type split = 5;
// split at 3
// vector<int> v{0,1,2,3,4,5,6,7,8,9};
// vector<int> v{7,8,9,0,1,2,3,4,5,6};
// forward_list<int> v{7,8,9,0,1,2,3,4,5,6};
// typename decltype(v)::difference_type split = 3;
// split at 7
// vector<int> v{0,1,2,3,4,5,6,7,8,9};
// vector<int> v{3,4,5,6,7,8,9,0,1,2};
forward_list<int> v{3,4,5,6,7,8,9,0,1,2};
typename decltype(v)::difference_type split = 7;
auto b = v.begin();
auto m = b;
advance(m, split);
auto e = v.end();
my_inplace_merge(b, m, e);
for (auto i : v)
cout << i << ", ";
cout << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment