How to update rows for some subset?

Question

I have an input consisting of ranks in some contest (say, a marathon) with values ​​in the range [0, N). There are several sub-contests (for example, based on age, gender, etc.) that are interesting only for a subset teamand for which another subset is not_eligiblenot suitable.

I am looking for an efficient algorithm (preferably written in terms of the standard library) that will update the series. Example:

auto team = std::vector<int>{ 1, 2, 9, 13 };
auto not_eligible = std::vector<int>{ 8, 10, 12 };
std::vector<int> result;

// some algorithm

assert(result == std::vector<int>{ 1, 2, 8, 10 });

Since only 1 constant below # 9 (i.e. # 8) is not eligible, rank No. 9 is reduced by 1, but because there are 3 inappropriate finishers (i.e. # 8, # 10 and # 12) to # 13 this rank is updated to 3 from # 13 to # 10 for this particular sub-contest.

Note 8 and 10 are part result, but not because they were combined from non_eligible, but because their ranks were taken 9 and 13 from team.

How can I achieve the above using a combination of standard algorithms? I was hoping I could do this in complexity O(N + M)for length input ranges Nand M(for example, through 5-legged std::transform).

The UPDATE . I am also interested in the inverse algorithm: given the ranking of the sub-competition, how to update the ranks of applicants in the subcontinent when adding previously unauthorized participants?

Answer 1

3-legged std::transform, , ( O(N + M) )

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;
    });
}

Live

Answer 2

algorithm s; merge :

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt update_ranks(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    typename std::iterator_traits<InputIt1>::value_type adjust = {};
    while (first1 != last1) {
        if (first2 != last2 && *first2 < *first1) {
            ++adjust;
            ++first2;
        } else {
            *d_first = *first1 - adjust;
            ++first1;
            ++d_first;
        }
    }
    return d_first;
}

merge.