Search code examples
c++vectorstructcollision

How to make a fast search for an object with a particular value in a vector of structs or classes? c++

If I have thousands of struct or class objects in a vector, how to find those that are needed, in a fast way?
For example:
Making a game, and I need fastest way of collision detection. Each tile is a struct, there are many tiles in the vector map, with a values: x and y. So basically I do:

For(i=0;i<end of vector list;i++)
{
 //searching if x= 100 and y =200
}

So maybe there is a different way , like smart pointers or something to search for particular objects faster?

Solution

  • You should sort your vector and then use the standard library algorithms like binary_search, lower_bound, or upper_bound.

    The above will give you a better compliexity than o(n) given by walk through of entire vector or by using standard library algorithm find.