Memory corruption when removing elements from a vector of shared pointers

Question

I was dealing with a bothersome error yesterday involving a function meant to delete elements from a vector of shared pointers. Here's the problematic code:

template <typename T>
void flush(
    std::vector<std::shared_ptr<T>>& offers
) {
    std::vector<unsigned int> idxs;
    for (unsigned int i = 0; i < offers.size(); i++) {
        if (!offers[i]->is_available()) {
            idxs.push_back(i);
        }
    }
    for (unsigned int i : idxs) {
        offers[i] = offers.back();
        offers.pop_back();
    }
}

Occasionally, elements of the offers vector would become corrupted (i.e. they would point to garbage data). I ended up changing the above code to use a more standard erase-remove idiom:

template <typename T>
void flush(
    std::vector<std::shared_ptr<T>>& offers
) {
    offers.erase(
        std::remove_if(
            offers.begin(),
            offers.end(),
            [](std::shared_ptr<T> offer) { return !offer->is_available(); }
        ),
        offers.end()
    );
}

Now I don't see the same problem as before (and this is more elegant in any case). However, I want to understand why this works when the previous code didn't. I suspect it has something to do with the wrong elements being retained in the vector or perhaps with something strange happening with the pointers' reference counting, but I would appreciate some insight into exactly what is going on here.

Answer 1

Just posting a quick answer so this can be marked as resolved. The issue is the second loop: in order for the algorithm to work, the indices need to be sorted in descending order; otherwise we'll access out-of-bounds data. I believe the following should behave correctly:

template <typename T>
void flush(
    std::vector<std::shared_ptr<T>>& offers
) {
    std::vector<unsigned int> idxs;
    for (int i = offers.size()-1; i >= 0; i--) {
        if (!offers[i]->is_available()) {
            idxs.push_back(i);
        }
    }
    for (unsigned int i : idxs) {
        offers[i] = offers.back();
        offers.pop_back();
    }
}