Removing duplicates for both values My special case: home project, automatic downloader for podcasts.

Overall algorithm is:


Download a list of available podcasts
hash the podcasts
load metadata + hash of downloaded podcasts from sqlite db
Algorithm this questions is about -  throw out all already downloaded.
Download new podcasts
save metadata to sqlite db


Algorithm discussion

I'm hoping for comments on using std::rotate, performance, and the implementation.

For downloaded data, I currently use a vector. For data from DB, I also use a vector.

I merge both together and sort them according to the hashes (obviously).

And algorithm doubleEraser on the merged vector.

#include &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;string&gt;

template &lt;typename ForwardItr&gt;
ForwardItr doubleEraser(ForwardItr first, ForwardItr last)
{
 auto itr = first;
 typename std::iterator_traits&lt;ForwardItr&gt;::value_type firstMatch = *first;
 bool hasFirstMatch(false);

 while(itr != last)
 {
  auto next = std::next(itr);
  if(next != last &amp;&amp; *itr == *next)
  {
    if(!hasFirstMatch)
    {
     hasFirstMatch = true;
     firstMatch = *itr;
    }
    else
    {
     if(*itr == firstMatch) // again at first match
     {
       return itr; 
     }
    }


    std::rotate(itr, std::next(itr, 2), last); // throw matched elements to the end of container
   }
   else
    ++itr;
  }
 return last;
}

template &lt;typename T&gt;
void print(T&amp; c)
{
 for(auto &amp; element : c)
  std::cout &lt;&lt; element &lt;&lt; " ";

 std::cout &lt;&lt; "\n";
}

template &lt;class T&gt;
void process(std::vector&lt;T&gt;&amp; t)
{
  std::string formating(" \t");
   std::cout &lt;&lt; "input: " &lt;&lt; formating;
 print(t);
 std::sort(t.begin(), t.end());
 std::cout &lt;&lt; "sorted:" &lt;&lt; formating;
 print(t);
 auto itr_begin = doubleEraser(t.begin(), t.end());
 std::cout &lt;&lt; "dEraser:" &lt;&lt; formating;
 print(t);
 t.erase(itr_begin, t.end());
 std::cout &lt;&lt; "output:" &lt;&lt; formating;
 print(t);
}

int main()
{
 std::vector&lt;int&gt; vec {1,2,3,4,5,6,7,8,9,3,5,6,7,2};
 std::vector&lt;char&gt; vec2 {'A', 'C', 'D', 'D', 'G', 'A' };
 std::vector&lt;std::string&gt; vec3 {"Hello", "World", "that", "be", "that", "Hello"};

 process(vec);
 process(vec2);
 process(vec3);
}
Comment by @T.C.: 

Don't merge them; sort them separately and then use std::set_difference:

#include &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
template &lt;typename T&gt;
void print(T&amp; c)
{
 for(auto &amp; element : c)
  std::cout &lt;&lt; element &lt;&lt; " ";

 std::cout &lt;&lt; "\n";
}

int main()
{
 std::vector&lt;int&gt; vec {1,2,3,4,6,7,8};
 std::vector&lt;int&gt; vec4 {3,4,5,6};
 std::sort(vec.begin(), vec.end());
 std::sort(vec4.begin(), vec4.end());
std::set_difference(vec.begin(), vec.end(), vec4.begin(), vec4.end(), std::inserter(vec5, vec5.begin()));
 print(vec5);
}



Input: {1,2,3,4,6,7,8} and {3,4,5,6}
Output wanted: 1,2,5,7,8
Output real: 1,2,7,8


You cannot use std::set_difference because of the hashes used as comparison criteria. The Hash Distribution of new hashes is not sortable in a way that new items will be the last ones, which is a requirement for std::set_difference.