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;
    }

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.

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.