二維矢量和矢量地圖有什麼區別？

比方說，我已經聲明二維矢量和矢量地圖有什麼區別？

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

什麼是這兩者之間的相似點和不同點？

來源

2017-10-10 Shaeekh Shuvro

map是一個關聯容器，而vector不是。 –

它們根本不同。雖然您可以同時執行g2[0]和g1[0]，但行爲卻大不相同。假設索引0處沒有任何內容，那麼std::map將默認構造一個新的value_type，在這種情況下是一個向量，並返回一個引用，而std::vector具有未定義的行爲，但通常是段錯誤或返回垃圾。

它們在內存佈局方面也完全不同。儘管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存在。

來源

2017-10-10 09:09:03 midor

請注意，RB樹不是由標準指定的。它依賴於實現，即使在大多數情況下都是如此。 – Caduchon

是真的，但是你知道一個不使用rb-tree的實現嗎？ IIRC標準通常只對某些操作要求某些漸近運行時間，但實際上，內存分配策略對大多數情況下的漸近運行時差異具有更大的影響。 – midor

不，但是有這麼多奇怪的編譯器，如果其中一些實現其他算法（例如卡西歐或德州儀器，已經使用16位字節），我不會感到驚訝。 – Caduchon

的相似性是訪問數據的方式，也可以是相同的語法：

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

的主要區別如下：矢量的地圖沒有包含所有的索引。然後，你可以有，如例子中，只有3地圖中的向量與鍵「17」，「1234」和13579訪問：

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

如果你想與向量的矢量相同的語法，你需要你的主向量中至少有13579個向量（包括13576個空向量）。但是這會在內存中使用很多未使用的空間。

另外，在映射圖，也可以用負密鑰訪問自己的載體（這是不可能以向量爲向量）：

g2[-10].resize(10);

這明顯高差後，數據的存儲是不同。矢量分配連續的內存，而地圖以樹的形式存儲。向量中訪問的複雜度爲O(1)，而在地圖中則爲O(log(n))。我邀請您學習一些關於C++中的容器的教程，以瞭解所有差異以及使用它們的常用方法。

來源

2017-10-10 09:09:49 Caduchon

用例子你可以理解它們之間的區別。假設vector<int>存儲唯一的ID號碼，並且map將各自的PIN碼存儲爲密鑰。

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

顯然，map能夠關聯鍵和值（這裏爲值列表），而vector可以有效地存儲一組數據。

來源

2017-10-10 09:12:23

二維矢量和矢量地圖有什麼區別？

回答

相關問題