如何使用未知（int-like）類型作爲std :: vector的索引？

我使用類型Id其在我正在使用的代碼的另一部分來定義：如何使用未知（int-like）類型作爲std :: vector的索引？

typedef int Id;

現在我提供許多對象，其每一個都帶有這樣的Id，我想使用Id作爲存儲這些對象的std::vector的索引。它可能是這個樣子：

std::vector<SomeObj*> vec(size); 
std::pair<Id, SomeObj*> p = GetNext(); 
vec[p.first] = p.second;

的問題是，std::vector使用自己的類型索引其內容：（？爲什麼不是模板）std::vector::size_type。

嚴格來說，使用std::map<Id, SomObj*>會更好，但效率會更低，並且我在這裏確實需要一個數組（我知道所有對象的索引都是連續的，並以0開頭）。另一個問題是，typedef int Id可能在未來變成typedef long int Id或類似的...（這是我自己的代碼的一部分，但我控制它，但理想情況下，我應該允許在某些點更改typedef;這是一個什麼typedef是）。

你會如何處理這個問題？也許使用unordered_map<Id, SomeObj*>，其中散列函數直接使用Id作爲散列鍵？這會降低內存效率嗎？（我並不完全理解unordered_map是如何分配空間的，因爲散列函數的範圍事先是未知的？）

來源

2010-09-22 Frank

您錯過了最後一段中的反引號。 – mkb 2010-09-22 15:25:40

好的，謝謝，修正。 – Frank 2010-09-22 15:26:40

您可以傳遞任何整數類型作爲std::vector的索引。如果它不匹配std::vector<T>::size_type（通常是unsigned long），則該值將被隱式轉換。

來源

2010-09-22 15:26:27

我90％確定'vector :: size_type' *不是* unsigned long'。相反，它幾乎總是一個「std :: size_t」，在某些計算機上它是「long」的兩倍。 – 2010-09-22 15:30:08

是的，'size_type'可能是'size_t'。但是，這通常是'unsigned long'。它在我的64位Linux系統上使用gcc，在我的32位Windows系統上。 – 2010-09-22 15:36:53

64位Windows是非典型的，因爲它是LLP64，而64位Linux是LP64。 – 2010-09-22 15:49:03

編寫您自己的容器包裝，將Id作爲索引類型。在內部使用map或unordered_map來實現容器。對這個包裝程序進行編程。如果事實證明這個實現太慢，請在內部切換到vector，並將Id索引轉換爲vector::size_type（當然也在內部）。

這是最乾淨的方法。但實際上，vector::size_type將是一些非常大的無符號整數類型，因此從Id到vector::size_type的轉換將始終是安全的（但不是相反！）。

來源

2010-09-22 15:27:10

爲什麼不是這樣的模板？

因爲標準容器被實現爲使用它們合理可以使用的最大的無符號類型。如果size_type在你的實現中是unsigned int，那麼這是有原因的，無論原因是什麼阻止了實現者使用更大類型，如果你要求其他東西[*]，它仍然存在。另外，對於您的特定示例，大小類型必須是未簽名的，並且您希望使用簽名類型，這是支持您想要執行的操作所需的另一個更改。

實際上，標準容器的size_type（幾乎？）總是size_t。所以如果你要求一個更大的矢量，你不可能有一個矢量，因爲矢量是由連續的存儲支持的。該向量將無法分配大於size_t字節的數組。

要使用Id作爲向量索引，您可以依靠隱式轉換，也可以顯式轉換（也可能是顯式限制檢查），以使其完全清楚您正在執行的操作。您還可以使用斷言來確保Id不大於size_type。像這樣的東西，雖然靜態斷言可能會更好：

assert(std::numeric_limits<Id>::max() <= std::numeric_limits<std::vector<SomeObj*>::size_type>::max());

一個map<Id, SomeObj*>將是一個很好的選擇，如果在使用中的ID值是稀疏。如果唯一有效的ID是1和400,000,000，那麼一個向量將會浪費內存。

如果它讓你感覺更舒適，請記住字面值0的類型爲int，而不是vector<SomeObj*>::size_type。大多數人對寫作vec[0]毫無疑問：確實在標準中使用。

[*]即使這個原因是正義的，「實施者認爲40億元素對任何人都是足夠的」。

來源

2010-09-22 15:37:45

問題是，Id是一個int（更確切地說，signed int），可以是負數。如果Id是無符號類型，例如typedef unsigned int Id;，沒有問題。

如果我的理解是正確的，那麼我不明白爲什麼有人想要使用負數作爲vector（或array）的索引。我錯過了什麼？

來源

2010-09-22 16:13:14 Arun

如何使用未知（int-like）類型作爲std :: vector的索引？

回答

相關問題