Om du vill generalisera din shell-sort till att hantera alla typer som implementerar indikeringsoperatorn [] så behöver du bara ändra tre små ändringar
template<class IndexableContainer>
void shellsort(IndexableContainer &a)
{
int j;
const int gap[8]={701, 301, 132, 57, 23, 10, 4, 1};
for(int x = 0; x<8; x++)
{
for(unsigned int i = gap[x]; i < a.size(); i++)
{
typename IndexableContainer::value_type tmp = a[i];
for(j=i; j>=gap[x] && tmp < a[j-gap[x]]; j-= gap[x])
{
a[j] = a[j-gap[x]];
}
a[j] = tmp;
}
}
}
Och vad det gäller shellsort(v) vs shellsort<int>(v), i detta fall spelar det ingen roll (men i detta fall är nog den första att föredra).
Skillnaden är att shellsort(v) låter kompilatorn lura ut dels om man ska använda en template överhuvudtaget (kan ju finns en shellsort(vector<int> &v) funktion som då "vinner") och om det ska använda en template så lurar kompilatorn ut värdet på T vilket i detta fall är möjligt då v är av typen vector<int> då den enda värdet på T som uppfyller sinaturen är int.
I shellsort<int>(v) så specificerar programmaren att T måste vara int, om v då är något annat än vector<int> så blir det ett kompileringsfel.
Edit: Har aldrig använt shell-sort mer än att testat att göra en implementation som kunde köra på flera CPU-kärnor (var relativt lätt just med shell-sort). Att skriva shell-sort för att lära sig är ju definitivt vettigt och jag har full förståelse för sådana experiment. Men finns det någon poäng med att använda denna algoritm i praktiken då den är relativt långsam? Är man nervös över quick-sorts "worst-case" där den konsumerar O(N²) stack och tar O(N²) att köra så finns ju alltid mergesort. Att göra en "in-place" mergesort i C++ är ju relativt enkelt, kan göra t.ex. så här
// Måste ha en bidirektionellt iterator för 'inplace_merge'
// Har explicit satt ut 'std::' för att visa att
// det är standardfunktioner jag använder
template<class BidIt>
void mergesort(BidIt first, BidIt last)
{
typename BidIt::difference_type len = std::distance(first, last);
if (len > 1)
{
BidIt middle = first;
std::advance(middle, len / 2);
mergesort(first, middle);
mergesort(middle, last);
std::inplace_merge(first, middle, last);
}
}
// Hjälpfunktion för att ge samma signatur
// som du hade i shell-sort
template<class Container>
void mergesort(Container &a)
{
mergesort(a.begin(), a.end());
}
