Как найти самую длинную цепочку в массиве

С++: самая длинная цепочка элементов, для которой выполняется признак, или «указатель на шаблон функции»

Представим, что мы хотим реализовать на C++ некий алгоритм, например, поиск в массиве самой длинной цепочки элементов, отвечающих какому-либо признаку (отрицательность значения, чётность целочисленного значения, первый символ строки является латинской гласной и т.п.).

При этом нам хочется, чтобы алгоритм работал с разнотипными данными, например, и с числами, и со строками.
Сам по себе код, реализованный в функции max_series, несложен — мы ищем очередной элемент, отвечающий нужному признаку f и считаем длину цепочки таких элементов, запоминая номер первого элемента цепочки в переменной start, а длину цепочки — в переменной maxlen.

Существенней то, что проверять на соответствие признаку нужно разнотипные элементы, а значит, алгоритму следует передать указатель на функцию, получающую входной параметр нужного типа данных — того же, что у элементов массива.
Помочь может механизм шаблонов, с той оговоркой, что создать «указатель на шаблон функции» и использовать его, например, в качестве параметра другой функции, в C++ невозможно.

Шаблон функции — это не функция, а инструкция компилятору сгенерировать набор функций, отличающихся между собой типами параметров.

Соответственно, тип «указателя на шаблон функции» невозможен. Шаблон просто не имеет адреса памяти, на который мог бы сослаться указатель.

«Указатель на шаблон» можно объявить только после подстановки конкретного типа вместо class Type, тогда у функции появится и адрес в памяти.

Иными словами, template существует только в исходном коде. В исполняемый код попадает экземпляр (instance) шаблона, специализированного конкретными типами.

Соответственно, использовать оператор typedef для объявления такого указателя тоже нельзя.

К счастью, если написать обычную функцию-шаблон, аргументом которой инстанцируется ещё одна шаблонная функция для проверки элемента типа T на нужное свойство, то адрес такой функции вполне можно передать и решить нашу задачу, по коду, наверное, сказанное будет понятней:

#include <iostream>
#include <cstring>
using namespace std;

template <typename T>
void max_series (int n, T *a, int (*f)(T), int &start, int &maxlen) {
 int i=0,len,s;
 start=-1; maxlen=0;
 while (i<n) {
  while (f(a[i])==0) {
   i++;
   if (i==n) return;
  }
  len = 0; s = i;
  while (f(a[i])==1) {
   len++;
   if (len>maxlen) { maxlen=len; start=s; }
   i++;
   if (i==n) return;
  }
 }
}

template <typename T> int f1 (T a) { return a<0; }
template <typename T> int f2 (T a) { return ((int)a)%2==0; }
template <typename T> int f3 (T a) { return strchr("eyuioaEYUIOA",a[0])?1:0; }

int main () {
 const int n=8;
 int a[n]={1,2,-3,-4,-8,-6,8,-8}; //Массив с данными-числами
 int start,len; //начало и длина самой длинной цепочки

 //Применям алгоритм для поиска разных цепочек:
 max_series (n,a,&f1<int>,start,len); //...отрицательных элементов
 cout << endl << start << "," << len;
 max_series (n,a,&f2<int>,start,len); //...и делящихся на 2 без остатка
 cout << endl << start << "," << len;

 char *b[n]={"abba","bobina","yana","ilky","yeah","ugogo","sava","head"}; //Массив строк
 max_series (n,b,&f3<char *>,start,len); //...или вообще строк, начинающихся с гласных
 cout << endl << start << "," << len;

 cin.get();
 return 0;
}

Как видим, один и тот же код может проверять не только разные признаки для элементов массива, но и работать с массивами разных типов данных.

Проверено в консолях Studio 2015 и QT5, работает. Ну и полезно для размышлений на тему функций-делегатов в современных IDE

Что касается указателей на функции, помните главное — им можно присваивать адреса разных функций, но построенных по одному прототипу.

Мы можем определить нужный набор функций, одинаковых по списку параметров, создать указатель на функцию (typedef в C++ не нужен) и затем программно ставить указатель на нужную функцию, косвенно вызывая её:

#include <iostream>
using namespace std;

int f1 (int x) { return x+1; }
int f2 (int x) { return x+2; }

int main() {
 int x = 0;
 int(*pf)(int); //определяем указатель на функцию
 
 pf = &f1;
 cout << pf(x); //1
 pf = &f2;
 cout << endl << pf(x); //2
 cin.get();	return 0;
}

Другой вариант — определить тип указателя на нужный тип функций, потом создать массив объектов этого типа, инициализировать его адресами функций и в нужный момент вызывать нужную функцию:

#include <iostream>
using namespace std;

typedef int(*fptr)(int);  //определяем тип указателя на нужный тип функций

int f1 (int x) { return x+1; }
int f2 (int x) { return x+2; }

int main() {
 int x = 0;
 fptr pf[2] = { &f1, &f2 };
 
 cout << pf[0](x); //1
 cout << endl << pf[1](x); //2
 cin.get();	return 0;
}

Следует понимать, что задавая шаблон функции, мы определяем обобщённый (абстрактный) алгоритм, который должен быть применим к объектам разных типов данных T:

#include <iostream>
#include <string>
using namespace std;

template <class T>
T max(T a, T b) {
 return (a>b ? a : b);
}

int main() {
 int a = 3, b = 5;
 cout << max(a, b); //5
 string c = "vvv", d = "www";
 cout << endl << max(c, d); //www

 cin.get(); return 0;
}

В общем случае можно обьявить шаблонный класс, затем создать экземпляры класса с нужным типом и создать на них указатели.
Уже через эти указатели мы можем обрашаться к методам экземпляров, параметры и возвращаемые значения которых будут нужного типа.

Наконец, если мы стремимся создать шаблон, который бы генерировал функцию, вызывающую другую функцию, которую мы передали первой в шаблоне, и не хотим передавать указатель в качестве аргумента, помочь может показанный ниже подход со структурой-«обёрткой» executor.

#include <iostream>
using namespace std;

template < int(*func_ptr)(int, int) >
struct executor {
 int operator() (int a, int b) { return func_ptr(a, b); }
};

int fplus (int a, int b) { return a + b; }
int fminus (int a, int b) { return a - b; }

int main() {
	executor <&fplus> algorythm1;
	cout << algorythm1(1, 2); //3
	executor <&fminus> algorythm2;
	cout << endl << algorythm2(1, 2); //-1
	cin.get(); return 0;
}

29.05.2017, 22:06 [3404 просмотра]

К этой статье пока нет комментариев, Ваш будет первым