1

This question suggests using std::set_intersection to find the intersection of two arrays. Wouldn't using std::find work just as well?

int a[5] = {1, 2, 3, 4, 5};
int b[5] = {3, 4, 5, 6, 7};

for (int i=0; i<5; i++)
{
    if (std::find(b, b+5, a[i])!=b+5)
        std::cout << a[i] << std::endl;
}

Does std::set_intersection basically do the same thing? Or maybe it uses a more efficient algorithm? I think the complexity of above is O(n^2) if std::find takes O(n) time.

Community
  • 1
  • 1
qwr
  • 9,525
  • 5
  • 58
  • 102

3 Answers3

1

For all (or at least almost all) of your standard-library-complexity questions, a good reference can answer this for you.
In particular we get that std::find performs At most last - first applications of the predicate (operator< in this case) where first and last define your range to be searched.
We also get that std::set_intersection performs At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).

This means that your loop performs at most N1 * N2 applications of operator<, which in this case is 25. std::set_intersection would use at most 18.

So, the two methods would "work just as well" in the sense that they give the same answer, but std::set_intersection would take less comparisons to do it.

SirGuy
  • 10,660
  • 2
  • 36
  • 66
0

std::set is an ordered collection. There are faster methods (linear) for such collections (think mergesort).

user515430
  • 298
  • 1
  • 3
  • 7
0

std::set::find takes O(lg n), it's a binary search. So using a for loop together with find takes O(n lg n). std::set_intersection takes linear time: align the two sets to find their intersection (similar to the merge operation of mergesort).

SirGuy
  • 10,660
  • 2
  • 36
  • 66
mrk
  • 3,061
  • 1
  • 29
  • 34
  • `std::find` does not do a binary search since there is no way for it to know _a priori_ that the input range is sorted, so it takes linear time. – SirGuy Oct 04 '14 at 23:55
  • sets have their own version of find. Edited to point that out. – mrk Oct 05 '14 at 00:04
  • There aren't any set objects here, we have arrays. And even if we did have sets, using `std::find` with iterators from a set isn't guaranteed to take `O(log n)`. Only using `std::set<...>::find` is guaranteed to do that. – SirGuy Oct 05 '14 at 00:07
  • There is mention to set_intersection and arrays in OP are sorted. Link to suggested answer talks about sorted sets as well. – mrk Oct 05 '14 at 00:15
  • `std::set_intersection` doesn't just work on sets, it works on any sorted range, of which `std::set` is one example. This doesn't change the fact that your `std::find` can only be guaranteed to take linear time. Unless when you say `std::find` you mean `std::set::find`, your answer has an error. – SirGuy Oct 05 '14 at 00:43