I managed to find a simple wrapper around the 3-legged version of std::transform
, both for the original and the inverse problem (both algorithms are O(N + M)
in the input sequences)
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt remove_ranks(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
auto delta = 0;
return std::transform(first1, last1, d_first,
[&, first2](int rank) mutable {
while (first2 != last2 && rank > *first2) { ++first2; ++delta; }
return rank - delta;
});
}
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt insert_ranks(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
auto delta = 0;
return std::transform(first1, last1, d_first,
[&, first2](int rank) mutable {
while (first2 != last2 && rank + delta >= *first2) { ++first2; ++delta; }
return rank + delta;
});
}