How to Create a Sparse Array in C++

What is the best way to create a sparse array in C++?

For C++, a map works well. Several million objects won't be a problem. 10 million items took about 4.4 seconds and about 57 meg on my computer.

My test application is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <map>

class triple {
public:
    int x;
    int y;
    int z;
    bool operator<(const triple &other) const {
        if (x < other.x) return true;
        if (other.x < x) return false;
        if (y < other.y) return true;
        if (other.y < y) return false;
        return z < other.z;
    }
};

int main(int, char**)
{
    std::map<triple,int> data;
    triple point;
    int i;

    for (i = 0; i < 10000000; ++i) {
        point.x = rand();
        point.y = rand();
        point.z = rand();
        //printf("%d %d %d %d\n", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}

Now to dynamically choose the number of variables, the easiest solution is to represent index as a string, and then use string as a key for the map. For instance, an item located at [23][55] can be represented via "23,55" string. We can also extend this solution for higher dimensions; such as for three dimensions an arbitrary index will look like "34,45,56". A simple implementation of this technique is as follows:

std::map data<string,int> data;
char ix[100];

sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;

sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;

Sparse array in C++

Items mostly added during initialization step (and not very often after). But access is frequent

In this case boost::container::flat_map can be a good option for you. It is basically just a sorted vector. Advantages (stolen from the website):

• Faster lookup than standard associative containers
• Much faster iteration than standard associative containers
• Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
• Improved cache performance (data is stored in contiguous memory)

A potential drawback:

• Worst case linear-time insertions and linear-time deletions

Even if the worst case happens during insertion or deletion (moving elements of the underlying vector), it is still not that bad thanks to (1) the good use of the cache, (2) relocation of the underlying elements may be vectorized (vector instructions). You would have to try it in your application to see if insertion / deletion is a problem, given your usage pattern.

If flat_map is not suitable for you, I would try std::unordered_map.

How to do sparse array in Cocoa

It sounds like your needs would be better met with an NSMutableDictionary. You will need to wrap the ints into NSNumber objects as follows:

-(void)addItem:(int)key value:(id)obj
{
    [data setObject:obj forKey:[NSNumber numberWithInt:key]];
}

-(id)getItem:(int)key
{
    return [data objectForKey:[NSNumber numberWithInt:key]];
}

There's no easy was to enlarge the size of an NSMutableArray, since you cannot have nil objects in the in-between slots. You can, however, use [NSNull null] as a 'filler' to create the appearance of a sparse array.

Generating a Sparse Matrix in C

Let t be the target number of non-zero elements in the array, which should be much less than the length of the array for sparseness. I'm assuming your array is of length length. I'm also generating the random indices without the modulus operator to avoid modulo bias.

for (i = 0; i < t; ++i) {
   int index = (int) (length * ((double) rand() / (RAND_MAX + 1.0)));
   array[index] = i % 2 ? -1 : 1;
}

Note that this may give a few less than t non-zero elements because random numbers can produce duplicates, but that should be rare if it really is sparse, e.g., t < square root of the array length. If you're worried about duplicate randoms making things sparser than you want, you can modify accordingly:

for (i = 0; i < t;) {
   int index = (int) (length * ((double) rand() / (RAND_MAX + 1.0)));
   if (array[index]) {  /* something already at this index */
      continue;         /* skip incrementing and try again */
   }
   array[index] = i % 2 ? -1 : 1;
   ++i;
}

In both cases I'm alternating +/- ones for the non-zero values, but if you want it more random that would be easy to replace the right-hand side of the assignment of array[index].

Finally, I ask your indulgence if I fluffed something on C syntax. My C is about 15 years rusty, but the intent should be clear.

---

Related Topics