Templates and higher-order kinds in C++

Question

I am trying to write a function that takes two containers of the same contained type, e.g., two std::vector<int>s, or a std::list<int> and a std::vector<int>. (But not a std::vector<int> and a std::vector<double>!)

Since I am not quite sure regarding how it should be done, I decided to write a test progam first:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

struct vector_wrapper
{
  template <typename T>
  struct instance_wrapper
  {
    typedef typename std::vector<T> instance;
  };
};

struct list_wrapper
{
  template <typename T>
  struct instance_wrapper
  {
    typedef typename std::list<T> instance;
  };
};

template <typename T, typename C1, typename C2>
void move(typename C1::instance_wrapper<T>::instance& c1, typename C2::instance_wrapper<T>::instance& c2) // line 29
{
  while (c1.size() > 0)
  {
    c2.push_front(c1.back());
    c1.pop_back();
  }
}

int main()
{
  std::vector<int> v;
  std::list  <int> l;

  v.reserve(10);
  for (int i = 0; i < 10; ++i)
    v.push_back(i);

  move<int, vector_wrapper, list_wrapper>(v, l);

  std::for_each(l.begin(), l.end(),
    [] (int i) { std::cout << i << " "; }
  );

  std::cout << std::endl;

  return 0;
}

---

This code gives me the following compile-time error with g++ 4.7, using the -std=c++11 flag:

metaclass.cpp:29:24: error: non-template 'instance_wrapper' used as template
... more ...

Why does the compiler not correctly identify instance_wrapper as a template?

Answer 1

Compiler has already told you what is wrong (errors from ideone):

prog.cpp:25:24: error: non-template 'instance_wrapper' used as template
prog.cpp:25:24: note: use 'C1::template instance_wrapper' to indicate that it is a template

Use C1::template instance_wrapper instead of C1::instance_wrapper - and, similarly, do the same for C2::instance_wrapper:

template <typename T, typename C1, typename C2>
void move(typename C1::template instance_wrapper<T>::instance& c1, 
    typename C2::template instance_wrapper<T>::instance& c2)
{
    // ...

It's because C1 is template and compiler cannot deduce that instance_wrapper is template and treats it as non-template type.

Please, please, read everything compiler outputs. Not just line-by-line. Often compiler says what's wrong in one of previous or following lines, as in this case, when it's already giving you the answer!

Answer 2

Here's a better solution that doesn't require any weird wrappers that disable argument deduction and have the client specify them, just clean and simple SFINAE that works in C++03:

#include <type_traits> // or Boost equivalent

// a little helper struct to keep the 
// function as clutter-free as possible
template<class C1, class C2, class T = void>
struct enable_if_same_value_type
  : std::enable_if<std::is_same<typename C1::value_type,
        typename C2::value_type>::value, T>
{
};

template<class C1, class C2>
typename enable_if_same_value_type<C1, C2>::type
move(C1& source, C2& target){
  /* ... */
}

Note that your code isn't quite generic, btw, since push_front is not supported by std::vector, so you're never able to pass two of them. Also, I wouldn't call the function move, since you're prepending the content of the first container on the second.

That said, there's a std::move overload in C++11 that takes three iterators and moves the content marked by the first too into the output iterator that is passed as the third parameter. As such, your main can be rewritten as follows:

#include <algorithm> // algorithmic move
#include <vector>
#include <list>
#include <iterator> // front_inserter
#include <iostream>

int main(){
  std::vector<int> v;
  std::list<int> l;

  v.reserve(10);
  for (unsigned i = 0; i < 10; ++i)
    v.push_back(i);

  // I used 'rbegin'  and 'rend' so the order stays the same
  std::move(v.rbegin(), v.rend(), std::front_inserter(l));

  std::copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " "));
}

Live example on Ideone.

Answer 3

For future reference, you can do this more simply:

#include <type_traits>

template<typename T, typename A1, typename A2, template <typename, typename> class Cont1, template<typename, typename> class Cont2>
void move(Cont1<T, A1>& from, Cont2<T, A2>& to) {
    while (!from.empty()) { // use !empty(), not size()
        to.push_front(from.back());
        from.pop_back();
    }
}

std::vector<int> v;
std::list<int> l;

move(v, l); // and no need to specify types