title: C++ template function using iterators
body: <p>I'm sorry this must be a really simple question...
  I'm a beginner of C++ and I was trying to write a trivial quicksort function using function template.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  template &lt;class iterator, class val&gt;
  void move_to_front(iterator movethis, iterator leftend) {
    val temp = *movethis;          // hold the element being moved
    for (iterator i = movethis; i != leftend; i--) {
      *i = *(i-1);
    }                              // all other elements shift right
    *leftend = temp;               // put it back to the front
  }
  
  template &lt;class iterator&gt;
  void qsort(iterator begin, iterator end) {
    iterator oldbegin = begin;
    for (iterator i = begin + 1; i != end; i++) {
      if (*i &lt;= *begin) {
        move_to_front(i, begin);
        oldbegin++;
      }
    } // move elements smaller than or equal to the first element
      // to the left of the first element.
      // oldbegin indicates the first element, so it + 1 every time an 
      // element is moved to its left. 
  
    qsort(begin, oldbegin);
    qsort(oldbegin, end);
  }
  
  int main(int argc, char const *argv[]) {
    int test[] = {8,7,2,4,1,4,5,4,2};
    vector&lt;int&gt; ar(test, test+9);
    qsort(ar.begin(), ar.end());
  
    for (vector&lt;int&gt;::iterator i = ar.begin(); i != ar.end(); i++) cout &lt;&lt; *i;
    return 0;
  }
  </code></pre>
  
  <p>The compiler complains</p>
  
  <pre><code>/Users/Larry_Li/Project Euler/foo.cpp:20:11: error: no matching function for call to 'move_to_front'
            move_to_front(i, begin);
            ^~~~~~~~~~~~~
  /Users/Larry_Li/Project Euler/foo.cpp:31:7: note: in instantiation of function template specialization 'qsort&lt;std::__1::__wrap_iter&lt;int *&gt; &gt;' requested here
        qsort(ar.begin(), ar.end());
        ^
  /Users/Larry_Li/Project Euler/foo.cpp:6:10: note: candidate template ignored: couldn't infer template argument 'val'
      void move_to_front(iterator movethis, iterator leftend) {
           ^
  1 error generated.
  </code></pre>
  
  <p>I think I was defining the template wrong somehow... especially the <code>val</code> part in <code>template &lt;class iterator, class val&gt;</code>,</p>
  
  <p>May I ask how to make it work?</p>