programacion - ¿Cómo hacer una búsqueda rápida de un objeto con un valor particular en un vector de estructuras o clases? c++

struct en c++

Question

Si tengo miles de objetos struct o class en un vector, ¿cómo encontrarlos de forma rápida?
Por ejemplo:
Haciendo un juego, y necesito la forma más rápida de detección de colisión. Cada ficha es una estructura, hay muchas fichas en el mapa vectorial, con valores: x e y. Así que, básicamente, lo hago:

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

Entonces, ¿tal vez hay una manera diferente, como punteros inteligentes o algo para buscar objetos particulares más rápido?

Answer 1

Creo que debes profundizar más en la simple búsqueda de un valor dentro de un grupo de struct, aún más si estás planeando buscar entre un número elevado. ¿Cómo se genera la estructura, cómo se recopilan y cómo se hace un seguimiento de ellos, hay una clave común que usted puede usar para ordenar mientras los crea?

Debes enfocarte en ordenarlos mientras lo agregas a toda la estructura, de esa forma evitas ráfagas de computación masivas cada vez que tienes que realizar una búsqueda. Elija un buen algoritmo (por ejemplo, clasificación AVL), de esa manera puede tener una O (log (n))) agregar / eliminar / buscar.

Answer 2

Debe ordenar su vector y luego usar los algoritmos de la biblioteca estándar como binary_search , lower_bound o upper_bound .

Lo anterior le dará una mejor conformidad que o(n) dada al recorrer todo el vector o al usar el algoritmo de búsqueda estándar encontrado .

Answer 3

Por ejemplo:

for_each(v.begin(),v.end(), [](int e)
{
if (e%2==1)//vector elements that are not divided by 2 without remainder
cout<<e<<endl;
});

Answer 4

Un vector es simplemente una colección desordenada de objetos. En realidad, no hay manera de hacer lo que se está preguntando a menos que empiece a ordenar su vector de maneras específicas (por ejemplo, si está ordenado puede saltar al centro del vector y dividir potencialmente el tiempo de búsqueda a la mitad)

Puede ser mejor elegir una estructura de datos diferente (ya sea en lugar del vector o en combinación con él)