C++ Template Collection Type

Question

Edit. Please see my comment.

I've been struggling with this for a while now. I've been writing a mergesort routine that operates on vectors (reinventing the wheel admittedly), and I've been passing iterators to my sort function. Within the sort function, I create a temporary vector. Now, I'd like it to operate on any element type, as there's nothing in the code that is specific to ints/doubles etc etc. I can't seem to get my template definition working. I've tried many many different ways of doing this. If someone could possibly look at the small snippet I've written below, and show me how to get it working so that I can accept a vector::iterator as a function argument, and then declare and use a vector within the function itself, I'd really appreciate it.

#include <vector>
using namespace std;

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

here's my compile time error:

$ 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) {

If it's of any interest, this is a current snapshot of the full listing I'm working with - and merge() is the one I'm struggling with. I've changed the template syntax multiple times with various types of fail:

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

and here's the compile error from the full listing:

$ 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

Two issues:

1. All instances of std::vector<T>::iterator should be typename std::vector<T>::iterator since it's dependent on a template parameter. The reason is explained in the canonical question Where and why do I have to put the "template" and "typename" keywords?

   The error message here is much clearer if you 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, the compiler will tell you that it can't deduce T when merge is called, because everything to the left of :: is a non-deduced context. There is no real reason why merge should be templated on T and not the iterator type, or indeed why it must be limited to iterators into a std::vector (other than the one place in the code when you first assign pivot and then temp.begin() to j, which can be easily fixed by adding another variable) :

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

   But you create a std::vector<T> as scratch, so we now need to figure out T, or the iterator's value type. The way to do it is via std::iterator_traits:

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

Side issue: i != end, j != temp.end() as a loop condition makes little sense. Presumably you meant i != end && j != temp.end().

Demo.