使用迭代器的 C++ 模板函数

Question

对不起，这一定是一个非常简单的问题...... 我是 C++ 的初学者，我正在尝试使用函数模板编写一个简单的快速排序函数。

#include <iostream>
#include <vector>
using namespace std;

template <class iterator, class val>
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 <class iterator>
void qsort(iterator begin, iterator end) {
  iterator oldbegin = begin;
  for (iterator i = begin + 1; i != end; i++) {
    if (*i <= *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<int> ar(test, test+9);
  qsort(ar.begin(), ar.end());

  for (vector<int>::iterator i = ar.begin(); i != ar.end(); i++) cout << *i;
  return 0;
}

编译器报错

/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<std::__1::__wrap_iter<int *> >' 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.

我想我在某种程度上错误地定义了模板...尤其是 val参与template <class iterator, class val> ,

请问如何实现？

Answer 1

问题是编译器无法在此处推断出您的模板参数之一:

template <class iterator, class val>
void move_to_front(iterator movethis, iterator leftend) {
    val temp = *movethis;          // hold the element being moved

没有 val 类型的函数参数，因此编译器无法知道该类型应该是什么。但无论如何你都不需要它。如果你有可用的 C++11，你可以使用 auto，正如 Scooby 所建议的那样。否则，您可以使用 std::iterator_traits从迭代器类型中获取值类型:

template <class iterator>
void move_to_front(iterator movethis, iterator leftend) {
    typename std::iterator_traits<iterator>::value_type temp = *movethis;