mercredi 6 avril 2016

Is it acceptable to use std::merge for overlapping ranges

I have an algorithm which requires applying set union many times to growing sets of integers. For efficiency I represent the sets as sorted vectors, so that their union can be obtained by merging them. I have a problem

A classical way to merge two sorted vectors is this:

void inmerge(vector<int> &a, const vector<int> &b) {
  a.reserve(a.size() + b.size());
  std::copy(b.begin(), b.end(), std::back_inserter(a));
  std::inplace_merge(a.begin(), a.end() - b.size(), a.end());
}

Unfortunately, std::inplace_merge appears to be much slower than std::sort in this case, because of the allocation overhead. The fastest way is to use std::merge directly to output into one of the vectors. In order not to write a value before reading it, we have to proceed from the ends, like this:

void inmerge(vector<int> &a, const vector<int> &b) {
  a.resize(a.size() + b.size());
  orig_a_rbegin = a.rbegin() + b.size();
  std::merge(orig_a_rbegin, a.rend(), b.rbegin(), b.rend(), a.rend(), [](Cid a, Cid b) { return a > b; });
}

It is for sure that an implementation of merge will never write more elements than it has read, so this is a safe thing to do. Unfortunately, the C++ standard (even C++17 draft) forbids this:

The resulting range shall not overlap with either of the original ranges.

Is it okay to ignore this restriction if I know what I'm doing?

Aucun commentaire:

Enregistrer un commentaire