Need help with algorithm for non-contiguous array. Index Grouping

Question

I need help writing an algorithm in C / C ++ (although an example language would be sufficient). The goal is a container / array that allows you to insert any index. However, if you insert an element into an index that is not close to an existing index, it will result in a large empty space of buckets. Then the array minimizes empty buckets.

i.e. You have a set of elements to insert into the following indexes:

14 54 56 57 12 8 6 5678 

The adjacent array will create a data structure that creates something like this.

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

However, I am looking for a solution that creates a new array when the index is not in x buckets of the nearest neighbor. eg.

 Array1 6 val 7 8 val 10 11 12 val 13 14 val Array2 54 val 56 val 57 val Array 3 5678 val 

Then it uses some index map to find the array in which the index is located during the search. My question is, what algorithm should I look for to group indexes together during insertions? (while maintaining good space / time savings)

---

Edit: Thanks for the answers. The data that I will look at will contain one or two very large ranges of indices without spaces, then one or two very large ranges, and then, perhaps, a couple of "scattered" single values. Also, the data must be sorted, so there are no hash tables.

Answer 1

Perhaps what you want is a sparse vector? Try the boost implementation .

Answer 2

Why not just use a hash table / dictionary? If you really need something specific, the first thing that comes to my mind is B tree. But there are probably much better solutions than this, too.

Answer 3

You are looking to either use sparse arrays, or some kind of hash, as the case may be. Generally:

• If you end up with long runs of filled buckets separated by large spaces, then you will be better off with a sparse array, as they optimize memory in this situation.
• If you are going to just scatter records in a huge sea of ​​empty holes, you will be better off with a hash.

Answer 4

I believe that you are looking for a hash map or a more general map. You can use the map class provided by STL.

This is similar to what you are looking for:

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