C++ remove_if без итерации по всему вектору

Question

У меня есть вектор указателей, указывающих примерно на 10 МБ пакетов. При этом с первых 2 МБ я хочу удалить все те, которые соответствуют моему предикату. Проблема здесь remove_if перебирает весь вектор, хотя это не требуется в моем случае использования. Есть ли другой эффективный способ?

fn_del_first_2MB
{
    uint32 deletedSoFar = 0;
    uint32 deleteLimit = 2000000;

    auto it = std::remove_if (cache_vector.begin(), cache_vector.end(),[deleteLimit,&deletedSoFar](const rc_vector& item){
    if(item.ptr_rc->ref_count <= 0) {
        if (deletedSoFar < deleteLimit) {
            deletedSoFar += item.ptr_rc->u16packet_size;
        delete(item.ptr_rc->packet);    
        delete(item.ptr_rc);
            return true;
        }
        else    
            return false;
    }
    else
        return false;
    });
    cache_vector.erase(it, cache_vector.end());
}

В приведенном выше коде, как только deletedSoFar больше, чем deleteLimitлюбая итерация более чем нежелательна.

Answer 1

Вы можете использовать свой собственный цикл:

void fn_del_first_2MB()
{
    const uint32 deleteLimit = 2000000;

    uint32 deletedSoFar = 0;
    auto dest = cache_vector.begin();
    auto it = dest

    for (; it != cache_vector.end(); ++it) {
        const auto& item = *it;

        if (item.ptr_rc->ref_count <= 0) {
            deletedSoFar += item.ptr_rc->u16packet_size;
            delete(item.ptr_rc->packet);    
            delete(item.ptr_rc);
            if (deletedSoFar >= deleteLimit) {
                ++it;
                break;
            }
        } else if (dest != it) {
            *dest = std::move(*it);
            ++dest;
        }
    }
    cache_vector.erase(dest, it);
}

Answer 2

Вместо cache_vector.end() поставить свой собственный маркер итератора myIter, С remove_if вариант, вы должны следовать идиоме удаления-удаления. Вот пример, который влияет только на первые 4 элемента:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    size_t index = 4; // index is something you need to calculate
    auto myIter = vec.begin() + index; // Your iterator instead of vec.end()
    vec.erase(std::remove_if(vec.begin(), myIter, [](int x){return x < 3; }), myIter);
    // modified vector:
    for (const auto& a : vec)
    {
        std::cout << a << std::endl;
    }
    return 0;
}

Answer 3

Там нет необходимости std::remove_if() пройти .end() Итератор как второй аргумент: если первый аргумент может достигать второго аргумента путем увеличения, любые итераторы могут быть переданы.

Есть некоторое осложнение, так как ваше состояние зависит от накопленного размера элементов, встречающихся до сих пор. Оказывается, это выглядит так, как будто std::remove_if() не будет использоваться Нечто подобное должно работать (хотя я не уверен, если это использование std::find_if() на самом деле законно, так как он продолжает изменять предикат):

std::size_t accumulated_size(0u);
auto send(std::find_if(cache_vector.begin(), cache_vector.end(),
                              [&](rc_vector const& item) {
        bool rc(accumulated_size < delete_limit);
        accumulated_size += item.ptr_rc->u16packet_size;
        return rc;
    });
std::for_each(cache_vector.begin(), send, [](rc_vector& item) {
       delete(item.ptr_rc->packet);    
       delete(item.ptr_rc);
    });
cache_vector.erase(cache_vector.begin(), send);

std::for_each() можно сложить в использование std::find_if() также, но я предпочитаю держать вещи логически разделенными. Для достаточно большой последовательности может быть разница в производительности, когда память должна быть перенесена в кэш дважды. Для приведенных крошечных чисел сомневаюсь, что разницу можно измерить.