How to update ranks for some subset?

Question

I have input consisting of ranks in some contest (let's say a marathon) with values in the range [0, N). There are several sub-contests (e.g. based on age, gender etc.) that are only interesting for a subset team and for which another subset not_eligible do not qualify.

I am looking for an efficient algorithm (preferably written in terms of the Standard Library), that will update the ranks. 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 });

Because only 1 constestant below #9 (i.e. #8) wasn't eligible, the rank of #9 is decreased by 1, and because there were 3 non-eligible finishers (i.e. #8, #10 and #12) before #13, that rank is updated by 3 from #13 to #10 for that particular sub-contest.

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

How can I achieve the above using a combination of standard algorithms? I was hoping to be able to do it in O(N + M) complexity for input ranges of length N and M (e.g. through the 5-legged std::transform).

UPDATE: I am also interested in the inverse algorithm: given the ranking of a sub-contest, how to update the ranks of the contenders in the subcontest when adding the previously non-eligible participants?

Answer 1

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

Live Example

Answer 2

There isn't really an obvious way to leverage the existing algorithms; you're better off taking the example code for merge and adapting it:

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

For the inverse, again adapting merge should work.