Ограничение remove_if только в части списка C++

У меня есть C++11 список сложных элементов, которые определены структурой node_info, node_info элемент, в частности, содержит поле time и вставляется в список упорядоченным образом в соответствии с его time значение поля. То есть список содержит различные node_info элементы, которые time приказал. Я хочу удалить из этого списка все узлы, которые проверяют некоторые конкретные условия, указанные coincidence_detectкоторый я сейчас реализую в качестве предиката для remove_if операция.

Так как мой список может быть очень большим (порядка 100k - 10M элементов), и для способа, которым я строю свой список, это coincidence_detect условие проверяется только несколькими (тысячами) элементами ближе к "нижнему" концу списка, то есть содержит элементы, чьи time значение меньше, чем некоторые t_xv, Я думал, что для повышения скорости моего кода мне не нужно запускать remove_if через весь список, но просто ограничьте его всеми теми элементами в списке, чьи time < t_xv,

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

Мой текущий код Элементы списка:

struct node_info {
char   *type = "x";
int    ID    = -1;
double time  = 0.0;
bool   spk   = true;
};

Предикат / условие для remove_if:

// Remove all events occurring at t_event
class coincident_events {
double t_event; // Event time
bool   spk;     // Spike condition
public:
    coincident_events(double time,bool spk_) : t_event(time), spk(spk_){}
    bool operator()(node_info node_event){
        return ((node_event.time==t_event)&&(node_event.spk==spk)&&(strcmp(node_event.type,"x")!=0));
    }
};

Фактическое удаление из списка:

void remove_from_list(double t_event, bool spk_){
// Remove all events occurring at t_event
coincident_events coincidence(t_event,spk_);
event_heap.remove_if(coincidence);
}

Псевдо основной:

int main(){
    // My list
    std::list<node_info> event_heap;

    ...
    // Populate list with elements with random time values, yet ordered in ascending order
    ...

    remove_from_list(0.5, true);

    return 1;
}

Кажется, что remove_if не может быть идеальным в этом контексте. Я должен рассмотреть вместо того, чтобы создать экземпляр итератора и запустить явный for цикл, как предлагается, например, в этом посте?

Источник

3 ответа

Решение

Благодарю. Я использовал ваши комментарии и придумал это решение, которое, по-видимому, увеличивает скорость в 5-10 раз.

void remove_from_list(double t_event,bool spk_){
    coincident_events coincidence(t_event,spk_);
    for(auto it=event_heap.begin();it!=event_heap.end();){
        if(t_event>=it->time){
            if(coincidence(*it)) {
                it = event_heap.erase(it);
            }
            else
                ++it;
        }
        else
            break;
        }
}

Идея сделать erase вернуть it (как уже ++it) было предложено этим другим постом. Обратите внимание, что в этой реализации я фактически стираю все элементы списка до t_event значение (то есть, я передаю все, что я хочу для t_xv).

Источник

Кажется, что remove_if не может быть идеальным в этом контексте. Стоит ли вместо этого рассматривать создание итератора и запуск явного цикла for?

Да и да. Не боритесь за использование кода, который мешает вам достичь ваших целей. Будь проще. В C++ нечего стыдиться.

Источник

Во-первых, сравнивая double это не очень хорошая идея, так как вы подвержены ошибкам с плавающей запятой.

Вы всегда можете найти точку, где вы хотите сделать поиск, используя lower_bound (Я предполагаю, что ваш список правильно отсортирован).

Вы можете использовать алгоритм свободных функций std::remove_if с последующим std::erase удалить элементы между итератором, возвращаемым remove_if и тот, который вернулся lower_bound,

Однако, делая это, вы выполняете несколько проходов в данных и перемещаете узлы, что влияет на производительность.

Смотрите также: https://en.cppreference.com/w/cpp/algorithm/remove

Таким образом, в конце концов, вероятно, предпочтительнее создать собственный цикл для всего контейнера и для каждой проверки, нужно ли его удалять. Если нет, то проверьте, следует ли вырваться из цикла.

for (auto it = event_heap.begin(); it != event_heap.end(); )
{
    if (coincidence(*it))
    {
        auto itErase = it;
        ++it;
        event_heap.erase(itErase)
    }
    else if (it->time < t_xv)
    {
        ++it;
    }
    else
    {
        break;
    }
}

Как видите, код может легко стать достаточно длинным для чего-то, что должно быть простым. Таким образом, если вам нужно часто делать такой алгоритм, подумайте о написании собственного универсального алгоритма.

Кроме того, на практике вам может не потребоваться выполнить полный поиск конца, используя первое решение, если вы обрабатываете данные в порядке возрастания времени.

Наконец, вы можете рассмотреть возможность использования std::set вместо. Это может привести к более простому и оптимизированному коду.

Источник
Другие вопросы по тегам