View Single Post
Old 2013-04-10, 21:37   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·32·653 Posts
Default C++ template function syntax issues

Just for fun I am trying to implement a simple 10-line-or-so C++/STL version of merge-sort, to compare with a C-array-based version I previously wrote. The version based on an explicit type works fine - the problem occurs when I try to templatize it. Here is the resulting code:
Code:
// Simple recursive merge-sort on a length-n vector of data
template<typename T>
void merge_sort_stlvec(typename std::vector<T>::iterator ai, int n)
{
	int p, q;
	// Start with a sublist length of 1 and do n/2 single-element-sublist merges, skipping the 'orphan' sublist a[0] if n odd.
	// On each pass through the data, double the length of the sublists-to-be-merged, and merge adjacent sublist pairs
	if(n < 2) {
		return;
	}
	p = n>>1;
	// Recursively call merge_sort on the 2 sublists...
	merge_sort_stlvec(ai  , p);
	merge_sort_stlvec(ai+p, n-p);
	// ...And merge the 2 sorted sublists.
	std::inplace_merge(ai,ai+p,ai+n);
}
Note that my first attempt at this left off the 'typename std::' preceding the 'vector<T>::iterator' in the arglist, but both GCC (that is, g++) and LLVM/Clang need that namespace-specializing prefix to compile. In fact the above compiles fine ... until I actually try to call the function, via e.g.

[init length-n vectors of doubles and ints dvec and ivec]
merge_sort_stlvec(dvec.begin(),n);
merge_sort_stlvec(ivec.begin(),n);

That gives the following typical template-code-related error spaghetti from GCC:
Quote:
merge_sort.cpp: In function ‘int main(int, char**)’:
merge_sort.cpp:622: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >, int&)’
merge_sort.cpp:637: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, int&)’
Note that the template function definition - there is no header file with separate declaration - occurs above the calls to the function in the source file, so I doubt it's a "template declaration needs to go into included header" issue - but I tried doing the latter to be sure, no change.

Moving the entire template function into a header and including that - also no change, same errors.

Adding the following type specifiers to the calls:

merge_sort_stlvec<double>(dvec.begin(),n);
merge_sort_stlvec<int>(ivec.begin(),n);

causes the error-message spaghetti bowl to get even fuller:
Quote:
merge_sort.cpp: In function ‘void merge_sort_stlvec(typename std::vector<T, std::allocator<_CharT> >::iterator, int) [with T = double]’:
merge_sort.cpp:622: instantiated from here
merge_sort.cpp:467: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >&, int&)’
merge_sort.cpp:622: instantiated from here
merge_sort.cpp:468: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >, int)’
merge_sort.cpp: In function ‘void merge_sort_stlvec(typename std::vector<T, std::allocator<_CharT> >::iterator, int) [with T = unsigned int]’:
merge_sort.cpp:637: instantiated from here
merge_sort.cpp:467: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >&, int&)’
merge_sort.cpp:637: instantiated from here
merge_sort.cpp:468: error: no matching function for call to ‘merge_sort_stlvec(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, int)’
Note for the same code, Clang gives these errors:
Quote:
merge_sort.cpp:467:2: error: no matching function for call to 'merge_sort_stlvec'
merge_sort_stlvec(ai , p);
^~~~~~~~~~~~~~~~~
merge_sort.cpp:622:2: note: in instantiation of function template specialization 'merge_sort_stlvec<double>' requested here
merge_sort_stlvec<double>(dvec.begin(),n);
^
merge_sort.cpp:457:6: note: candidate template ignored: couldn't infer template argument 'T'
void merge_sort_stlvec(typename std::vector<T>::iterator ai, int n)
^
merge_sort.cpp:468:2: error: no matching function for call to 'merge_sort_stlvec'
merge_sort_stlvec(ai+p, n-p);
^~~~~~~~~~~~~~~~~
merge_sort.cpp:457:6: note: candidate template ignored: couldn't infer template argument 'T'
void merge_sort_stlvec(typename std::vector<T>::iterator ai, int n)
^
merge_sort.cpp:467:2: error: no matching function for call to 'merge_sort_stlvec'
merge_sort_stlvec(ai , p);
^~~~~~~~~~~~~~~~~
merge_sort.cpp:637:2: note: in instantiation of function template specialization 'merge_sort_stlvec<unsigned int>' requested here
merge_sort_stlvec<uint32>(ivec.begin(),n);
^
merge_sort.cpp:457:6: note: candidate template ignored: couldn't infer template argument 'T'
void merge_sort_stlvec(typename std::vector<T>::iterator ai, int n)
^
merge_sort.cpp:468:2: error: no matching function for call to 'merge_sort_stlvec'
merge_sort_stlvec(ai+p, n-p);
^~~~~~~~~~~~~~~~~
merge_sort.cpp:457:6: note: candidate template ignored: couldn't infer template argument 'T'
void merge_sort_stlvec(typename std::vector<T>::iterator ai, int n)
^
Lastly, I tried prefixing each occurrence of the 'ai' iterator in the function body with the same prefix as in the arglist, no joy. Any clues as to what is needed to make the syntax acceptable to the compiler/preprocessor are welcome.

Last fiddled with by ewmayer on 2013-04-10 at 21:49
ewmayer is offline   Reply With Quote