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