CODEWITHSUNDEEP
c++templates
Larry
Larry

Reputation: 938

C++ template function using iterators

I'm sorry this must be a really simple question... I'm a beginner of C++ and I was trying to write a trivial quicksort function using function template.

#include <iostream>
#include <vector>
using namespace std;

template <class iterator, class val>
void move_to_front(iterator movethis, iterator leftend) {
  val temp = *movethis;          // hold the element being moved
  for (iterator i = movethis; i != leftend; i--) {
    *i = *(i-1);
  }                              // all other elements shift right
  *leftend = temp;               // put it back to the front
}

template <class iterator>
void qsort(iterator begin, iterator end) {
  iterator oldbegin = begin;
  for (iterator i = begin + 1; i != end; i++) {
    if (*i <= *begin) {
      move_to_front(i, begin);
      oldbegin++;
    }
  } // move elements smaller than or equal to the first element
    // to the left of the first element.
    // oldbegin indicates the first element, so it + 1 every time an 
    // element is moved to its left. 

  qsort(begin, oldbegin);
  qsort(oldbegin, end);
}

int main(int argc, char const *argv[]) {
  int test[] = {8,7,2,4,1,4,5,4,2};
  vector<int> ar(test, test+9);
  qsort(ar.begin(), ar.end());

  for (vector<int>::iterator i = ar.begin(); i != ar.end(); i++) cout << *i;
  return 0;
}

The compiler complains

/Users/Larry_Li/Project Euler/foo.cpp:20:11: error: no matching function for call to 'move_to_front'
          move_to_front(i, begin);
          ^~~~~~~~~~~~~
/Users/Larry_Li/Project Euler/foo.cpp:31:7: note: in instantiation of function template specialization 'qsort<std::__1::__wrap_iter<int *> >' requested here
      qsort(ar.begin(), ar.end());
      ^
/Users/Larry_Li/Project Euler/foo.cpp:6:10: note: candidate template ignored: couldn't infer template argument 'val'
    void move_to_front(iterator movethis, iterator leftend) {
         ^
1 error generated.

I think I was defining the template wrong somehow... especially the val part in template <class iterator, class val>,

May I ask how to make it work?

Upvotes: 1

Views: 5287

Answers (3)

Valdrinium
Valdrinium

Reputation: 1416

Try this, assuming you are using C++11:

template <class iterator>
void move_to_front(iterator movethis, iterator leftend) {
  auto temp = *movethis;          // hold the element being moved
  for (iterator i = movethis; i != leftend; i--) {
    *i = *(i-1);
  }                              // all other elements shift right
  *leftend = temp;               // put it back to the front
}

But, in my opinion, I thik you're overcomplicating with all the iterators.

Upvotes: 0

Fred Larson
Fred Larson

Reputation: 62113

The problem is that the compiler cannot deduce one of your template arguments here:

template <class iterator, class val>
void move_to_front(iterator movethis, iterator leftend) {
    val temp = *movethis;          // hold the element being moved

There is no function parameter of type val, so there's no way for the compiler to know what that type should be. But you don't need it anyway. If you have C++11 available, you could use auto, as Scooby suggested. Otherwise, you could use std::iterator_traits to get the value type from the iterator type:

template <class iterator>
void move_to_front(iterator movethis, iterator leftend) {
    typename std::iterator_traits<iterator>::value_type temp = *movethis;

Upvotes: 3

Michael Urman
Michael Urman

Reputation: 15905

This probably won't help directly, as you appear to be intentionally reinventing the wheel, and/or using this scenario to test and expand your template knowledge rather than to solve the exact problem your code is written to solve. But just in case all you want to do is implement move_to_front, consider std::rotate:

#include <algorithm>

template <class iterator>
void move_to_front(iterator movethis, iterator leftend) {
    std::rotate(leftend, movethis, movethis + 1);
}

You may also want to consider changing the order of your arguments to be more in line with the STL, but that's up to you. See a live example (the example uses C++11 but the function does not require it).

Upvotes: 1

Related Questions