Index-based algorithm design

[Deviouscola]

I was wondering if ya'll could help me out here with improving an algorithm I've developed. The problem I'm trying to address is memory usage while avoiding extra computation as much as possible. I'll be leaving out extraneous details in the interest of brevity. So, try not to ask 'Why?' too much please.

Here is the data structure that the index-based algorithm uses:

const int index_size = 30;    // this is usually set to 25-30ish
unsigned long num_possible_indicies = (1 << index_size);   // 2^30

vector< vector<unsigned int>* > bins;
bins.reserve(num_possible_indicies);

vector<unsigned int> * temp_bin = NULL;

for (unsigned long i = 0; i < num_possible_indicies; ++i)
    bins.push_back(temp_bin);

After initialization only a very small amount of pointers will actually be pointing to a vector (e.g. worst case: ~10,000,000 pointers != NULL ; best case: ~5,000,000 pointers != NULL). Also, the indicies that have non-null pointers are random, essentially.

This 'bin' data structure is analogous to the map container. Essentially, I have number-keys [0, (2^30)-1] mapped to vector-values. It's very nice because it allows for constant-time access of the vectors (plus time for pointer dereferencing, too) and it also takes constant-time to determine whether a key exists (i.e. if ptr == NULL). This algorithm does those things a lot. Moreover, you can probably see why a map container is out of the question - too much memory and it doesn't beat constant-time access.

So, my idea for avoiding the need to create so many null pointers is akin to a hash-function. The input to the function would be the key (i.e. a number [0, (2^30)-1]) that gets converted to an index corresponding to a smaller array that contains the non-null pointers or, say, a negative number that would indicate that the key doesn't exist. I just have no idea how I would go about doing that. But, I guess alternatively I can perform a binary search on a sorted array of the keys that exist.

Hopefully I've made my question clear and I even better if you find it interesting :).

Thanks in advance. Any ideas would be greatly appreciated.

[JLBorges]

Consider using a sparse vector / matrix library.

SparseLib++ http://math.nist.gov/sparselib++/
Boost uBLAS http://www.boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/vector_sparse.htm
and the like.