Как сделать быстрый поиск объекта с определенным значением в векторе структур или классов? C ++

Question

Если у меня есть тысячи объектов struct или class в векторе, как быстро найти нужные объекты?
Например:
Создание игры, и мне нужен самый быстрый способ обнаружения столкновений. Каждая плитка является структурой, в векторной карте есть много плиток со значениями: x и y. Так что в основном я делаю:

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

Так, может быть, есть другой способ, например, умные указатели или что-то для более быстрого поиска определенных объектов?

Answer 1

Я думаю, вам нужно углубиться в более простое исследование значения внутри группы структур, даже больше, если вы планируете поиск среди повышенного числа. Как создаются структуры, как они собираются и как вы их отслеживаете, есть ли общий ключ, который вы можете использовать для заказа при создании?

Вы должны сосредоточиться на сортировке их, пока вы добавляете ее ко всей структуре, таким образом, вы избегаете массивного всплеска вычислений при каждом выполнении поиска. Выберите хороший алгоритм (пример сортировки AVL), чтобы вы могли добавить / удалить / найти O (log (n))).

Answer 2

Вы должны отсортировать ваш вектор и затем использовать стандартные библиотечные алгоритмы, такие как binary_search , lower_bound или upper_bound .

Вышеприведенное даст вам лучшую гибкость, чем o(n), получаемый путем обхода всего вектора или использования стандартного библиотечного алгоритма find .

Answer 3

Например:

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

Вектор - это просто неупорядоченная коллекция объектов.В любом случае, выполнить то, о чем вы просите, не существует, если только вы не начнете сортировать вектор определенным образом (например, если он отсортирован, вы можете перейти к середине вектора и потенциально разделить время поиска пополам)

Возможно, вам лучше выбрать другую структуру данных (либо вместо вектора, либо в сочетании с ним)