c++ - C++ std::map と std::vector の利点は?

Question

週末にプログラミング コンテストに参加する予定ですが、std::vector と std::map のどちらを使用すればよいですか? それらを単に配列として使用しますが、どちらが優れているか混乱しています(主に基本操作の速度)?

私はこの写真をstackoverflowで見ましたが、これらの主な違いはどれかわかりません...

写真は、ベクトルの方が速いことを示唆しています...どうすればよいか本当にわかりません。助けてください！配列のようにのみ使用する必要がありますが、動的サイズで使用する必要があります...よろしくお願いします。

編集 私はおそらく整数の2D配列を取得します（たとえば、都市や迷宮の地図で、グラフアルゴリズムまたは動的プログラミングで解決できるある種の問題が与えられるでしょう）ので、必要なものは: 「テーブル」の特定のセルの書き込み、読み取り、特定の値の検索、それだけだと思います。std::map はメモリ内の完全な N*M サイズのテーブルを見つけられないと聞きましたが、値ごとに実行します...メモリ使用量が少ないというのは本当ですか?

ばかげて申し訳ありませんが、私が知っていることすべてを学んだ本当の教師はいません。データ構造 (2-3 木、赤黒木、二項ヒープなど...) について学び始めたところです。

Answer 1

std::vector使うべきか、使うべきか知りたいのですがstd::map？

それはあなたが何をしたい/何をする必要があるかに完全に依存します。ユーザーから2つの数値を入力し、それらを追加して結果を表示する必要がある場合は、ベクトルやマップを使用しても意味がありません。

ただし、オブジェクト（またはプリミティブ）の配列を格納する必要がある場合std::vectorは、通常、これが最適な方法です。キーと値の保存が必要な場合は、それstd::mapが発明されたものです。あなたが尋ねた質問は広すぎるので、それに答えるのは実際には非常に難しいですが、それでもあなたはその考えを理解するかもしれません。

また、ここで複製しようとしてはいけないコードについてのインスピレーションを得ることができます。

Answer 2

std::map は配列ではなく、赤黒二分木です。したがって、基本的な配列ストレージとしては適切な選択ではありません。

std::vector は配列として使用でき、配列と同様のアクセス速度が得られる可能性があります (実装に依存する場合がありますが、ほとんどが配列として実装されるわけではありません)。std::vector の利点は速度ではなく、メモリを管理することです。

また、さまざまなデータ構造について読みたいと思うかもしれません。プログラミングスキルの幅を広げるのに役立ちます。

Answer 3

文字配列のCの意味での配列、または数学の意味での配列を意味しますか？配列は多次元になりますか？

数学的な種類を意味する場合は、ヒープ内でmallocされ、新しい、より大きなmallocに続いてメモリコピーを実行し、古いmalloc領域を解放することでサイズを変更した配列を、std：containersを使用するよりも高速に格納できる場合があります。

stdに騙されないでください。コンストラクターは、必要なものをスペース単位で割り当てるように聞こえます。彼らはコンストラクター時にあまりにも多くのスペースをmallocするので、これがなければ彼らがそうするかもしれないほど頻繁に成長する必要はありません。彼らが成長しなければならないとき、彼らは再びまったく同じ理由で再び余分なスペースを要求します。スペースを拡張する必要がある場合は、可能な限り最大のデータ項目を使用してデータを移動することを忘れないでください。64ビットバスがあり、charが一度に1つずつ移動し、コンパイラがこれを最適化するほど賢くないと仮定すると、1/64のlongはNバイトよりも速く移動します。