中間ロックを持つDequeのリスト

Question

要素間に中間ロックエンティティを持つデータ構造を設計したいと思います。これらのロックは、隣接する2つの要素に共通です。 （i）はB（i）とB（i + 1）によって制御される要素への要素の追加が行われていない場合にのみ使用されます。 Eを分割することができます。 B（i + 1）を除去してE（i）とE（i + 1）をマージしてE（i）を形成することができる。 Eの除去は禁止されています。

これはC++で最良のデータ構造になります。

Answer 1

標準ライブラリには、異種のデータ構造を持っていません。 3つのアプローチがあります：自分で実装する、タグ付きの共用体型のオブジェクトを含む均質な構造を使用する、または2つの並列構造を使用する。

異質リストの最低限の例：

template<class T,class E> 
struct node; 

template<class T, class E> 
struct edge { 
    node<T, E> *prev, *next; 
    E data; 
}; 

template<class T, class E> 
struct node { 
    edge<T, E> *prev, *next; 
    T data; 
}; 

template<class T, class E> 
struct fancy_list { 
    edge<T, E> *head, *tail; 
}; 

struct wagon { 
    // wagon members 
}; 
struct boundary { 
    // boundary members 
}; 

int main() { 
    fancy_list<wagon, boundary> wagons; 
} 

アルゴリズムは、均質なリストのためのアルゴリズムとして、ほとんど同じように動作しますが、ノードの除去に対処するための戦略を策定する必要がありますが（1です既存のエッジメンバーを新しいエッジメンバーにコピーするか、デフォルトのステートを設定するかなど）などがあります。「右」または「右」はありません。最良の "ソリューションを提供します。

---

タグ付きユニオン実装std::variantは、C++ 17で導入されます。それまでは、自分で実装するか、サードパーティに依存する必要があります。

このアプローチの問題点は、データ構造が本質的にノードとノードだけに隣接するエッジの不変量を隣接するエッジのみに強制することではないため、あなた自身のアルゴリズムを実装する必要があることです。

---

エッジとノードの並列構造は、グラフを実装する典型的な方法です。あなたのリストは、各ノードのちょうど2つのエッジを持つ特別なグラフのケースです。