Гарантируется ли std::remove_if вызывать предикат по порядку?

Будет ли std::remove_if всегда вызывать предикат для каждого элемента по порядку (в соответствии с порядком итератора) или он может вызываться не по порядку?

Вот игрушечный пример того, что я хотел бы сделать:

void processVector(std::vector<int> values)
{
    values.erase(std::remove_if(values.begin(), values.end(), [](int v)
    {
        if (v % 2 == 0)
        {
            std::cout << v << "\n";
            return true;
        }
        return false;
    }));
}

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

Можно ли предположить, что мой предикат будет вызываться для каждого элемента по порядку?

Я предполагаю, что политики выполнения C++17 устранят это неоднозначно, но, поскольку C++17 еще не вышел, это, очевидно, мне не поможет.

Редактировать: Кроме того, это хорошая идея? Или есть лучший способ сделать это?

Источник

3 ответа

Решение

Стандарт не дает никаких гарантий порядка вызова предиката.

То, что вы должны использовать, это stable_partition, Вы разделяете последовательность на основе вашего предиката. Затем вы можете пройти секционированную последовательность, чтобы выполнить любой "побочный эффект", который вы хотели сделать, так как stable_partition обеспечивает относительный порядок обоих наборов данных. Затем вы можете стереть элементы из vector,

stable_partition должен быть использован здесь, потому что erase_if оставляет содержимое "стертых" элементов неопределенным.

В коде:

void processVector(std::vector<int> values)
{
    auto it = std::stable_partition(begin(values), end(values), [](int v) {return v % 2 != 0;});

    std::for_each(it, end(values), [](int v) {std::cout << v << "\n";});

    values.erase(it, end(values));
}
Источник

Немного опоздал на вечеринку, но вот мое мнение:

Хотя порядок не указан, он будет включать в себя прыжки через обручи для реализации порядка, отличного от первого к последнему, из-за следующего:

  • Сложность указана как "точноstd::distance(first, last)применения предиката", что требует посещения каждого элемента ровно один раз.
  • ИтераторыForwardIterators, что означает, что их можно только увеличивать.
  • [C++17 и выше] Чтобы предотвратить параллельную обработку, можно использовать версию, которая принимает политику выполнения, и передатьstd::execution::seq.

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

Источник: https://en.cppreference.com/w/cpp/algorithm/remove

Источник

Они должны быть обработаны по порядку, но это не гарантировано.

std::remove_if() перемещает "удаленные" элементы в конец контейнера, они фактически не удаляются из контейнера, пока erase() называется. Обе операции могут сделать недействительными существующие итераторы в std::vector,

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