mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

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

267378 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
Old 2013-04-10, 22:24   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1174310 Posts
Default

Figured it out - the 2 recursive calls within the function definition also need a type-specialization prefix:

merge_sort_stlvec<T>(ai , p);
merge_sort_stlvec<T>(ai+p, n-p);

I simply *love* working with templates ... the compiler error messages are always so clear and incredibly helpful at pinpointing what is needed.
[/sarc]
ewmayer is offline   Reply With Quote
Old 2013-04-10, 22:33   #3
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

29B116 Posts
Default

Quote:
Originally Posted by ewmayer View Post
I simply *love* working with templates ... the compiler error messages are always so clear and incredibly helpful at pinpointing what is needed.
[/sarc]
Yeah. One might reasonably ask exactly who is working for whom.

Turning on excessive and pedantic warnings can be useful, but it might be nice if the compiler understood what we're trying to do.

Oh well... We're not there yet....
chalsall is offline   Reply With Quote
Old 2013-04-13, 01:37   #4
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

11010102 Posts
Default

The reason your the original code fails is deep in the C++ standard's language. In short, when you want the compiler to deduce argument types, those types must not be dependent types. In the above case, the type vector<T>::iterator is dependent on the type of T and will not be deduced. Hence, you're forced to spell out all the specializations. There are two ways around this:

- Accept the whole vector as input, i.e., by reference
- Accept a pair of iterators as input

Here's the latter, which is the standard way of doing things on the STL:

Code:
template<typename Iterator>
void merge_sort(Iterator begin, Iterator end)
{
    static_assert( std::is_same<
                        typename std::iterator_traits<Iterator>::iterator_category, 
                        std::random_access_iterator_tag
                    >::value, "merge_sort only likes random-access iterators" );
    const auto n = std::distance(begin, end);
    const auto p = n / 2;

    if(n < 2)
        return;

    merge_sort(begin, begin + p);
    merge_sort(begin + p, end);

    std::inplace_merge(begin, begin + p, end);
}
This uses some of the newer C++11 standard stuff, like auto type deduction, static_asserts, and standard type traits for the iterators.

You can safely ignore the static_assert: it is only there to cause a compilation error when the iterator type is not random-access, since we may want, for example, to implement the merge sort differently for vectors and linked-lists, depending on whether sequential or random access exists.

Here is an example, with an added helper function that takes in arbitrary containers (including normal C arrays): https://ideone.com/fvu57s

Last fiddled with by Robert Holmes on 2013-04-13 at 01:37
Robert Holmes is offline   Reply With Quote
Old 2013-04-13, 17:45   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

11,743 Posts
Default

Thanks, Robert, for the very succinct explanation and example. Being able to validate the iterator types at compile time as you demonstrate is very useful, especially in a templatized multi-type context.
Quote:
Originally Posted by Robert Holmes View Post
The reason your the original code fails is deep in the C++ standard's language. In short, when you want the compiler to deduce argument types, those types must not be dependent types. In the above case, the type vector<T>::iterator is dependent on the type of T and will not be deduced.
Now wouldn't it be nice if compilers (or their preprocessors) actually emitted errors to such effect, rather than utterly useless, exceedingly verbose gibberish?

Last fiddled with by ewmayer on 2013-04-14 at 00:51
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM RAM issues yoyo GMP-ECM 7 2018-04-28 05:51
A useful template for functions gcd() and totient(). JM Montolio A Miscellaneous Math 8 2018-02-28 15:23
Manual Testing LL result syntax (where to find documentation) preda GPU Computing 15 2017-04-17 15:02
New GPU; new issues... chalsall GPU Computing 18 2013-06-12 19:28
Some help needed with GGNFS syntax. 3.14159 Factoring 12 2010-05-28 01:25

All times are UTC. The time now is 08:41.


Sun Oct 2 08:41:16 UTC 2022 up 45 days, 6:09, 0 users, load averages: 1.70, 1.53, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔