4

ソートされたベクトルと別のソートされたベクトルのインプレース結合を行うための効率的な方法が欲しいです。インプレースとは、一時的であっても、アルゴリズムがユニオンを格納するためのまったく新しいベクトルやその他のストレージを作成してはならないことを意味します。代わりに、最初のベクトルは、新しい要素の数だけ単純に増加する必要があります。

何かのようなもの：

void inplace_union(vector & A, const vector & B);

その後、AにはAユニオンB のすべての要素が含まれ、並べ替えられます。

std::set_unioninは、 A<algorithm>である宛先を上書きするため、機能しません。

また、これは 2 つのベクトルを 1 回通過するだけで実行できますか?

編集: AとB の両方にある要素は、 Aに 1 回だけ出現する必要があります。

4

3 に答える 3

6

アルゴリズムを使用できると思いますstd::inplace_merge。サンプルコードは次のとおりです。

void inplace_union(std::vector<int>& a, const std::vector<int>& b)
{
    int mid = a.size(); //Store the end of first sorted range

    //First copy the second sorted range into the destination vector
    std::copy(b.begin(), b.end(), std::back_inserter(a));

    //Then perform the in place merge on the two sub-sorted ranges.
    std::inplace_merge(a.begin(), a.begin() + mid, a.end());

    //Remove duplicate elements from the sorted vector
    a.erase(std::unique(a.begin(), a.end()), a.end());
}
于 2010-09-03T04:58:08.490 に答える
2

はい、これはインプレースで、O（n）時間で、両方の入力がソートされ、両方のベクトルを1回通過することを前提として実行できます。方法は次のとおりです。

A（宛先ベクトル）を次のように拡張しますB.size()-新しい要素のためのスペースを作ります。

Bの終わりと元の終わりから始めて、2つのベクトルを逆方向​​に繰り返しAます。ベクトルが小さい→大きい（最後に大きい）ようにソートされている場合は、大きい方の数を指すイテレータを取得し、の真の端に貼り付けますA。Bのイテレータがの先頭に到達するまで続行しますB。ここでは、逆イテレータが特に優れていることがわかります。

例：

A: [ 1, 2, 4, 9 ]
B: [ 3, 7, 11 ]

* = iterator, ^ = where we're inserting, _ = unitialized
A: [ 1, 3, 4, 9*, _, _, _^ ]   B: [ 3, 7, 11* ]
A: [ 1, 3, 4, 9*, _, _^, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9, _^, 9, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9^, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*, 4^, 4, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*^, 3, 4, 7, 9, 11 ]  B: [ 3, 7, 11 ]

スーパーエディット：検討しましたstd::inplace_mergeか？（私はちょうど再発明したかもしれませんか？）

于 2010-09-03T04:56:42.197 に答える