Skip over element ranges in vector-CodePudding

I have a list of pairs of (0-based offset) indices into a vector, and I want to index into this vector but skip over the ranges defined by the index pairs. For example:

vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
ranges to skip = {[3, 6), [7, 8)}

print out all elements of vector via some indexer function
output = 1, 2, 3, 7, 9, 10

How would I implement this? i.e what should "ranges to skip" be (std::map?) and what would the algorithm for the indexer function be?

CodePudding user response：

As @Frank said in the comments, it would be much simpler to convert the "ranges to skip" problem into the "ranges to keep" problem.

Suppose we have calculated the pair value of "ranges to keep" based on the "ranges to skip", ie

std::vector v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector ranges_to_keep = {std::pair{0, 3}, {6, 7}, {8, 10}};

Then we just need to convert these pair values into subranges and join them into a single sequence, which can easily be done with C 20 <ranges>

auto r = ranges_to_keep
       | std::views::transform([&v](auto r) { 
           auto [beg, end] = r;
           return std::views::counted(v.begin()   beg, end - beg);
         }) 
       | std::views::join;

Demo

The remaining problem is how to calculate the value of ranges_to_keep, but I don't think it's that hard.

CodePudding user response：

The answer was much simpler than I anticipated ...

int& indexer(std::vector<int>& vec,
             const std::vector<std::pair<std::size_t, std::size_t>>& skip,
             std::size_t index) {
    for (auto& range : skip) {
        if (index >= range.first)
            index  = range.second - range.first;
        else break;
    }

    return vec[index];
}

skip is assumed to have no overlapping ranges, and is also assumed to be sorted by the first value of each pair. Getting the size of a vector with element ranges skipped can be done like so:

std::size_t get_skipped_size(const std::vector<int>& vec,
                             const std::vector<std::pair<std::size_t, std::size_t>>& skip) {
    std::size_t skipped_size = vec.size();
    for(auto& range : skip)
        skipped_size -= range.second - range.first;
    return skipped_size;
}