tags:

views:

69

answers:

2

Hi. I have been trying out to figure out a way to find intersection of N lists in c++.

The method that is clicking me is sort, merge and iterate.

Is there any other way too ?

Please share your suggestions.

+4  A: 

Sort each list using std::sort (or if it's an std::list, use std::list::sort) then compute the intersections using std::set_intersection iteratively (apply it to the first two lists, then to the result and the third list, then to the result and the fourth list, and so on).

James McNellis
A: 

A solution using unsorted lists would be messier. Presumably, you'd have an 'answer' list, initially empty. Then you'd identify two lists, and step through one; for each element, you'd scan the other list to see if it is present in that list - storing the element in the answer if there's a match. Then you'd create a new empty answer list, and step through another of the original lists, searching through the previous answer list for a matching element, and adding to the new answer list. Repeat ad nauseam.

This is not particularly efficient.

For the 'sort, merge, and iterate' solution, working with pairs of lists, is also not as effective as simultaneously iterating through the N sorted lists in parallel, only selecting elements that appear in all lists as part of the answer.

Jonathan Leffler