CODEWITHSUNDEEP
c++performancealgorithmdata-structures
Madz
Madz

Reputation: 1279

Data structure for fast searching in C++

I need to store the values like the following in a data structure,

id   x     y     z
0    0.1   0.1   0.1
1    0.2   0.1   0.6
2    0.01  0.3   0.1
.....

Now I need to match the x,y,z double values and get the corresponding id(int) value. I might need to store around 400000 values. What sot of data structure should I use for efficient searching? Does C++ come with any built-in structures that would support my requirement.

Upvotes: 3

Views: 6544

Answers (4)

Baj Mile
Baj Mile

Reputation: 780

You can use OcTree (http://en.wikipedia.org/wiki/Octree). It would be faster and more convenient than any container in std based on binary tree. Also you would not worry about index or hash functions. However it will take more memory. It can be used even for NN(Nearest Neighbors) search. Another option is the Kd-tree (http://en.wikipedia.org/wiki/K-d_tree). Both are not part of STD. KdTree needs less memory than OcTree and sometimes is even faster. You should be able to find good C++ implementations of OcTree or KdTree with google.

Upvotes: 1

Lie Ryan
Lie Ryan

Reputation: 64837

If you need only to do exact search, then a hash table (unordered_map) would be a good choice. Make the key a tuple or a struct and the value the int id.

If you need to do interval search (e.g. find the element closest to x) and you always search from x,y,z in order, then you'll need an ordered data structure. An ordered tree (map) should work. Use a three levels of nested map so you can do search by doing essentially mymap[x][y][z] with whatever interval rules you want to apply.

If you need a more sophisticated search, where you can start from any elements or search where you only know the latter two elements, then you'll need a multidimensional ordered data structure, which can be used to partition the dimensions world space for logarithmic searching. Some examples are octtree or k-d tree. There is no standard library implementation of an octtree/k-d tree as far as I can tell. There are many variations of this class of data structure, for example, you may use a skiplist instead of a tree.

Upvotes: 1

amit
amit

Reputation: 178421

This is probably come as bad news for you, but I think the best fit for your purpose is the k-d tree, and it is not implemented in the standard library.

This data structure allows you to search the closest neighbor to any given point in multi-dimensional space (3d space in your case). This will guarantee tolerance for rounding errors that are most likely to occur when dealing with floating-point keys.

However, this DS is very popular and I am sure you will be able to find an online implementation of it.

Upvotes: 1

InsertMemeNameHere
InsertMemeNameHere

Reputation: 2433

If you aren't interested in NN search, you can use std::unordered_set. You will need to define your own hash function, however.

Here is an (probably terrible) example:

struct entry
{
    int id;
    double x, y, z;

    // constructor if needed, etc...
};

struct entry_hasher
{
    size_t operator()(const entry &e) const
    {
        std::hash<double> h;
        return h(e.x) ^ (h(e.y) << 1) ^ (h(e.z) << 2);
    }
};

std::unordered_set<entry, entry_hasher> entries;

Otherwise, the standard does not provide containers capable of geometric queries (such as NN).

Upvotes: 2

Related Questions