Need help with an Algorithm for non-contiguous Array. Index grouping

Question

I'm need some help writing an algorithm in C/C++ (Although an language example would suffice). The purpose is a container/array, which allows insertion at any index. However if inserting an element in an index that is not close to an existing index i.e. would cause an large empty space of buckets. Then the array minimising the empty buckets.

i.e. You have a set of elements which need to be inserted at the following indexes;

14
54
56
57
12
8
6
5678

A contiguous array would produce a data structure produce something like this

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

However i'm looking for a solution that create a new array when an index is not within x buckets of it's nearest neighbour. e.g.

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 uses some kind of index map to find the array an index is in during a lookup. My question is what kind of algorithm should I be looking at to group the indexes together during inserts? (while still keeping a good space/time trade off)

---

Edit: Thanks for the answers so far. The data i'm going to be looking at will contain one or two very large index ranges with no gaps, then one or two very large gaps then possibly a couple of "straggling" single values. Also the data needs to be sorted, so hash tables are out.

Answer 1

I believe you are looking for a hashmap or more generally a map. You can use the STL provided map class.

This sounds like exactly what you are looking for:

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

Answer 2

Why not just use a hashtable / dictionary? If you really need something this specific, the first thing that comes to mind for me is a B tree. But there's probably much better solutions than that too.

Answer 3

Maybe what you want is a sparse vector? Try the Boost implementation.

Answer 4

You're looking either to use sparse arrays or some sort of hash, depending on circumstances. In general:

1. If you're going to eventually end up with long runs of filled buckets separated by large gaps, then you're better off with a sparse array, as they optimize memory use well in this situation.
2. If you're going to just end up with scattered entries in a huge sea of empty holes, you're better off with a hash.