27

タイトルが尋ねるように。

両端キューについての私の理解は、それが「ブロック」を割り当てたということでした。より多くのスペースを割り当てるとイテレータが無効になる方法がわかりません。どちらかといえば、両端キューのイテレータはベクトルよりも多くの保証を持っていると思うでしょう。

4

7 に答える 7

21

C++ 標準では、deque の実装方法が指定されていません。新しいチャンクを割り当てて前のチャンクにチェーンすることによって新しいスペースを割り当てる必要はありません。必要なのは、両端での挿入が一定時間償却されることだけです。

そのため、必要な保証を与えるように deque を実装する方法を理解するのは簡単ですが [*]、それが唯一の方法ではありません。

[*] イテレータは、要素への参照と、要素が含まれるブロックへの参照を持っているため、ブロックの端に到達したときにブロックの端から前後に進むことができます。さらに、両端キュー自体への参照を想定しているためoperator+、ランダム アクセス イテレータに期待される一定時間になる可能性があります。ブロックからブロックへのリンクのチェーンをたどるだけでは十分ではありません。

于 2009-05-27T00:16:52.763 に答える
15

さらに興味深いのは、両端キューの要素への参照が無効push_backにpush_frontならないことです。イテレータのみが無効と見なされます。

私の知る限り、標準はその理由を述べていません。ただし、リストのようにすぐ近くにあるものを認識する反復子が実装されている場合、両端キューの端とブロックの端の両方にある要素を指している場合、その反復子は無効になります。

于 2009-05-27T04:07:53.483 に答える
7

私の推測。push_back/push_frontは、新しいメモリ ブロックを割り当てることができます。deque イテレーターは、インクリメント/デクリメント演算子が次のブロックにジャンプするタイミングを認識している必要があります。実装は、その情報を反復子自体に格納する場合があります。push_back/push_frontの後に古いイテレータをインクリメント/デクリメントすると、意図したとおりに機能しない場合があります。

このコードは実行時エラーで失敗する場合としない場合があります。私のVisual Studioでは、デバッグモードで失敗しましたが、リリースモードで最後まで実行されました. Linux では、セグメンテーション違反が発生しました。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> x(1), y(1);
    std::deque<int>::iterator iterx = x.begin();
    std::deque<int>::iterator itery = y.begin();

    for (int i=1; i<1000000; ++i) {
        x.push_back(i);
        y.push_back(i);
        ++iterx;
        ++itery;
        if(*iterx != *itery) {
            std::cout << "increment failed at " << i << '\n';
            break;
        }
    }
}
于 2011-03-18T04:08:19.787 に答える
2

チャンクで割り当てている場合でも、(ベクターの場合のように) 十分なスペースがない場合、挿入によってその特定のチャンクが再割り当てされます。

于 2009-05-26T22:31:02.600 に答える
0

標準はそれができると言っているからです。dequeをチャンクのリストとして実装することは必須ではありません。これは、特定の事前条件と事後条件、および特定のアルゴリズムの複雑さの最小値を備えた特定のインターフェースを義務付けています。

実装者は、これらの要件をすべて満たす限り、選択した方法で自由に実装できます。賢明な実装では、チャンクのリストを使用する場合もあれば、トレードオフの異なる他の手法を使用する場合もあります。

すべての状況で、すべてのユーザーにとって、ある手法が別の手法よりも厳密に優れているとは言えません。これが、この規格が実装者に選択の自由を与える理由です。

于 2010-04-02T14:14:43.617 に答える