C++ template function using iterators

Question

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?

Hint: iterator traits

Fred Larson
– Fred Larson

2014-06-05 17:48:32 +00:00
Commented Jun 5, 2014 at 17:48 — Fred Larson
– Fred Larson, Commented Jun 5, 2014 at 17:48

Fred Larson · Accepted Answer · 2014-06-05 18:20:44Z

3

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;

answered Jun 5, 2014 at 18:20

Fred Larson

62.3k19 gold badges117 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Michael Urman · Accepted Answer · 2014-06-05 18:02:58Z

1

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).

answered Jun 5, 2014 at 18:02

Michael Urman

15.9k2 gold badges31 silver badges44 bronze badges

1 Comment

Larry Over a year ago

thanks for the reply :) yah i was trying to fool around with function templates

Valdrinium · Accepted Answer · 2014-06-05 18:22:01Z

0

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.

edited Jun 5, 2014 at 18:22

answered Jun 5, 2014 at 17:48

Valdrinium

1,4161 gold badge14 silver badges29 bronze badges

2 Comments

Valdrinium Over a year ago

I know, but it's been some time since it's been released, so he should try using C++11

Valdrinium Over a year ago

You're right. Sorry. At least now is visible in the comments.

Collectives™ on Stack Overflow

C++ template function using iterators

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related