C++ ベクトルを使用して、スタック、キュー、ヒープ、プライオリティ キュー、有向加重グラフを実装しました。書籍や参考文献で、これらのデータ構造の大きなクラスを見てきましたが、それらはすべてベクトルを使用して簡単に実装できます。(ポインタの使用により柔軟性があるかもしれません)
vector を使用して高度なデータ構造を実装することはできますか?
はいの場合、なぜ C++ の本はポインターを使用して長いクラスの概念を説明しているのですか?
その方がより鮮やかな場合、または学生にそのようなポインターの使用法を身に付ける場合は、より低いレベルのアイデアを心に留めておくためですか?
多くのデータ構造をベクトル（この回答のために配列）の上に実装できることは事実です。すべての計算タスクを実装して、はるかに多くの機能を持つチューリングマシンで実行できるため、基本的にすべてのデータ構造を実装できます。基本的なデータ アクセス機能 (または、現実の世界では、ポインターを使用して実装するプログラムは、最終的に単純な配列のような仮想メモリ空間を持つ CPU 上で実行されると言うかもしれません。そのため、それを単に巨大な配列と呼ぶことができます)。ただし、常に賢いとは限りません。2 つの主な理由:
パフォーマンス/時間の複雑さ - ベクトルは、O(1) ですべての基本的な操作を提供することはできません。初期化を高速化するための解決策がありますが、値を大きなベクトルにランダムに挿入してみて、パフォーマンスがどれほど悪いかを確認してください。これは、すべての要素を 1 か所ずつ何度も移動する必要があるためです。リストは、1 回の操作でそれを行うことができます。もちろん、他の構造にも独自のパフォーマンス上の欠点がありますが、それは、これらの基本的なビルディング ブロックを使用して複雑なデータ構造を設計する利点です。
構造の複雑さ - ベクトルの同じ行に沿ったリストを順序付けられたコンテナと考えることができ、おそらくこれを多次元行列に拡張して、基本的な順序を保持しているため、それらの上に実装できますが、より複雑な構造があります. たとえば、ツリーを例にとると、単純な完全バイナリ ツリーは、親子関係をインデックス演算に簡単に変換できるため、ベクトルを使用して非常に簡単に実装できますが、ツリーが完全ではなく、1 つあたりの子の数が異なる場合はどうなるでしょうか。ノード？今でも、それは可能だと言うかもしれません (任意のグラフは、隣接行列または隣接リストなどを介してベクトルで実装できます)。配列で AVL ロールを行うことを考えてみてください。:身震い:
2 番目の引数はパフォーマンスに帰結する可能性があることに注意してください (「これは厄介なアプローチですが、それでもベクトルを使用することができました!」)。しかし、それ以上のものです。コードが複雑になり、データ構造の設計が乱雑になります。 、バグが発生しやすくなる可能性があります。
さて、ここで「しかし」が来ます。言語が提供するすべての可能なツールを使用することには多くの意味がありますが、パフォーマンスが重要なタスクにベクトルベースの構造を使用することは非常に広く受け入れられています。ほぼすべての科学的 CPU ベンチマークを参照してください。それらのほとんどは最終的にベクトルに依存しています (引用されていませんが、興味のある人がいる場合はさらに詳しく説明できます。よく知られている *グラフ*500 でさえそうです)。
その理由は、それがプログラミングのベスト プラクティスだからではなく、CPU の内部構造により適していて、HW からより多くの「ジュース」を引き出すためです。これは空間的局所性によるものです - CPU は、メモリユニットがアクセスを並列化できるようにするため、非常に気に入っています (配列では次の要素がどこにあるかを常に知っており、リストでは現在の要素がフェッチされるまで待機する必要があります)。将来のリクエストのレイテンシを短縮するストリーム/ストライド プリフェッチを発行します。これが常に良い習慣であるとは言えません。グラフを実行すると、配列の実装を使用してもアクセスは依然としてかなり不規則ですが、それでも非常に一般的な方法です。
要約すると、質問を文字通りに解釈すると、ほとんどの場合、ある種の可能性があります (「ほとんど」の特定の定義については、わかりましたか?)。制限と、使用できるものと使用する必要があるもの - 配列やポインターだけでなく、さらに多くのことを知る必要があります。優れたプログラマーは、OS 設計、CPU 設計など、すべてについて少し知っている必要があります。実行しているファブリックを本当に理解していない限り、適切なことは何もできません。残念ながら (またはそうではない)、多くのポインターが含まれています。