c++ - ポインターをデータ構造にすることはできますか?

Question

ポインタは効率的でセマンティックなデータ構造と見なすことができますか? リンクされたリスト、ハッシュ、キュー、スタックに対してどのようにスタックアップできますか?

Answer 1

いいえ、ポインターは単なる型であり、構造体ではありません。std::vector型 ( 、std::map、...) である構造体の実装がありますが、ポインターはそうではありません。

これらは、列挙した構造体の実装で内部的に一般的に使用されますが、ポインター自体は構造体ではありません。

Answer 2

ポインターはデータ型であり、データ構造ではありません (用語がかなり緩い本では、ポインターなどの基本的な型をより大きなデータ構造セットの要素として定義していますが、ポインターは確かに抽象的なデータ構造の例ではありません。 .)

さらに適切なことに、リンクされたリスト、キュー、スタック、ツリーなどの抽象データ構造のほとんどの C++ 実装では、データメンバーとしてポインターが使用されます。つまり、ポインタは実装の一部を形成します。それらは実装そのものではありません。

例として、独自のリンク リストの実装を考えている場合は、リスト内の各要素が前後のノードへのポインターを含むノードによって表される、二重リンク バージョンを使用することを選択できます。

template <typename T>
class DLList
{
public:
    // Lots of things
private:
    Node* _head; // Pointer to the head of the list
    Node* _tail; // Pointer to the tail of the list
};

ノードは次のように実装できます。

template <typename T>
struct Node {
    Node* _prev;
    Node* _next;
    T     _data;
};

Answer 3

データ構造とは、効率的に使用できるようにデータをコンピュータに格納および編成する特定の方法です。ポインタは、データを格納および整理するための非常に効率的な方法であり、最近ではメモリをアドレス指定する主要な方法です。ただし、これが唯一の方法ではありません。たとえば、CPU レジスタのアドレス指定は異なります。したがって、最初の質問に対する答えはイエスです。

2 番目の質問については、ポインターをハッシュ、キュー、スタックなどの高レベルのデータ構造と実際に比較することはできません。これらは、2 つの異なるレベルの抽象化です。高レベルのコンテナーは、ポインターなどの低レベルのデータ構造を使用して実装されます。