How to apply the intersection between two lists in C++?

Question

I am new to C++ list.

I have two lists: list1 and list2. I need to get common elements between these lists. How can I get this?

Answer 1

You can use: std::set_intersection for that, provided you first sort the two lists:

Example:

#include <algorithm>
#include <iostream>
#include <list>

int main() {
    std::list<int> list1{2, 5, 7, 8, -3, 7};
    std::list<int> list2{9, 1, 6, 3, 5, 2, 11, 0};

    list1.sort();
    list2.sort();

    std::list<int> out;
    std::set_intersection(list1.begin(), list1.end(), list2.begin(), list2.end(),
                          std::back_inserter(out));

     for(auto k : out)
         std::cout << k << ' ';
}

Output:

2 5

EDIT:

The above method is likely not going to be optimal, mostly because sorting a std::list isn't nice to the CPU...

For a trade-off of space, the method below will certainly be faster for larger sets of data, because we iterate through each list only once, and all operations done at each iteration doesn't go beyond a O(1) amortized complexity

template<typename T>
std::list<T> intersection_of(const std::list<T>& a, const std::list<T>& b){
    std::list<T> rtn;
    std::unordered_multiset<T> st;
    std::for_each(a.begin(), a.end(), [&st](const T& k){ st.insert(k); });
    std::for_each(b.begin(), b.end(),
        [&st, &rtn](const T& k){
            auto iter = st.find(k);
            if(iter != st.end()){
                rtn.push_back(k);
                st.erase(iter);
            }
        }
    );
    return rtn;
}

I used std::unordered_multiset rather than std::unordered_set because it preserves the occurences of common duplicates in both lists

I ran a dirty benchmark for the two methods on randomly generated 9000 ints, The result was (lower is better):

Average timings for 100 runs:
intersection_of:  8.16 ms
sortAndIntersect: 18.38 ms

---

Analysis of using the std::set_intersection method:

• Sorting List 1 of size N is: O(Nlog(N))
• Sorting List 2 of size M is: O(Mlog(M))
• Finding the Intersection is: O(M + N)
• Total: O( Nlog(N) + Mlog(M) + M + N) ...(generalized as logarithmic)

Assuming M and N are equal, we can generalize it as: O(Nlog(N))

But if we use the intersection_of method I posted above:

• Iterating through List 1 of size N and adding to the set is: O(N) + O(1) = O(N)
• Iterating through List 2 of size M, checking the multiset, adding to out, removing from List 2 : O(M) + O(1) + O(1) + O(1) = O(M)
• Total: O(M + N) ...(generalized as linear)

Assuming M and N are equal, we can generalize it as: O(N)