C++ 模板集合类型

Question

编辑。请看我的评论。

我已经为此苦苦挣扎了一段时间。我一直在编写一个对 vector 进行操作的归并排序例程(诚然是重新发明轮子)，并且我一直在将迭代器传递给我的排序函数。在排序函数中，我创建了一个临时 vector 。现在，我希望它可以对任何元素类型进行操作，因为代码中没有任何内容是特定于整数/ double 等的。我似乎无法让我的模板定义工作。我已经尝试了许多不同的方法来做到这一点。如果有人可以看看我在下面写的小片段，并告诉我如何让它工作，以便我可以接受一个 vector::iterator 作为函数参数，然后在函数本身内声明和使用一个 vector ，我真的很感激。

#include <vector>
using namespace std;

template <typename T>
void test(vector<T>::iterator myiter) {
  typename vector<T> myvec;
}

这是我的编译时错误:

$ make tmpl
g++  -Wall -ggdb --std=c++11   tmpl.cc   -o tmpl
tmpl.cc:5:22: error: variable or field ‘test’ declared void
 void test(vector<T>::iterator myiter) {
                      ^
tmpl.cc:5:31: error: expected ‘)’ before ‘myiter’
 void test(vector<T>::iterator myiter) {

如果有任何兴趣，这是我正在使用的完整列表的当前快照 - 而 merge() 是我正在努力处理的。我已经多次更改模板语法并出现各种类型的失败:

#include <iostream>
#include <vector>

template <typename Iter>
void print_collection(Iter start, Iter end) {
  std::cout << "collection = { ";
  for(; start != end; ++start) {
    std::cout << *start << ", ";
  }
  std::cout << "};" << std::endl;
}


template <typename T>
void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
  std::vector<T> temp;
  std::vector<T>::iterator i, j;
  i = start;
  j = pivot;
  while(i != pivot && j != end) {
    if(*i <= *j) {
      temp.push_back(*i);
      ++i;
    } else if(*i > *j) {
      temp.push_back(*j);
      ++j;
    }
  }
  for(; i != pivot; ++i) {
    temp.push_back(*i);
  }
  for(; j != end; ++j) {
    temp.push_back(*j);
  }
  i = start;
  j = temp.begin();
  for(; i != end, j != temp.end(); ++i, ++j) {
    *i = *j;
  }
}


template <typename Iter>
void merge_sort(Iter start, Iter end, int len) {
  if(len <= 1) {
    return;
  }
  int odd, left_len, right_len;
  Iter pivot;
  odd = len % 2;
  left_len = (len / 2) + odd;
  pivot = start + left_len;
  right_len = len / 2;

  merge_sort(start, pivot, left_len);
  merge_sort(pivot, end, right_len);
  merge(start, pivot, end, left_len, right_len);
}


int main(void) {
  std::vector<double> vl = { 1.1, 9.1, 2.1, 8.1, 3.1, 7.1, 4.1, 6.1, 5.1, 0.1 };
  print_collection(vl.begin(), vl.end());
  merge_sort(vl.begin(), vl.end(), vl.size());
  print_collection(vl.begin(), vl.end());
  return 0;
}

这是完整 list 中的编译错误:

$ make vec
g++  -Wall -ggdb --std=c++11   vec.cc   -o vec
vec.cc:39:28: error: variable or field ‘merge’ declared void
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                            ^
vec.cc:39:37: error: expected ‘)’ before ‘start’
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                     ^
vec.cc:39:69: error: expected ‘)’ before ‘pivot’
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                                                     ^
vec.cc:39:101: error: expected ‘)’ before ‘end’
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                                                                                     ^
vec.cc:39:106: error: expected primary-expression before ‘int’
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                                                                                          ^
vec.cc:39:120: error: expected primary-expression before ‘int’
 void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                                                                                                        ^
vec.cc: In instantiation of ‘void merge_sort(Iter, Iter, int) [with Iter = __gnu_cxx::__normal_iterator<double*, std::vector<double> >]’:
vec.cc:88:45:   required from here
vec.cc:81:47: error: ‘merge’ was not declared in this scope
   merge(start, pivot, end, left_len, right_len);

^

Answer 1

两个问题:

1. std::vector<T>::iterator 的所有实例应该是 typename std::vector<T>::iterator因为它依赖于模板参数。原因在规范问题 Where and why do I have to put the "template" and "typename" keywords? 中有解释。

   如果你compile with Clang，这里的错误信息会更清楚:

   main.cpp:15:12: error: missing 'typename' prior to dependent type name 'std::vector<T>::iterator'
   void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
              ^~~~~~~~~~~~~~~~~~~~~~~~
              typename 
   main.cpp:15:44: error: missing 'typename' prior to dependent type name 'std::vector<T>::iterator'
   void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                              ^~~~~~~~~~~~~~~~~~~~~~~~
                                              typename 
   main.cpp:15:76: error: missing 'typename' prior to dependent type name 'std::vector<T>::iterator'
   void merge(std::vector<T>::iterator start, std::vector<T>::iterator pivot, std::vector<T>::iterator end, int left_len, int right_len) {
                                                                              ^~~~~~~~~~~~~~~~~~~~~~~~
                                                                              typename 
   main.cpp:17:3: error: missing 'typename' prior to dependent type name 'std::vector<T>::iterator'
     std::vector<T>::iterator i, j;
     ^~~~~~~~~~~~~~~~~~~~~~~~
     typename 
   

2. Once you fix that , 编译器会告诉你它不能推断出 T什么时候merge被调用，因为 :: 左边的所有内容是一个非推导上下文。没有真正的原因 merge应该在 T 上模板化而不是迭代器类型，或者实际上为什么必须将迭代器限制为 std::vector (除了代码中第一次分配 pivot 然后将 temp.begin() 分配给 j 的地方，可以通过添加另一个变量轻松修复):

   template <typename Iter>
   void merge(Iter start, Iter pivot, Iter end, int left_len, int right_len);
   

   但是你创建了一个std::vector<T>从头开始，所以我们现在需要弄清楚T ，或迭代器的值类型。方法是通过 std::iterator_traits :

   typedef typename std::iterator_traits<Iter>::value_type T;
   

附带问题:i != end, j != temp.end()作为循环条件毫无意义。大概你的意思是i != end && j != temp.end() .

Demo .