Как реализовать шаблон выбора типа метода в C ++?

Question

Вот сценарий:

void quicksort(void *data, size_t size);
void mergesort(void *data, size_t size);
void heapsort(void *data, size_t size);


size_t binary_search(void *data, size_t size, size_t key)
{
    // Usual binary search implementation
    // ...
    return 0; // just a placeholder
}

Я хочу, чтобы пользователь указал, какой алгоритм использовать для сортировки данных, а затем сортировка выполняется на основе этого алгоритма сортировки, а затем вызывается двоичный поиск для поиска ключа в этих данных.

Как мне реализовать эту минимальную ответственность для пользователя?

Answer 1

Конкретные примечания к вашему вопросу:

Не смешивайте сортировку и поиск.

Во-первых, линейный поиск - это O (N), тогда как sort_and_search - в лучшем случае O (N log N), т. Е. линейный поиск будет быстрее .Бинарный поиск - это хороший выбор алгоритма, только если вы много раз выполняете поиск по уже отсортированным данным.

Во-вторых, вы заметили, что вызывающей стороне необходим контроль над алгоритмом сортировки.Почему бы не позволить вызывающей стороне сделать это:

quicksort(data,size);
size_t result = binary_search(data,size);

---

Обобщение: Способы использования вашего примера:

(1) Параметр функтора , как продемонстрировал Навин

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

(2) указатель на функцию , как демонстрирует roe
Даже при том, что это выглядит "C-ish«Это простое, прямолинейное решение.Недостаток: вы не можете параметризовать функцию сортировки (например, указав, как выбрать точку в двоичной сортировке).

(3) полиморфизм
В основном вы:

определяете абстрактный базовый класс,

 struct ISort
 {
    virtual void Sort(void * data, size_t size) = 0;  
    virtual ~ISortData() {}      
 }

наследует от него конкретные реализации:

struct BinarySort : public ISort { ... }
struct MergeSort  : public ISort { ... }
struct HeapSort   : public ISort { ... }

и предоставить сортировку в качестве параметра для sort_and_search:

size_t sort_and_search(void * data, size_t size, ISort & sort);

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

---

Дополнительные примечания: интерфейс (void * data, size_t size)

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

STL применяет здесь три обобщения:

Сделать тип элемента параметром шаблона:

 template <typename T>
 size_t sas(T * values, size_t count)

это обеспечивает проверку типа и поддерживает перегруженное сравнениеоператоры для типа T.

Используйте итераторы вместо массивов:

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

Необязательный функтор сравнения:

Необязательный аргументкоторый содержит функтор для сравнения.Это позволяет использовать разные условия сортировки для одного и того же типа T.

Answer 2

Если вы хотите предоставить набор функций для сортировки и выполнить сортировку в функции binary_search перед поиском, попробуйте следующее:

void quicksort(void *data, size_t size);
void mergesort(void *data, size_t size);
void heapsort(void *data, size_t size);

size_t binary_search(void *data, size_t size, size_t key, void(*algorithm)(void*,size_t) = &quicksort)
{
    alogrithm(data,size); // sort it..
    // Usual binary search implementation
    return 0; // just a placeholder
}

Это решение в стиле C с добавленным по умолчанию аргументом C ++, позволяющим пользователю вообще ничего не указывать. Чтобы использовать больше C ++, ваши алгоритмы должны быть функторами, как предложил Навин, и позволить пользователю указать один из них. Хотя это потребует больше памяти и вызовет еще одно косвенное обращение (и пропадание кэша), так как оператор () обязательно является виртуальным, но это, вероятно, незначительно. Или вы можете создать шаблон, в этом случае вы просто будете использовать больше кода. Функтор имеет дополнительное преимущество, заключающееся в том, что вы можете параметризовать алгоритм (например, восходящий или нисходящий).

Тем не менее, это похоже на странный способ сделать это, когда 'binary_search' также выполняет сортировку. Я бы наложил ограничение на то, что данные должны быть отсортированы, поскольку сортировка уже отсортированных данных - пустая трата времени (например, если вы выполняете многократный поиск). Кроме того, быстрая сортировка имеет тенденцию быть O (n ^ 2) в отсортированных данных.

Answer 3

Я предлагаю принять функтор в качестве параметра для binary_search.Пользователь должен написать структуру и обеспечить реализацию для operator().Внутри operator() он может использовать любой метод сортировки, который он предпочитает.Этот подход будет аналогичен используемому в стандартной библиотеке.

РЕДАКТИРОВАТЬ

Пример кода:

void quicksort(void *data, size_t size)
{
}
void mergesort(void* data, size_t size)
{
}
struct QuickSort
{
    void operator()(void* data, size_t size) const
    {
        quicksort(data,size);
    }
};
struct MergeSort
{
    void operator()(void* data, size_t size) const
    {
        mergesort(data,size);
    }
};


template<typename Functor>
size_t binary_search(void *data, size_t size, size_t key, Functor sort)
{
    sort(data, size);
    //Rest of the code
    return 0;
}

int main() 
{ 
    binary_search(NULL,0, 0, QuickSort());
    binary_search(NULL,0, 0, MergeSort());
    return 0; 
}