7

[first, last]両方のエンドポイントを含めて range をスプライスしたい。before firstと toの要素へのイテレータがありますlast。私はそれを行うことができましsplice_after()たが、線形時間でしかできませんでした。

このスプライスは一定時間でできると思います。どうすればそれを行うことができstd::forward_listますか?

質問が明確でない場合は、私の問題を示すコード例を次に示します。

ライブワークスペースのコード

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;

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

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

    // trg.splice(trg.begin(), src, before_first, last); // no such splice
    auto end = last;
    ++end; // Ouch! splice has to find last again although I already had it  :(
    trg.splice_after(trg.begin(), src, before_first, end);

    cout << "Target after splice:\n";
    copy(trg.begin(), trg.end(), ostream_iterator<char>(cout," "));

    cout << "\nSource after splice:\n";
    copy(src.begin(), src.end(), ostream_iterator<char>(cout," "));

    cout << endl;
}

出力：

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

1 に答える 1

6

の仕様でforward_listは、範囲(first, last)を接合する必要があると述べていますが、残念ながら O(1) 時間でこれを行う方法はありません。これを行うには にアクセスする必要がlast-1あり、 にアクセスする唯一の方法last-1は から前方に反復することですfirst。

仕様が範囲をスプライスすること(first, last]であった場合、O(1) スプライスが可能になります。現在のforward_list仕様でこれを達成する方法はありません。

欠陥だと思います。ただし、私はすでに試しましたが、修正できませんでした：

http://cplusplus.github.com/LWG/lwg-defects.html#897

しかし、特にあなたのような委員会以外のメンバーから苦情が寄せられた場合、問題は過去に逆転しています. 苦情を申し立てる方法は、必要に応じて古い問題または関連する問題を参照して、新しい問題を開くことです。問題を開く手順については、こちらをご覧ください。

PS：質問に+1。

于 2013-01-05T21:52:59.237 に答える