Inner-Join on two sorted C++ vector<int>'s

[Dean_5]

So... I've slept since college - meaning I've forgotten a few things. I need to do an inner-join on two large-ish sorted vectors. Thought about converting them to unsorted sets and walking through "find-ing", but I'm pretty sure this is the fastest way to do it - and still accurately. Still, wanted to check with DaniWeb:

#include <iostream>
#include <vector>

int main(){
    std::vector<int>
        aList={0,2,3,4,6,7,8,10,11,12},
        bList={0,1,3,4,5,6,8,9,11},
        cList={};
    //Begin matching algorithm
    for(
        //Create iterators
        auto aIter=aList.begin(),bIter=bList.begin();
        //Break on either iterator reaching the end
        (aIter != aList.end() && bIter != bList.end());
        //Increment aIter before looping
        aIter++
    ){
        //Skip any elements on bList less than current aIter
        while((*bIter)<(*aIter)){
            bIter++;
        }
        //If there's a match, push it onto cList
        if((*bIter)==(*aIter)){
            cList.push_back(*bIter);
        }

    }
    //End matching algorithm
    for(auto c:cList){
        std::cout<<c<<std::endl;
    }
    return 0;
}

This should run O(n).

[StuXYZ]

This method seems strange to me .

The first thing that is obviously wrong is these lines:

 while((*bIter)<(*aIter)){
            bIter++;
        }

What happens if bIter is at the last position in the array.

So in short I would have written something like this

  std::vector<int>::const_iterator aIter=aList.begin();
  std::vector<int>::const_iterator bIter=bList.begin();
  if (bIter==bList.end()) return 0;

  for(;aIter!=aList.end();aIter++)
    {
      while(*bIter < *aIter)
        {
          if (++bIter==bList.end()) break;
        }
     if (*bIter == *aIter)
        cList.push_back(*bIter);
    }

Finally there is always the standard algorithms and you can do this:

#include <algorithm> 

//.....

std::set_intersection(aList.begin(), aList.end(),
            bList.begin(), bList.end(),                       
            std::back_inserter(cList));

I am not 100% certain of its speed but is it quick and easy to write and normally the stl is quick enough relative to simple hand coded stuff.

Notes:

I am very disinclinded to use auto when the algorithm only works for int and not doubles or other number types.

Second many may not like the break in the middle of the loop -- you can put it outside if you like.