C++ベクタの実装 - 要素を削除する

Question

私はベクトル型を実装しています。私はアルゴリズムやデータ構造に全く悩まされていませんが、私はremoveメソッドについてはわかりません。

bool Remove(Node* node) 
{ 
/* rearrange all the links and extract the node */ 

delete node; 
} 

ここで、nodeは、現在のノードへのポインタです。しかし、私はノードを削除した場合、その後どのように私はこのようなことが起こらないでください：currentNodeのは、それが容易になるだろうポインタへのポインタであったが...場合

Node* currentNode = MoveToRandNode(); 
Remove(currentNode); 
cout << currentNode->value; 

そうではありません。

Answer 1

最初に戻る。ベクトルが指すメモリを "所有する"人を定義する必要があります。それはベクトルそのものか、またはそのベクトルを使用するコードですか？これを定義すると、答えは簡単になります。Remove（）メソッドは常にそれを削除するか、決して削除しないでください。あなたはベクトルをコピーする場合は、あなたがする必要がありますか

• ：あなたはバグの可能性の表面をちょうど傷きたし、あなたが「それを所有している人」のような他の可能性のある問題を助けるために答える

  注意（例えば、浅いコピーや深いコピーを行うなど）

• ベクターを破壊するときは、その中のアイテムを破壊する必要がありますか？
• アイテムを挿入するときは、アイテム、またはベクトルが所有権を取得していますか？

Answer 2

まあ、できませんが、コードを変更すると安全性が向上します。 はnullptr

if(currentNode) 
    cout << currentNode->value; 

のための参照

bool Remove(Node*& node) 
{ 
/* rearrange all the links and extract the node */ 

delete node; 
node = nullptr; 
} 

チェックおそらくあなたがSTDをしようとする必要があります:: shared_ptrの

Answer 3

これは "イテレータの無効化" に似ているを追加します。たとえば、std::list lとそのリストを指しているstd::list::iterator itがあり、l.erase(it)を呼び出した場合、イテレータitは無効になります。つまり、何らかの方法で使用すると、未定義の動作が発生します。

したがって、その例の次の行に沿ってRemoveメソッドをドキュメントに含める必要があります。 "ポインタnodeは無効になり、このメソッドが返された後に参照または参照解除されない可能性があります。

（。もちろん、あなたもちょうどホイールを再発明する気にはstd ::リストを使用して、ことができませんでした）

をイテレータの無効化の詳細情報については、以下を参照してください。またhttp://www.angelikalanger.com/Conferences/Slides/CppInvalidIterators-DevConnections-2002.pdf

Answer 4

何innochentiが書いた。 私はあなたがcout << currentNode->value;の期待されているものを/希望の動作を決定する必要がありますと思う：

• エラー - （innochentiがnode = nullptrを書いたように）
• デフォルト値 - （そのvalueのためのいくつかのデフォルト値を持つ）ノードdevault_valueを作成し、そしてdelete node;後にあなたは生のポインタを処理していない場合 （今生のポインタである）あなたのイテレータに抽象化の別のレベルを追加しますが、私のいくつかの並べ替えを作成することができnode=default_value

Answer 5

を行いますポインタの代わりにteratorクラスを使用すると、イテレータを無効にすることができ、削除された後に誰かがイテレータにアクセスしようとすると制御が失敗する可能性があります。

もちろん、このポインタの折り返しは、ある程度のオーバーヘッドがかかります（各逆参照のポインタを確認してください）。だから、あなたはどれくらい安全にプレイしたいのかを決める必要があります。他の人が提案したように文書化するか、安全のために折り返す。