|
2013-04-10, 21:37
|
#1 | |||
|
∂2ω=0
Sep 2002
República de California
5×2,351 Posts |
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);
}
[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:
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:
Quote:
Last fiddled with by ewmayer on 2013-04-10 at 21:49 |
|||
|
|
|
2013-04-10, 22:24
|
#2 |
|
∂2ω=0
Sep 2002
República de California
5×2,351 Posts |
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] |
|
|
|
|
2013-04-10, 22:33
|
#3 | |
|
If I May
"Chris Halsall"
Sep 2002
Barbados
2·72·113 Posts |
Quote:
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.... |
|
|
|
|
|
2013-04-13, 01:37
|
#4 |
Oct 2007
2·53 Posts |
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);
}
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 |
|
|
|
|
2013-04-13, 17:45
|
#5 | |
|
∂2ω=0
Sep 2002
República de California
2DEB16 Posts |
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:
Last fiddled with by ewmayer on 2013-04-14 at 00:51 |
|
|
|
|
 |
| 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 |
