C++ template error

Question

I am learning C++ template, and I write a little algorithm. Unfortunately I got some errors Here is my code

    #include <iostream>
#include <iomanip>
#include <deque>
using namespace std;

template<typename T, typename S, typename W>
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
{
  original_stack.push_back(value);
  if (min_index.size() == 0)
    min_index.push_back(0);
  else
    {
      if (value < original_stack[min_index.back()])
    {
      min_index.push_back(original_stack.size() - 1);
    }
      else
    {
      min_index.push_back(min_index.back());
    }
    }
}

template<typename S, typename W>
void pop(deque<S>& original_stack, deque<W>& min_index)
{
  original_stack.pop_back();
  min_index.pop_back();
}

template<typename T, typename S, typename W>
const T& min(deque<S>& original_stack, deque<W>& min_index)
{
  return original_stack[min_index.back()];
}

int main()
{
  deque<int> data_stack;
  deque<int> min_index;
  push(3, &data_stack, &min_index);
  push(4, &data_stack, &min_index);
  push(2, &data_stack, &min_index);
  push(1, &data_stack, &min_index);
  pop(&data_stack, &min_index);
  pop(&data_stack, &min_index);
  push(0, &data_stack, &min_index);
  cout<<"min num is: "<<min(&data_stack, &min_index)<<endl;
}

When I use g++ to compile it, I get this:

g++ minstack.cpp -o minstack
minstack.cpp:42:3: error: no matching function for call to 'push'
  push(3, &data_stack, &min_index);
  ^~~~
minstack.cpp:7:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-1, allocator<type-parameter-0-1> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:43:3: error: no matching function for call to 'push'
  push(4, &data_stack, &min_index);
  ^~~~
minstack.cpp:7:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-1, allocator<type-parameter-0-1> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:44:3: error: no matching function for call to 'push'
  push(2, &data_stack, &min_index);
  ^~~~
minstack.cpp:7:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-1, allocator<type-parameter-0-1> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:45:3: error: no matching function for call to 'push'
  push(1, &data_stack, &min_index);
  ^~~~
minstack.cpp:7:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-1, allocator<type-parameter-0-1> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:46:3: error: no matching function for call to 'pop'
  pop(&data_stack, &min_index);
  ^~~
minstack.cpp:26:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-0, allocator<type-parameter-0-0> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void pop(deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:47:3: error: no matching function for call to 'pop'
  pop(&data_stack, &min_index);
  ^~~
minstack.cpp:26:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-0, allocator<type-parameter-0-0> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void pop(deque<S>& original_stack, deque<W>& min_index)
     ^
minstack.cpp:48:3: error: no matching function for call to 'push'
  push(0, &data_stack, &min_index);
  ^~~~
minstack.cpp:7:6: note: candidate template ignored: could not match
      'deque<type-parameter-0-1, allocator<type-parameter-0-1> >' against
      'std::__1::deque<int, std::__1::allocator<int> > *'
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)
     ^
7 errors generated.

I am confused, could anyone help me to fix these bugs, I am kind of new to C++ template.

Answer 1

You have a problem at the call site, e.g.:

deque<int> data_stack;
deque<int> min_index;
push(3, &data_stack, &min_index);

If you compare the above push() function call with your push() template overload here:

template<typename T, typename S, typename W>
void push(const T& value, deque<S>& original_stack, deque<W>& min_index)

you can note that the second and third parameters are references (to some deque instances).

But at the call site you pass addresses of the deque instances, using the address-of operator (&), which would have worked if the parameters were defined as pointers (not references).

Since you opted for using references (and not pointers) in the function definition, then just get rid of the address-of operator at the call site.
This will be just fine:

push(3, data_stack, min_index); // References used

The same goes for the other function calls.

---

Note that this is a problem related to references vs. pointers. You can abstract away the template part, and just consider this simple C++ code to figure out the problem:

void f(int& n) {
    n++;
}

int main() {
    int i = 1;
    // f(&i); // <-- fails to compile
    f(i);
}

Since the f() function expects a reference to an int, then you don't want to pass the int i variable using a pointer at the call site: just pass i (not &i).

Answer 2

original_stack.push_back(value); // T and S should have the same type or at least T should be derived from S

But that is not the problem.

int main()
{
  deque<int> data_stack;
  deque<int> min_index;
  push(3, data_stack, min_index);
  push(4, data_stack, min_index);
  push(2, data_stack, min_index);
  push(1, data_stack, min_index);
  pop(data_stack, min_index);
  pop(data_stack, min_index);
  push(0, data_stack, min_index);
  cout<<"min num is: "<<min(data_stack, min_index)<<endl;
}

As you can see, I removed al the address-of operators because you are passing by reference; You need to pass the address when your arguments are pointers.

Also, the return type of min should be S, because you return an element of the stack. And you don`t even need W, because indexes are always ints.

Answer 3

Don't pass the addresses to the functions, the arguments are references not pointers

  push(3, data_stack, min_index);
  push(4, data_stack, min_index);
  push(2, data_stack, min_index);
  push(1, data_stack, min_index);
  pop(data_stack, min_index);
  pop(data_stack, min_index);
  push(0, data_stack, min_index);

And you need to explicitly tell the return type for min

cout << min<int>(data_stack, min_index) << std::endl ;

Or use:

template<typename S, typename W>
 typename deque<S>::value_type& min(deque<S>& 
                                  original_stack, deque<W>& min_index)
{
  return original_stack[min_index.back()];
}