0

非常に特殊なアプリケーションの場合、可変サイズの要素とメモリ内で連続するコンテナを使用したいと考えています。理論的根拠は、アクセスはほとんどシーケンシャルであるため、すべてのデータを同じ線形データ構造にすると、キャッシュ動作に役立つはずです。

もちろんランダム アクセスは不可能ですが、データ構造はベクトル スタイルのpush_back方法で動的にサイズ変更する必要があります。

このようなコンテナは存在しますか？それはどのように呼ばれますか？

Arne Mertz のコメントに対処するために編集します。

表現したい構造はグラフです。コンテナーにはノードのリストが含まれ、ノードごとにエッジのリストが含まれます。おそらく、他の (前の) ノードへのポインターのリストとして表されます。

struct Node {
  //various fixed size fields about the node itself
  ...

  unsigned short n_edges;
  Node * edges[n_edges]; // schematically
};
4

4 に答える 4

1

これを解決する 1 つの方法は、内部 void ポインターを使用することです。次に、各要素がそのメモリに格納されます。各要素はそのサイズから始まります。コンテナーを反復処理すると、現在の要素のサイズだけバイト ポインターがインクリメントされます。ランダム アクセスが必要な場合は、すべての要素へのポインターを含むディレクトリを使用できます。

于 2013-06-19T09:03:58.177 に答える
1

Boost Intrusive singlelylinked listはどうですか。独自の割り当てを自分で実装する必要があります。単純に大きな領域 (char[] 型) を割り当て、この領域内にアドレスを増やしてオブジェクトを作成することができます (整列を忘れないでください)。エリアがいっぱいの場合は、別のエリアを簡単に作成できます。ただし、すべての割り当てを自分で行い、オブジェクトの有効期間を管理する必要があります。さらにstd::vector、O(1) アクセスのサポート構造として を使用できます。

于 2013-06-19T09:05:07.260 に答える
1

std::vector<char> vと組み合わせた を作成できますstd::list<size_t> l。v拡張可能な char バッファーとして機能しl、オブジェクトへのオフセットが含まれます。

次に、現在のオフセットを std::list に挿入し、オブジェクトを &v[offset] の場所にコピーする独自の push_back を作成する必要があります (事前に v を増やすことを忘れないでください)。

template <class T>
void push_back(T t)
{
    size_t vectorSize = v.size());
    size_t objectSize = sizeof(T);

    l.pushback(vectorSize);

    v.reserve(vectorSize + objectSize);
    st::memcpy(&v[vectorSize], &t, objectSize);
}
于 2013-06-19T09:02:09.460 に答える