Code Yarns ‍👨‍💻
Tech BlogPersonal Blog

C++ STL: Find common elements of 2 sorted vectors

📅 2010-May-25 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, intersection, stl, vectors ⬩ 📚 Archive

Finding the elements common among two sorted vectors and storing the (common) result in a third vector can be done using the std::set_intersection algorithm as follows:

std::set_intersection(  vec0.begin(), vec0.end(),
                        vec1.begin(), vec1.end(),
                        vec2.begin()    );

Note that std::set_intersection expects the result vector to be of enough size, i.e. of size max( vec0.size(), vec1.size() ). I find this ugly since the result vector needs to be filled with junk elements and its space is wasted depending on the result of the intersection.

Thankfully, STL has std::back_inserter which can handle this situation:

std::set_intersection(  vec0.begin(), vec0.end(),
                        vec1.begin(), vec1.end(),
                        std::back_inserter( vec2 )  );

The std::back_inserter acts as an iterator to std::set_intersection while it uses std::vector.push_back() to insert each new element given by it. So, the resulting vector does not need to be initialized to an appropriate size and after std::set_intersection it has only the result elements and has exactly that size.