CODEWITHSUNDEEP
c++stlset
user535450
user535450

Reputation:

set intersection

I want to calculate the gcd of two numbers m and n by prime factorization and taking common factors like this. Take example m = 36 n = 48

vector<int> factors1 = prime_factorization(m); // 2 2 3 3 
vector<int> factors2 = prime_factorization(n); // 2 2 2 2 3
vector<int> intersection(10);
set_intersection(factors1.begin(), factors1.end(), factors2.begin(), factors2.end(), intersection.begin());

intersection is now 2 2 3 0 0 0 0 0 0 0. For this i must set the size of the vector beforehand. Also the remaining elements are set to 0. I don't want this to happen.

Is there a better way to do this? Using sets or anything else?

Also, how do i calculate the product of elements in the vector intersection (2*2*3) using stl ignoring the zeroes?

Upvotes: 0

Views: 3487

Answers (2)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

Oli's answer is best in the situation as you describe it. But if you were using a vector that already existed and had elements that you were writing over, and you wanted to chop off the extra numbers, you can do it a different way. By calling the vector member erase using the return value of set_intersection:

intersection.erase(
    set_intersection(factors1.begin(), factors1.end(), factors2.begin(), factors2.end(), intersection.begin()),
    intersection.end());

Upvotes: 5

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

You can use a back-inserter:

vector<int> intersection;
set_intersection(..., back_inserter(intersection));

Note that there are much better ways of determining the GCD, such as Euclid's algorithm.

Upvotes: 12

Related Questions