Search in a large vector in C ++

Question

I have the following vectors:

std::vector<A*> vec; std::vector<std::pair<A*, A*>> vec_pair; 

The size of vec_pair is much larger than the size of vec. I would like to find a pair inside vec_pair in which both members are inside vec.

vec_pair content is persistent. However, after each iteration, the contents of vec will change and I would like to run the test again.

I know that I can do a for loop and check. However, given the difference in size and job repeatability , I am looking for a smart and effective way to do this.

Answer 1

If you are not going to modify the contents of vec , create std::unordered_set<A*> with the same contents and find the entries there. A search in unordered_set roughly O (1), so this will be a simple win.

The easiest and most efficient way to build an unordered_set from vector is to use a constructor with two iterators:

 unordered_set<A*> us(vec.begin(), vec.end()); 

Answer 2

vec_pair size is much larger than vec .

This must be the key to use std::map . Place all elements of the vec vector inside the map: myMap[vec[i]] = 1; Then go through each pair in vec_pair and do

 if (myMap.find(vec_pair[i].first != myMap.end()) && myMap.find(vec_pair[i].second != myMap.end()) ) { return FOUND; } else return NOT_FOUND;` 

As Gates commented, use unordered_map for faster operations.

Answer 3

You can use unordered_set (you don't need a map ) which allows O(1) to search and insert.

1) From vec you create unordered_set<A*> S;

2) For each pair in vec_pair you can check if both elements are present in S

Something like the following will do the job on average O(vec_pair.size())

 std::vector<A*> vec; std::vector<std::pair<A*, A*>> vec_pair; unordered_set<A*> S; for(auto a: vec) S.insert(a); for(auto p : vec_pair){ if(s.find(p.first)!=S.end() && s.find(p.second)!=S.end()) { //PAIR GOOD }else{ //THIS PAIR IS NOT GOOD } } 

Answer 4

I do not know your requirements exactly, but if the order of the element in vec_pair not important, I suppose you can replace it with std::multimap or, I suppose, better, std::unordered_multimap .

I mean (using example A , equal to int as an example), instead

  using A = int; std::vector<std::pair<A, A>> const vec_pair { {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {4, 1}, {4, 2}, {4, 3}, {4, 4} }; 

you can use

  std::unordered_multimap<A, A> const cM { {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {4, 1}, {4, 2}, {4, 3}, {4, 4} }; 

If you want vec_pair be a vector of pairs, using the fact that vec_pair is a constant (I understand correctly?), You can create a constant unordered multimar.

The advantage of this solution is that if you find that the card key is not in vec , you can avoid the test for all values ​​with the same key.

Additionally: if you build a set (or, better, unordered_set ) starting with vec (this is not enough, if I understand correctly, you can check the pairs as follows

  for ( auto ci = cM.cbegin() ; ci != cM.cend() ; ) { auto val = ci->first; auto cnt = cM.count(val); if ( s.end() == s.find(val) ) { for ( auto i = 0U ; i < cnt ; ++i ) ++ci; } else for ( auto i = 0U ; i < cnt ; ++i, ++ci ) if ( s.end() != s.find(ci->second) ) std::cout << "- good for <" << val << ", " << ci->second << '>' << std::endl; } 

I know: this is not an elegant solution.

Another way is to use a combination of map and set (unorderd, better) and instead

  std::vector<std::pair<A, A>> const vec_pair { {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {4, 1}, {4, 2}, {4, 3}, {4, 4} }; 

use (or construct)

  std::unordered_map<A, std::unordered_set<A>> const cM { {1, {1, 2, 3, 4}}, {2, {1, 2, 3, 4}}, {3, {1, 2, 3, 4}}, {4, {1, 2, 3, 4}} }; 

In this case, the search part is more elegant (IMHO)

  for ( auto const & p : cM2 ) if ( s.end() != s.find(p.first) ) for ( auto const & sec : p.second ) if ( s.end() != s.find(sec) ) std::cout << "- good for <" << p.first << ", " << sec << '>' << std::endl; 

Below is a complete compiled example for both solutions

 #include <vector> #include <utility> #include <iostream> #include <unordered_map> #include <unordered_set> int main() { using A = int; std::unordered_multimap<A, A> const cM { {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {4, 1}, {4, 2}, {4, 3}, {4, 4} }; std::unordered_set<A> s { 4, 3 }; for ( auto ci = cM.cbegin() ; ci != cM.cend() ; ) { auto val = ci->first; auto cnt = cM.count(val); if ( s.end() == s.find(val) ) { for ( auto i = 0U ; i < cnt ; ++i ) ++ci; } else for ( auto i = 0U ; i < cnt ; ++i, ++ci ) if ( s.end() != s.find(ci->second) ) std::cout << "- good for <" << val << ", " << ci->second << '>' << std::endl; } std::unordered_map<A, std::unordered_set<A>> const cM2 { {1, {1, 2, 3, 4}}, {2, {1, 2, 3, 4}}, {3, {1, 2, 3, 4}}, {4, {1, 2, 3, 4}} }; for ( auto const & p : cM2 ) if ( s.end() != s.find(p.first) ) for ( auto const & sec : p.second ) if ( s.end() != s.find(sec) ) std::cout << "- good for <" << p.first << ", " << sec << '>' << std::endl; } 

Answer 5

How much less vec than vec_pair? Is the vec size square much smaller than vec_pair? If so, you do unordered_set from vec_pair, and then do a search for each possible pair generated from two things from vec.

Why can't you sort two containers? Can you make a sorted copy of each? If so, take a pointer to the beginning of both lists and increase both matches. You would still be O (vec_pair size), but your constant would be very small - often this is just a comparison with a single pointer.