Skip over element ranges in vector

Question

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?

@Eljay the second index is the index to the (theoretical) element after the range, just like how `std::vector<>::end()` returns an iterator to the (theoretical) element just after the end of the vector. — fortytoo, Apr 14 '22 at 13:57
So in range to remove `{3, 6}` `3` is inclusive and `6` is exclusive? `output` should be `{1, 2, 6, 8, 9, 10}` then? — Yksisarvinen, Apr 14 '22 at 13:59
General direction suggestion: Convert to "ranges to skip" into "ranges to keep", as as a vector of pair of iterators, and then use `std::ranges::join_view` to bind them together — , Apr 14 '22 at 13:59
@Frank I cannot do that. The list of index pairs must be ranges of elements to skip. This is for a weird allocator/array hybrid thing that I am working on, and indexing into the array while skipping over "deallocated" parts of the array is... surprisingly the only thing that has stumped me so far. — fortytoo, Apr 14 '22 at 14:03
@spitconsumer I'm not saying to change the data, just to create an intermediate structure computed from the list of ranges to skip. — , Apr 14 '22 at 14:04
I'm also confused about the example ranges definition and expected output. It doesn't seem consistent. Can you explain how you get to your expected output from the example range and example input? And since the example input has elements that happen to be sequential integers, it's unclear whether your range is supposed to be in terms of the elements themselves or the indices of the elements. — lurker, Apr 14 '22 at 14:07
@spitconsumer It is still confusing as to what you want to remove. If those ranges are 0-based offsets, then the canonical way to represent a range is to use the `(`, `[` to mark exclusive/inclusive begin and `)`, `]` to mark the exclusive/inclusive end. That's how most, if not all STL documentation defines the range that will be used. — PaulMcKenzie, Apr 14 '22 at 14:08
@PaulMcKenzie I thought about it but didn't want to make a fool of myself if I got the exclusive/inclusive mixed up (I am exceptionally tired). The ranges to skip over are [index, index), and yes they are 0-based offsets — fortytoo, Apr 14 '22 at 14:10
@spitconsumer How many items are you expecting to have in the vector? There is one simple, systematic way of removing the elements, but it requires copying the existing data to a temporary structure, adjusting the data there, and copying back the results to the original vector. — PaulMcKenzie, Apr 14 '22 at 14:15
The vector to iterate over is not bounded in size (except by memory limitations) and may be anywhere from 5 items large to 10,000. — fortytoo, Apr 14 '22 at 14:18
I'd probably implement this as an iterator type, the `begin` iterator constructed from the original range, and the set of index to skip, and the `end` having a sentinel value. Edit : There's probably already something in `std::ranges` for this. — François Andrieux, Apr 14 '22 at 14:19
Using [Yakk's technique](https://stackoverflow.com/a/31457319/4641116), you could construct `for (auto&& e : range_indexer(vec).skip(3, 6).skip(7, 8)) { ... }`. — Eljay, Apr 14 '22 at 14:20

score 1 · Answer 1 · answered Apr 14 '22 at 15:00

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.

score 0 · Answer 2 · edited Apr 14 '22 at 15:35

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

I wont accept my own answer, lest someone with arcane knowledge of how to do this in non-linear time comes along and dazzles me — fortytoo, Apr 14 '22 at 14:56
It looks like the function's user has to already know the new view's maximum length to effectively use this solution. An example of how you intend to use this function could help others to provide better answers. — François Andrieux, Apr 14 '22 at 15:38

Skip over element ranges in vector

2 Answers2