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).

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.