需要關於非連續陣列算法的幫助。索引分組

Question

我需要一些幫助在C/C++中編寫算法（儘管語言示例就足夠了）。目的是一個容器/數組，允許在任何索引處插入。但是，如果在索引中插入一個不接近現有索引的元素，即會導致大量的存儲空間。然後數組最小化空桶。

即你有一組元素需要在以下索引處插入;

14 
54 
56 
57 
12 
8 
6 
5678 

一個連續的數組會產生一個數據結構產生這樣的

0 
1 
2 
3 
4 
5 
6 val 
7 
8 val 
9 
10 
11 
12 val 
...etc 

但是我正在尋找的是創建一個新的陣列的解決方案時的指數是不是X水桶內的它的最近鄰居。 例如

Array1 
6 val 
7 
8 val 
10 
11 
12 val 
13 
14 val 

Array2 
54 val 
56 val 
57 val 

Array 3 
5678 val 

然後使用某種索引映射查找查找過程中索引所處的數組。我的問題是，我應該在插入期間將索引分組到一起使用哪種算法？ （同時仍保持了良好的空間/時間權衡）

---

編輯： 感謝迄今答案。我要查看的數據將包含一個或兩個非常大的索引範圍，沒有空白，然後有一個或兩個非常大的空白，然後可能會有幾個「零散」單個值。此外，數據需要排序，所以散列表已經不存在。

Answer 1

我相信你正在尋找一個hashmap或更一般的地圖。你可以使用STL提供的地圖類。

這聽起來像正是你在找什麼：

http://www.cplusplus.com/reference/stl/map/

Answer 2

爲什麼不直接使用一個哈希表/字典？如果你真的需要這個特定的東西，我想到的第一件事情是B tree.但是也可能有比這更好的解決方案。

Answer 3

也許你想要的是一個稀疏矢量？試試Boost implementation。

Answer 4

根據具體情況，您正在尋找使用稀疏數組還是某種散列。一般來說：

1. 如果你要最終與大的間隙分開充滿桶的長期運行結束，那麼你就要去用一個稀疏數組更好，因爲他們優化內存在這種情況下，用得好。
2. 如果你打算在一個空洞的大海中散落一些條目，你最好用散列表。