sort(vi); sort(Vector<int>& v);

sort(vc); sort(Vector<String>& v);

sort(vi2); sort(Vector<int>& v);

sort(vs); sort(Vector<char*>& v);

Какая именно функция sort() будет вызываться определяется фактическим параметром. Программист дает определение шаблона типа для функции, а задача системы программирования обеспечить создание правильных вариантов функции по шаблону и вызов соответствующего варианта. Например, простой шаблон с алгоритмом пузырьковой сортировки можно определить так:

template<class T> void sort(Vector<T>& v)

Сортировка элементов в порядке возрастания Используется сортировка по методу пузырька

*/ {

unsigned n = v.sizeO; for (int i=0; i<n-1;

for (int j=n-1; i<j; j-- )

if (v[j] < v[j-1]) { меняем местами v[j] и v[j-1] T temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

Советуем сравнить это определение с функцией сортировки с тем же алгоритмом из $$4.6.9. Существенное отличие этого варианта в том, что вся необходимая информация передается в единственном параметре v. Поскольку тип сортируемых элементов известен (из типа фактического параметра, можно непосредственно сравнивать элементы, а не передавать указатель на производящую сравнение функцию. Кроме того, нет нужды возиться с операцией sizeof. Такое решение кажется более красивым и к тому же оно более эффективно, чем обычное. Все же оно сталкивается с трудностью. Для некоторых типов операция < не определена, а для других, например char*, ее определение противоречит тому, что требуется в приведенном определении шаблонной функции. (Действительно, нам нужно сравнивать не указатели на строки, а сами строки). В первом случае попытка создать вариант sort() для таких типов закончится неудачей (на что и следует надеяться) , а во втором появиться функция, производящая неожиданный результат.

Чтобы правильно сортировать вектор из элементов char* мы можем просто задать самостоятельно подходящее определение функции

sort(Vector<char*>&):

void sort(Vector<char*>& v)

unsigned n = v.sizeO; for (int i=0; i<n-1;

for ( int j=n-1; i<j; j-- )

if (strcmp(v[j],v[j-1])<0) {

меняем местами v[j] и v[j -1]

char* temp = v[j];

v[j] = v[j-1];

8.4.1 Простой шаблон типа для глобальной функции

Начнем с простейшего шаблона для sort():

template<class T> void sort(Vector<T>&); void f(Vector<int>& vi,

Vector<String>& vc,

Vector<int>& vi2,

Vector<char*>& vs)

Класс SortableVector (сортируемый вектор) можно определить так:

template<class T> class SortableVector

: public Vector<T>, public Comparator<T> { public:

SortableVector(int s) : Vector<T>(s) { }

Чтобы это определение имело смысл еще надо определить шаблонный класс Comparator (сравниватель):

template<class T> class Comparator { public:

inline static lessthan(T& a, T& b) функция меньше

{ return strcmp(a,b)<0; } ...

Чтобы устранить тот эффект, что в нашем случае операция < дает не тот результат для типа char*, мы определим специальный вариант класса сравнивателя:

class Comparator<char*> { public:

inline static lessthan(const char* a, const char* b)

функция меньше

{ return strcmp(a,b)<0; }

...

Описание специального варианта шаблонного класса для char* полностью подобно тому, как в предыдущем разделе мы определили специальный вариант шаблонной функции для этой же цели. Чтобы описание специального варианта шаблонного класса сработало, транслятор должен обнаружить

v[j-1] = temp;

Поскольку для векторов из указателей на строки пользователь дал свое особое определение функции sort(), оно и будет использоваться, а создавать для нее определение по шаблону с параметром типа Vector<char*>& не нужно. Возможность дать для особо важных или необычных типов свое определение шаблонной функции дает ценное качество гибкости в программировании и может быть важным средством доведения программы до оптимальных характеристик.

8.4.2 Производные классы позволяют ввести новые операции

В предыдущем разделе функция сравнения была встроенной в теле sort() (просто использовалась операция <). Возможно другое решение, когда ее предоставляет сам шаблонный класс Vector. Однако, такое решение имеет смысл только при условии, что для типов элементов возможно осмысленное понятие сравнения. Обычно в такой ситуации функцию sort() определяют только для векторов, на которых определена операция < :

template<class T> void sort(SortableVector<T>& v)

unsigned n = v.sizeO; for (int i=0; i<n-1;

for (int j=n-1; i<j; j-- )

if (v.lessthan(v[j],v[j-1])) { меняем местами v[j] и v[j-1] T temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

sort(vi); sort(vc); sort(vi2); sort(vs);

Возможно иметь два вида векторов и не очень хорошо, но, по крайней мере, SortableVector является производным от Vector. Значит если в функции не нужна сортировка, то в ней и не надо знать о классе SortableVector, а там, где нужно, сработает неявное преобразование ссылки на производный класс в ссылку на общий базовый класс. Мы ввели производный от Vector и Comparator класс SortableVector (вместо того, чтобы добавить функции к классу, производному от одного Vector) просто потому, что класс Comparator уже напрашивался в предыдущим примере. Такой подход типичен при создании больших библиотек. Класс Comparator естественный кандидат для библиотеки, поскольку в нем можно указать различные требования к операциям сравнения для разных типов.

8.4.3 Передача операций как параметров функций

Можно не задавать функцию сравнения как часть типа Vector, а передавать ее как второй параметр функции sort(). Этот параметр является объектом класса, в котором определена реализация операции сравнения:

template<class T> void sort(Vector<T>& v, Comparator<T>& cmp)

unsigned n = v.sizeO; for (int i = 0; i<n-1;

for ( int j = n-1; i<j; j-- )

if (cmp.lessthan(v[j],v[j-1])) { меняем местами v[j] и v[j -1] T temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

Этот вариант можно рассматривать как обобщение традиционного приема, когда операция сравнения передается как указатель на функцию. Воспользоваться этим можно так:

void f(Vector<int>& vi,

Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs)

Comparator<int> ci;

Comparator<char*> cs;

Comparator<String> cc;

sort(vi,ci); sort(Vector<int>&);

sort(vc,cc); sort(Vector<String>&);

sort(vi2,ci); sort(Vector<int>&);

sort(vs,cs); sort(Vector<char*>&);

его до использования. Иначе будет использоваться создаваемый по шаблону класс. Поскольку класс должен иметь в точности одно определение в программе, использовать и специальный вариант класса, и вариант, создаваемый по шаблону, будет ошибкой.

Поскольку у нас уже специальный вариант класса Comparator для char*, специальный вариант класса SortableVector для char* не нужен, и можем, наконец, попробовать сортировку:

void f(SortableVector<int>& vi,

SortableVector<String>& vc, SortableVector<int>& vi2, SortableVector<char*>& vs)