1

std::arrayヒープメモリを回避するために依存する、ハードコーディングされた最大要素数 N を持つデータ構造の消去方法に取り組んでいます。に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 }はジャンクです)。ここでは SO の例を使用してintいますが、実際のプログラムには .xml を実装するオブジェクトが格納されていますoperator==。以下は、すべてを削除して-1M を更新する実際の例です。

#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シフトが適用されているかどうか疑問に思っています

4

2 に答える 2

4

cppreference による:

複雑さ: まさにstd::distance(first, last)述語の適用。

の呼び出し後に未指定の値を持つ可能性があるため、削除された要素にはシフト操作はありません。std::remove_if

于 2016-08-11T06:02:47.967 に答える
2

編集

この回答は、振り返ってみると、尋ねられたものよりも複雑な質問に対処しています-「プッシュバックツーエンド」機能を線形時間で実装するにはどうすればよいですか。尋ねられた特定の質問に関して-関連してremove_if-@ millenimumbugの答えはそれをよりよく扱います。

削除されたm個のアイテムのそれぞれをΘ(n)距離シフトする必要があるため、複雑さがΘ(mn)になると考える理由がわかります。

実際には、時間Θ(n)と追加のO(1)スペース (数個の追加イテレータ) でこれを行うことができます。

アルゴリズムの可能な実装の反復を示す次の図を検討してください。

ここに画像の説明を入力

赤いアイテムは、この時点で最後まで削除される認識されたアイテムの連続したグループです (これを記録するには 2 つのポイントが必要です)。緑色のアイテムは、現在検討中のアイテムです (別のポインター)。

緑色のアイテムを削除する場合、赤色のグループはそれを含めることで単純に大きくなります。これは、赤いグループが展開されている次の図に示されています。次の反復では、緑色のアイテムがその右側になります。ここに画像の説明を入力

そうでない場合は、すべての赤いグループをシフトする必要があります。赤のグループでは線形時間でこれを行うことができると考える人もいるかもしれません (イテレータは順方向イテレータのみであることが保証されていますが)。

複雑さはなぜ線形なのですか? これは、左のグループに対して左にシフトされた緑の要素と同等であると想像できるからです。理論的根拠は、償却分析の理論的根拠に似ています。

次の図は、2 番目のケースを示しています。次の反復では、緑の要素 (検討中) が再び赤のグループの右側に配置されます。

ここに画像の説明を入力

于 2016-08-11T06:23:19.023 に答える