C++ 模板集合类型

Question

编辑。请看我的评论。

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

#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;
}

这是完整清单中的编译错误：

$ 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

两个问题：

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

Once you fix that，调用merge时编译器会告诉你不能推导出T，因为[=17左边的都是=] 是一个非推导上下文。没有真正的理由说明为什么 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>作为scratch，所以我们现在需要弄清楚T，或者迭代器的值类型。方法是通过 std::iterator_traits:
```
typedef typename std::iterator_traits<Iter>::value_type T;
```

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

Demo.

C++ 模板集合类型

C++ Template Collection Type

c++

collections

templates

vector

std