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

by

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;

More Related Contents:

  1. How do I compare chars (or strings) using void functions, also comparing chars that were taken from a struct array
  2. How to get the maximum number after erasing n digits from the number [closed]
  3. When should you use a class vs a struct in C++?
  4. Is there a performance difference between i++ and ++i in C++?
  5. How to call a parent class function from derived class function?
  6. Is the PIMPL idiom really used in practice?
  7. What is the difference between private and protected members of C++ classes?
  8. How do I combine hash values in C++0x?
  9. Why does the C++ STL not provide any “tree” containers?
  10. How to specialize std::hash::operator() for user-defined type in unordered containers?
  11. How to get the MD5 hash of a file in C++? [closed]
  12. Vectors, structs and std::find
  13. iterate vector, remove certain items as I go
  14. Why can’t a derived class call protected member function in this code?
  15. Choosing between std::map and std::unordered_map [duplicate]
  16. How to hash and compare a pointer-to-member-function?
  17. Implementing multiple interfaces in c++
  18. what is the difference between set and unordered_set in C++?
  19. Diamond inheritance (C++)
  20. overloading base class method in derived class
  21. Efficiency of the STL priority_queue
  22. What is the default hash function used in C++ std::unordered_map?
  23. Hash an arbitrary precision value (boost::multiprecision::cpp_int)
  24. Easiest way of using min priority queue with key update in C++
  25. iterator adapter to iterate just the values in a map?
  26. Convert Lat/Longs to X/Y Co-ordinates
  27. Making a vector of instances of different subclasses
  28. Calculating the info-hash of a torrent file
  29. Calling erase with iterator vs const_iterator
  30. MD5 hash from file in C++

Leave a Comment