2013-04-18 105 views
0

我有一個ID(整數)的列表。 他們是在一個非常有效的方式來分類,使我的應用程序可以輕鬆地處理它們,例如C++索引到索引映射

9382 
297832 
92 
83723 
173934 

(這種是在我的應用非常重要)。

現在我面臨的問題是不得不訪問另一個向量中的ID的某些值。

例如ID 9382的某些值位於someVectorB [30]上。

我一直在使用

const int UNITS_MAX_SIZE = 400000; 

class clsUnitsUnitIDToArrayIndex : public CBaseStructure 
{ 
private: 
    int m_content[UNITS_MAX_SIZE]; 
    long m_size; 
protected: 
    void ProcessTxtLine(string line); 
public: 
    clsUnitsUnitIDToArrayIndex(); 
    int *Content(); 
    long Size(); 
}; 

但現在,我提出UNITS_MAX_SIZE至400.000,我得到頁堆錯誤,並告訴我,我做錯了什麼。我認爲整個方法並不是很好。

如果我想在不同的向量中定位一個ID,如果「位置」不同,應該使用什麼?

ps:我正在尋找一些簡單的東西,可以很容易地從一個文件讀入,也可以很容易地被序列化爲一個文件。這就是爲什麼我以前一直在使用這種蠻力方法。

+2

你可以考慮使用一個std ::向量或std ::地圖'的std ::地圖'? – 2013-04-18 05:31:20

+1

如果您當前的m_content數組超出了會導致您的直接錯誤的堆棧大小,我不會感到驚訝。無論這種方法似乎關閉。你想解決什麼問題? – 2013-04-18 05:34:03

+0

我想保留一個列表,告訴我某個ID位於矢量上的哪個位置。 – tmighty 2013-04-18 05:37:55

回答

3

如果你想從int對廉政局的,你的索引號不連續的映射你應該考慮一個std::map。在這種情況下,您可以這樣定義:

std::map<int, int> m_idLocations; 

映射表示兩種類型之間的映射。第一種類型是「鍵」,用於查找稱爲「值」的第二種類型。每個ID查找你可以將它插入:

m_idLocations[id] = position; 
// or 
m_idLocations.insert(std::pair<int,int>(id, position)); 

你可以使用下面的語法找一找:

m_idLocations[id]; 

通常在STL中std::map使用red-black trees其中有一個worse-實現強制查找O(log n)的速度。這比O(1)稍微慢一點,你會從巨大的數組中獲得,但是它更好地利用了空間,並且除非存儲真正龐大的數字或做了大量的查找工作。

編輯:

在迴應一些評論我想指出的是,距離O移動(1)至O(log n)的可以使你的應用程序的速度顯著差異是非常重要的更不用說將固定的內存塊轉移到基於樹的結構所帶來的實際速度問題。不過,我認爲首先要表達你想說的(int-to-int)映射並避免過早優化的陷阱是很重要的。

當你已經表達了這個概念之後,你應該使用使用探查器來確定速度問題是否以及在哪裏。如果你發現地圖引發了問題,那麼你應該考慮用你認爲更快的東西來替換你的地圖。 請務必測試優化是否有幫助,不要忘記包含關於您所代表的內容以及爲什麼需要更改的重要評論。

+0

2個向量中的值是相同的,但它們是混合的,例如vector1:43,98,11和vector2:98,11,43 – tmighty 2013-04-18 05:46:35

+0

謝謝您的解釋。但是因爲我有這麼多的數據(400.000 * 2個ID對於RAM來說可能真的太多了),我是否應該使用文件映射從文件中獲取數據,然後使用memcopy來檢索值?我的代碼非常龐大,爲了簡單地嘗試,我需要幾個小時,這就是爲什麼我想提前詢問我的方法是否合乎邏輯。 – tmighty 2013-04-18 05:54:47

+1

800,000個id對於對數運算而言相對較小。把它放到透視日誌(800000)〜= 5.903,這在大型計算的規模上很小。複製那麼多的數據會比執行一些地圖查找要慢得多。儘管所有這些取決於你的應用程序如何放在一起。 – 2013-04-18 05:57:16

1

可能是由於int m_content [UNITS_MAX_SIZE]導致的stackoverflow錯誤。該數組在堆棧中分配,而400000是堆棧中相當大的數字。您可以使用std :: vector的,相反,它是動態分配的,你可以返回向量部件的參考,以避免拷貝操作:

std::vector<int> m_content(UNITS_MAX_SIZE); 

const std::vector<int> &clsUnitsUnitIDToArrayIndex::Content() const 
{ 
    return m_content; 
} 
+0

到底動態分配和固定分配有什麼區別,都變成了相同的大小?例如,如果我在向量中真的有400.000個id,則動態分配或立即分配並不重要,是嗎? – tmighty 2013-04-18 05:52:02

+1

@tmighty,固定分配分配在堆棧上,堆棧的大小有限,但動態分配的限制僅限於可用RAM。如果你想使用像這樣的巨大數組,你可以通過使用像std :: vector這樣的標準容器來避免stackoverflow的問題,或者你可以在關鍵字new的堆上定義你的數組 – 2013-04-18 05:55:30

+0

你能告訴我怎樣才能從那裏訪問vector外?我的「int * Content();」已過時。我想你錯了。它不應該是「std :: vector m_content();」 ? – tmighty 2013-04-18 06:39:34

1

如果沒有其他的工作,你可以在構造函數中動態分配數組。這將移動堆上的大數組並避免頁堆棧錯誤。你應該還記得釋放資源,而毀了自己的clsUnitsUnitIDToArrayIndex

不過是由其他成員提出的建議用量,使用