c++ - std::remove_if 的渐近复杂度

Question

我正在为具有硬编码最大元素数 N 的数据结构开发一种删除方法，它依赖于 std::array 来避免堆内存。虽然 std::array 只包含 N 个元素，但只有 M 个元素，其中 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 并更新 M 的工作示例:

#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 次转换

Answer 1

通过 cppreference :

Complexity: Exactly std::distance(first, last) applications of the predicate.

被移除的元素没有移位操作，因为它们在调用 std::remove_if 后可能具有未指定的值