CODEWITHSUNDEEP
c++booststl
Rajat Gupta
Rajat Gupta

Reputation: 93

Algorithm to find elements with matching properties amongst opposite catgeories using STL

I have a list of elements belonging to either of two categories A & B. Each element has a property P. The requirement is that property P can not have same value for any two elements belonging to different categories. We have to find all sets of elements which share the same property value and violate this rule. What is the simplest way to implement it using C++ STL/boost libraries. I am using gcc 4.8.3. So any solution requiring c++14 or beyond will not work.

Upvotes: 0

Views: 105

Answers (1)

Adrian McCarthy
Adrian McCarthy

Reputation: 47952

Sort the list on P. That will bring all elements with the same P together. So you can now walk the list and, for each adjacent pair, check if they have the same P and are of different categories.

O(n log n) for the sort and O(n) to walk the list and check.

Upvotes: 1

Related Questions