10

あるリストから別のリストへの範囲のスプライシングは、size()の複雑さを線形にすることを犠牲にして、一定の時間で達成できます。

C++11 では、一定時間であるstd::list必要がある場合に変更されました。size()これにより、たとえば gcc の実装が壊れました。[C++0x] std::list::size complexを参照してください。

range 以外splice()に、以前の C++03 準拠の実装で一定時間にできなかった他の理由はありますか? size() std::list

リスト全体または範囲を線形に接合するのはなぜ std::forward_listですか?

splice_after()、ケース (1) および (3)を参照してください。標準ドラフト N3485の 23.3.4.6 forward_list 操作 [forwardlist.ops] も参照してください。も実装していstd::forward_listませんsize()。

splice_after()forward_list が単独でリンクされたリストであることは知っていますが、一定の時間で範囲を実行できない理由がわかりません。私はおそらくここで些細なことを見逃しています...

編集: OK、少なくとも部分的には私の誤解でした。4 がソース リストに残らないと思っていました。コード：

#include <algorithm>
#include <iostream>
#include <forward_list>

using namespace std;

void dump_list(const forward_list<char>& l) {
    for(char c : l)
        cout << c << ' ';
    cout << '\n';
}

int main()
{
    forward_list<char> trg = {'a','b','c'};
    forward_list<char> src = {'1','2','3','4'};

    auto first = src.begin();
    auto last  = find(src.begin(), src.end(), '4');
    cout << "first = " << *first << ", last = " << *last << "\n\n";

    trg.splice_after(trg.begin(), src, first, last);

    cout << "Target after splice:\n";
    dump_list(trg);

    cout << "Source after splice:\n";
    dump_list(src);

    cout << endl;
    return 0;
}

出力：

first = 1, last = 4
Target after splice:
a 2 3 b c
Source after splice:
1 4
4

2 に答える 2

2

forward_list の場合、splice_after の範囲を一定時間にするにはどうすればよいでしょうか? ソース リストには、イテレータしかありません。ソースの順方向リンク リストからノードを削除するには、 の直前のノードが必要になるlastため、そのリンク リスト ノードのソースを直線的に検索する必要があります。firstしたがって、なぜとの間の距離が線形であるかlast

ソース リスト全体を使用するバージョンでも、ソースの末尾の直前のノードを検索する必要があるため、宛先の接合後の要素を指すように変更できます。そのため、ソースのサイズの線形時間も必要です。

于 2013-01-04T14:41:29.873 に答える
1

size範囲スプライスは、以前の C++ 標準では一定時間ではなかった唯一の理由です。実際、Sun CC コンパイラは、size一定時間とすべてのバージョンをsplice線形にすることを選択しました。

スプライシング先のリストに最後のノードをリンクできるようにするには、マージ先のリストをトラバースする必要があるため、前方リスト全体のスプライシングは線形です。ただし、範囲スプライスが線形である理由がわかりません。

編集: @Xeo が指摘するように、範囲ベースのバージョンには線形時間が必要です。lastこれは、 が範囲に含まれておらず、前first のイテレータを見つけるために検索する必要があるためです。 last

于 2013-01-04T15:11:35.273 に答える