CODEWITHSUNDEEP
c++vector
KimHee
KimHee

Reputation: 778

How to find different set of two vectors with no repetitions?

I am writing the code to return the data in v1 that is not in v2 vector, with no repetitions using C++.

std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
                        std::inserter(diff, diff.begin()));

However, when my input v1,v2 are

v1=[137   138   139   140   141   142   143   144   148   150   157   158   161]
v2=[138   157   150   140   137   158   141   139   143   148]

The output results in unexpected solution as

diff=[   137   139   140   141   142   143   144   148   150   161]

While, my expected solution must be

diff=[  142   144   161]

What should I correct my function? Thanks

Upvotes: 1

Views: 286

Answers (3)

mksteve
mksteve

Reputation: 13073

v2 needs to be sorted. As does v1 (which it is). The function set_difference assumes both vectors are sorted.

The algorithm only has to walk each vector once, and only needs to compare the current cursor of each vector. This is a significant performance improvement, and space saving from an algorithm which worked with arbitrary inputs.

Upvotes: 1

Aram Gevorgyan
Aram Gevorgyan

Reputation: 2205

std::set_difference:

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first

http://en.cppreference.com/w/cpp/algorithm/set_difference

You must sort your vectors, before difference them

Upvotes: 1

Daniel Trugman
Daniel Trugman

Reputation: 8501

Look at the method:

std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
                        std::inserter(diff, diff.begin()));

It's called set_difference for a reason :)

Just use set containers instead of your vector ones. They will make sure that your data is sorted and that the algorithm is successful.

Upvotes: 0

Related Questions