Асимптотическая сложность std :: remove_if

Я работаю над методом стирания для структуры данных с жестко запрограммированным максимальным количеством элементов, N, который опирается на std::array чтобы избежать кучи памяти. Хотя std::array содержит N элементов только с некоторым числом, M, из них являются «соответствующими» элементами, где M меньше или равно N. Например, если N равно 10, а массив выглядит так:

std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };

…и если M равно 7, только первые 7 элементов являются «релевантными», в то время как остальные считаются ненужными (окончание { -1, -1, -9 } являются мусором). я использую int здесь для примера SO, но реальная программа хранит объекты, которые реализуют operator==, Ниже приведен рабочий пример, который удаляет все -1 и обновления М:

#include <algorithm>
#include <array>
#include <iostream>

constexpr unsigned N = 10;
unsigned           M = 7;
std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 };

int main() {
for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';

auto newEnd = std::remove_if(
std::begin(elements), std::begin(elements) + M,
[](const auto& element) {
return -1 == element;
}
);

unsigned numDeleted = M - std::distance(std::begin(elements), newEnd);
M -= numDeleted;
std::cout << "Num deleted: " << numDeleted << '\n';

for (unsigned i = 0; i < M; ++i)
std::cout << elements[i] << ' ';
std::cout << '\n';

return 0;
}

Вопрос, который я имею, состоит в том, какова асимптотическая сложность std::remove_if? Я полагаю, что между std::remove_if а также std::distance это всего O (2M) или O (M), где std::remove_if это более дорогая операция. Однако я не уверен, что std::remove_if равно O (N * M) из-за смещения элементов при удалении

редактироватьЯ понимаю, что это должно применяться к предикату M раз, но мне интересно, применяются ли N сдвигов каждый раз, когда предикат истинен