So I have a long (very long) array X if integers {1,5,3,4,1,2,2} (I keep it short for example). And I have a short array Y what holds indexes of array X to remove {1, 3, 4}. After this operation X should be {1,3,2,2}. However after removing first index the array shrinks and the Y indexes become invalidated. How do I get around this? All that comes to my mind are recreating strategies (like inclusion and exclusion), but with a long array it's very inefficient.

CodePudding user response：

Since your collection (not an "array" as noted by commenters) is very long, you want to do this efficiently and not move all the elements multiple times.

Make two iterators for source and destination.
Loop through the collection of indexes, which should be sorted from lowest to highest.
At the first index location, point the destination to that position and the source to the next position (i 1). Step through, assigning *dest = *src ; and incrementing i, until you reach the next index in the index list. In that case, just increment src once instead, and advance the loop of index values. Now, after the second removal, your source and dest are 2 units apart and your assignment is moving each element back by two slots. When you hit the next one, you continue with them 3 apart, etc.

When you are done, resize the vector to the shorter size, based on the number of items you removed.

CodePudding user response：

You can search the exactly index of the values that have Y vector. When you delete the first one elemement in your case the value 1. Search the index of the second element and equals for the rest.

If you search every time the index. Fexemple in your case the index that program find befor every search are. 0,1,1,

CodePudding user response：

It isn't possible to remove elements of an array in C . An array has constant number of elements through its entire lifetime.

But algorithmically, speaking of "resizable arrays" (such as std::vector container), the solution is simple: Iterate the values of Y from largest to smallest. Sort them if necessary.

CodePudding user response：

First of all, this question only makes sense if we are using the term "array" colloquially and are actually talking about a resizable serial container -- in C , an std::vector.

The most straightforward way I see to do this in place is to compute the "spans" of items that need to be shifted from the indices that need to be deleted, and then do all the shifts keeping track of where the current end of undeleted items is.

The shift spans can be figured out easily if the deletion indices are sorted. The below assumes the indices are sorted. If they are are sorted, given two indices like i_k and i_{k 1} the span between them, inclusive, will be [i_k 1 , i_{k 1} - 1], basically, but it's slightly more complicated because you need to handle the spans at the ends of the array correctly and handle adjacent deletion indices.

The code below works but I may have missed some edge cases:

#include <iostream>
#include <vector>

std::vector<std::pair<int, int>> get_spans(const std::vector<int>& indices, int n) {
    if (indices.empty())
        return {};

    std::vector<std::pair<int, int>> spans;
    spans.reserve(indices.size());

    int num_indices = static_cast<int>(indices.size());
    for (int i = -1; i < num_indices;   i) {
        int from = ((i == -1) ? -1 : indices[i])   1;
        int to = ((i == num_indices-1) ? n : indices[i 1]) - 1;
        if (to < from) {
            continue;
        }
        spans.emplace_back(from, to);
    }

    return spans;
}

void shift_span(std::vector<int>& v, int src_from, int src_to, int dst) {
    if (src_from == dst)
        return;
    for (int i = src_from; i <= src_to;   i,   dst) {
        v[dst] = v[i];
    }
}

void delete_at_indices(std::vector<int>& v, const std::vector<int>& indices) {
    auto spans = get_spans(indices, v.size());
    if (spans.empty()) {
        return;
    }
    int i = 0;
    for (const auto& [from, to] : spans) {
        shift_span(v, from, to, i);
        i  = to - from   1;
    }

    v.resize(i);
}

void display_vec(const std::vector<int>& v) {
    for (auto i : v) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

int main()
{
    std::vector<int> v = { 1,5,3,4,1,2,2 };
    std::vector<int> delete_indices = { 1, 3, 4 };

    display_vec(v);
    delete_at_indices(v, delete_indices);
    display_vec(v);
}