Intersection of two sorted vectors in C++

Question

Intersection of two sorted vectors in C++ - can this be written any better?

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 vector<int> result;
 int l = 0, r = 0;
 while(l < nums1.size() && r < nums2.size()){
 int left = nums1[l], right = nums2[r];
 if(left == right){
 result.push_back(right);
 while(l < nums1.size() && nums1[l] == left )l++;
 while(r < nums2.size() && nums2[r] == right )r++;
 continue;
 }
 if(left < right){
 while(l < nums1.size() && nums1[l] == left )l++;
 }else while( r < nums2.size() && nums2[r] == right )r++;
 }
 return result;
 }

• user673679: Do you know about std::set_intersection()? Reference and example implementations: en.cppreference.com/w/cpp/algorithm/set_intersection
• Rick: @user673679 yes I did, and didn't want to use it

Answer 1

• Indentation

  Your indentation is not consistent. This makes the code hard to read and maintain. It should be fixed so you don't give other people headaches.

   if(left < right){
   while(l < nums1.size() && nums1[l] == left )l++;
   }else while( r < nums2.size() && nums2[r] == right )r++;
  

  That is basically unreadable giberish (opinion of Martin).

• Using namespace std; is super bad

  This is mention in nearly every C++ review. There is a large article on the subject here: Why is "using namespace std" considered bad practice? . The second answer is the best in my opinion (Martin) see

• Multiple declarations in one is bad (thanks to terrible syntax binding rules)

  The one declaration per line has been written about adnausium in best practice guides. Please for the sake of your reader declare one variable per line with its own exact type.

  The syntax binding rules alluded to above is:

  int* x, y; // Here x is int* and y in int
   // confusing to a reader. Did you really mean to make y an int?
   // Avoid this problem be declaring one variable per line
  

• Typically, functions like this would be based on iterators to work on any container

  Here your code is limited to only using vectors. But the algorithm you are using could be used by any container type with only small modifications. As a result your function could provide much more utility being written to use iterators.

  The standard library was written such that iterators are the glue between algorithms and container.

• It would be a lot simpler, if not necessarily more efficient at runtime, to just use some hash sets.

• This function could be generic in T rather than assuming int.
• The repeated conditions make me feel like there's simplification waiting here, although exactly what that is eludes me in the two minutes I'm spending on this.
• Should take by const ref, not ref, so that you can operate on temporaries.

• pacmaninbw: You caught the problems and I voted you up, but you could improve your answer by explaining what the issue for the first 4 bullet items.
• Loki Astari: @pacmaninbw: Added some context.
• Will Ness: @MartinYork wow! whose answer is it, anyway? :) :) /intended in a positive way/

Answer 2

I invite you to review @DeadMG's answer.

Rewriting following (most of) his advice, you'd get something like:

#include <cassert>
#include <algorithm>
#include <vector>
std::vector<T> intersection(std::vector<T> const& left_vector, std::vector<T> const& right_vector) {
 auto left = left_vector.begin();
 auto left_end = left_vector.end();
 auto right = right_vector.begin();
 auto right_end = right_vector.end();
 assert(std::is_sorted(left, left_end));
 assert(std::is_sorted(right, right_end));
 std::vector<T> result;
 while (left != left_end && right != right_end) {
 if (*left == *right) {
 result.push_back(*left);
 ++left;
 ++right;
 continue;
 }
 if (*left < *right) {
 ++left;
 continue;
 }
 assert(*left > *right);
 ++right;
 }
 return result;
}

I've always found taking pairs of iterators awkward, so I would not recommend such an interface. Instead, you could take simply take any "iterable", they need not even have the same value type, so long as they are comparable:

template <typename Left, typename Right>
std::vector<typename Left::value_type> intersection(Left const& left_c, Right const& right_c);

Also, note that I've included some assert to validate the pre-conditions of the methods (the collections must be sorted) as well as internal invariants (if *left is neither equal nor strictly less than *right then it must be strictly greater).

I encourage you to use assert liberally:

• They document intentions: pre-conditions, invariants, etc...
• They check that those intentions hold.

Documentation & Bug detection rolled in one, with no run-time (Release) cost.

• Loki Astari: Why don't you post that as its own questions. There are some improvements even if we don't move to iterators like using template template types.
• Matthieu M.: @MartinYork: I generally don't find "template template" to be an improvement, they're quite awkward to use, and tend to constrain the inputs more than intended.
• Toby Speight: Accepting iterable types is a good idea, and certainly the direction of modern C++ (Ranges, etc). If I were writing it, I'd probably provide the iterator-pair interface for the rare occasions that the caller needs more control, and provide the range interface as a thin adapter. Also, consider the Standard Library pattern of passing an output iterator - that can similarly be wrapped with an adaptor if a vector result is needed.
• Matthieu M.: @TobySpeight: If you want two pairs of iterators as input and an output iterator as output... well, that's set_intersection :) Another nice trick, rather than taking an output iterator as argument, would be to create an "intersecting range" which can be consumed lazily and us that to initialize whatever collection you want... haven't played much with ranges yet but it seems doable.
• Toby Speight: I've haven't played with ranges myself, but that does sound like a worthwhile exercise; I'll put that on the list of fun things to do when I get around to it (probably when I need light relief from maintaining C++03 code).