Самый быстрый способ проверить, находится ли элемент в обоих векторах

Question

Итак, подумайте, что у нас есть два вектора vec1 и vec2. Каким будет самый быстрый способ только выполнить некоторую операцию с элементами, которые находятся в обоих векторах. До сих пор я это сделал. Просто, как мы можем достичь этого быстрее, и есть ли способ:

vector<Test*> vec1; 
vector<Test*> vec2; 

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them. 


for (Test* test : vec1){ 

    //Check if test is in vec2 
    if (std::find(vec2.begin(), vec2.end(), test) != vec2.end){ 

     //Do some stuff 

    } 

} 

Answer 1

Один простой способ состоит в std::unordered_set

vector<Test*> vec1; 
vector<Test*> vec2; 

//Fill both of the vectors, with vec1 containing all existing 
//objects of Test, and vec2 containing some of them. 
std::unordered_set<Test*> set2(vec2.begin(),vec2.end()); 

for (Test* t : vec1) { 
    //O(1) lookup in hash set 
    if (set2.find(t)!=set2.end()) { 
    //stuff 
    } 
} 

O (N + M), где п число элементов в vec1, м является количество элементов в vec2 }

Answer 2

Ваш подход O (M * N), так как он вызывает std::find линейный по числу элементов vec2 для каждого элемента vec1. Вы можете улучшить его несколькими способами:

• Сортировка vec2 позволит сократить время на O ((N + M) * Log M) - то есть вы можете использовать бинарный поиск по диапазону vec2.begin(), vec2.end()
• Сортировка оба векторов позволит вам искать в O (N Log N + M Log M) - вы можете использовать алгоритм, аналогичный слияние отсортированных диапазонов, чтобы найти совпадающие пары в линейное время
• Использование хэша-набор для vec2 элемент l et, вы сокращаете время до O (N + M) - теперь как время построения набора, так и поиск в нем линейны.