6

注:これは、「リストを使用するか、デキューを使用するか」という問題ではありません。に直面したイテレータの有効性についての質問ですinsert()。

これは簡単な質問かもしれませんが、私はこれを行う正しい方法を理解するにはあまりにも密集しています。ネットワーク トラフィック バッファを (良くも悪くも) として実装std::list<char> bufし、現在の読み取り位置を iterator として維持していますreadpos。

データを追加するときは、次のようにします

buf.insert(buf.end(), newdata.begin(), newdata.end());

readpos私の質問は、イテレータを有効に保つにはどうすればよいですか? それが old の中間を指している場合、buf(std::list のイテレータ保証により) 問題ないはずですが、通常はすべてのデータを読み取って処理した可能性があり、readpos == buf.end(). readpos 挿入後、常に次の未読文字を指すようにしたいのですが、挿入の場合は最初に挿入された文字でなければなりません。

助言がありますか？(以下に提案されているように、バッファを a に変更するstd::deque<char>だけで、タスクにより適しているように見えます。)

更新: GCC4.4 を使用した簡単なテストから、deque と list の動作が次の点で異なることがreadpos = buf.end()わかりました。最後に挿入した後、readpos はリスト内で壊れていますが、deque 内の次の要素を指しています。これは標準保証ですか？

( cplusplusによると、すべての deque::insert()はすべてのイテレータを無効にしました。これは良くありません。両端キュー内の位置を追跡するには、イテレータよりもカウンタを使用する方がよいでしょうか?)

4

4 に答える 4

5 
if (readpos == buf.begin())
{
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    readpos = buf.begin();
}
else
{
    --readpos;
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    ++readpos;
}

エレガントではありませんが、うまくいくはずです。

于 2011-06-03T17:38:01.560 に答える
4

http://www.sgi.com/tech/stl/List.htmlから

「リストには、挿入とスプライシングによって要素をリストするイテレータが無効にならず、削除しても削除された要素を指すイテレータのみが無効になるという重要な特性があります。」

したがって、readpos挿入後も有効である必要があります。

でも...

std::list< char >この問題を解決するには非常に非効率的な方法です。に格納する各バイトにstd::listは、バイトを追跡するためのポインターと、リスト ノード構造のサイズ (通常はさらに 2 つのポインター) が必要です。これは、1 バイトのデータを追跡するために使用される、少なくとも 12 または 24 バイト (32 または 64 ビット) のメモリです。

std::deque< char>おそらくこれにはより良いコンテナです。バックで一定時間の挿入を提供するようstd::vectorに、フロントで一定時間の除去も提供します。最後に、likestd::vector std::dequeはランダム アクセス コンテナーであるため、反復子の代わりにオフセット/インデックスを使用できます。これら 3 つの機能により、効率的な選択が可能になります。

于 2011-06-03T17:53:35.690 に答える
0

私は確かに密でした。この規格は、必要なすべてのツールを提供してくれます。具体的には、シーケンス コンテナー要件 23.2.3/9 には次のように記載されています。

from から返されるイテレータは、 またはifa.insert(p, i, j)に挿入された最初の要素のコピーを指します。api == j

次に、list::insert(23.3.5.4/1) の説明:

イテレータと参照の有効性には影響しません。

実際pos、リスト内の現在のイテレータが消費されている場合、次のように言えます。

auto it = buf.insert(buf.end(), newdata.begin(), newdata.end());

if (pos == buf.end()) { pos = it; }

リスト内の新しい要素の[it, buf.end())範囲は で、まだ処理されていない要素の範囲は です[pos, buf.end())。これが機能するのは、挿入前posに等しい場合buf.end()、挿入後も挿入後であるためです。

于 2014-06-16T20:21:16.880 に答える
-1

list<char>文字列を格納するための非常に非効率的な方法です。文字列自体よりもおそらく10〜20倍大きく、さらにすべての文字のポインタを追跡しています...

std::dequeue<char>代わりに使用することを検討しましたか？

[編集]

実際の質問に答えるために、要素を追加および削除しても、list...のイテレータが無効になることはありませend()んend()。readposしたがって、イテレータを更新するために新しい要素を挿入する時点で、特別な場合としてそれをチェックする必要があります。

于 2011-06-03T17:17:55.187 に答える