Code Yarns ‍👨‍💻
Tech Blog ❖ Personal Blog

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

📅 2010-May-25 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, stl, vector ⬩ 📚 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(),

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.

© 2022 Ashwin Nanjappa • All writing under CC BY-SA license • 🐘 • 📧