2次元ベクトルとベクトルのマップの違いは何ですか？

Question

のは、私が

map< int , vector<int> > g1; 
vector< vector<int> > g2; 

これら二つの間の類似点と相違点は何ですか

を宣言したとしましょうか？

Answer 1

これらは基本的に異なります。 g2[0]とg1[0]の両方を実行できますが、動作は大きく異なります。インデックス0に何もないと仮定すると、std::mapはデフォルトで新しいvalue_type（この場合はベクトル）を構築して参照を返しますが、std::vectorには未定義の動作がありますが、通常はsegfaultsまたはgarbageを返します。

また、メモリレイアウトも全く異なります。 std::mapは赤黒の木で裏打ちされていますが、std::vectorはメモリ内で連続しています。したがって、マップに挿入すると常にメモリのどこかに動的割り当てが行われますが、現在の容量を超えた場合にはベクトルのサイズが変更されます。ただし、ベクトルのベクトルはメモリ内で連続していないことに注意してください。

struct vector 
{ 
    T* data; 
    size_t capacity; 
    size_t size; 
}; 

ベクトルの各々はdataにおけるその動的メモリ割り当てを所有している：それ自体がメモリに連続している最初のベクトルが、データの点で概ね次のようになりベクトルから構成されています。

マップの利点は、つまりあなたが間にあるすべてのものなしのインデックス0と12902で何かを持つことができる人口が密集する必要はありませんであり、それに加えてソートされます。ソートされたプロパティを必要とせず、C++ 11を使用できる場合は、std::unordered_mapを検討してください。ベクトルは常に密集しています。つまり、サイズ10000、要素0-9999が存在します。

Answer 2

類似性は、あなたがデータにアクセスする方法です、それは同じ構文になります

std::cout << g1[3][2] << std::endl; 
std::cout << g2[3][2] << std::endl; 

主な違いは以下の通りです：ベクターのマップは、すべてのインデックスが含まれている必要はありません。あなたはベクトルのベクトルと同じ構文をしたい場合は、必要に

g2[17].resize(10); 
g2[1234].resize(5); 
g2[13579].resize(100); 

：次に、あなたは、一例として、キー「17」、「1234」と13579でアクセスマップ内のみ3のベクトルを持つことができますあなたのメインベクトルに少なくとも13579個のベクトル（13576個の空のベクトルを含む）を持っています。しかし、これはメモリ内の多くの未使用領域を使用します。

また、あなたのマップで、あなたも（ベクトルのベクトルでは不可能である）負のキーを使用してベクトルにアクセスすることができます。

g2[-10].resize(10); 

この明らかに高い相違した後、データの保存が異なっています。ベクトルは連続したメモリを割り当て、マップはツリーとして格納されます。ベクトル内のアクセスの複雑さはO(1)ですが、マップ内ではO(log(n))です。私はあなたにC++でのコンテナに関するいくつかのチュートリアルを学び、相違点とそれを使う普通の方法を理解することを勧めます。

Answer 3

例では、その違いを理解することができます。人々のvector<int>店舗固有のID、およびmap格納し、キーとしてそれぞれのPINコードを言うことができます。vectorを効率的にデータの束を格納することができるしながら

map< int , vector<int> > listOfPeopleAtRespectivePinCode; 
vector< vector<int> > bunchOfGroupsOfPeople; 

は明らかに、mapは、（ここでの値のリスト）キーと値を関連付けることが可能です。