Как я могу реализовать несколько версий одного и того же алгоритма, избегая дублирования кода и конфликтующих имен?

Question

Я разработал алгоритмы сортировки вставкой и быстрой сортировки на C ++.Теперь я намерен создать как минимум четыре варианта алгоритма быстрой сортировки.Они будут различаться в зависимости от того, как они выбирают сводку и используют ли они сортировку вставки для небольших списков или нет.В Java или C #, чтобы избежать дублирования кода и противоречивых имен, я бы реализовывал каждую версию алгоритма Quicksort в отдельном файле класса и использовал наследование.В частности, я бы создал следующие классы:

• QuicksortFixedPivot
• QuicksortRandomPivot
• QuicksortFixedPivotInsertion - подмассивы с не более k элементами отсортированыиспользуя сортировку вставкой
• QuicksortRandomPivotInsertion

Однако из моего понимания «автономные» алгоритмы, такие как Quicksort, обычно не реализуются в классах в C ++.

Ниже приведен мойначальная реализация Quicksort.

quicksort.hpp

#pragma once
#include <vector>

namespace algorithms 
{
   void quicksort(std::vector<int> &list);
   void quicksort(std::vector<int> &list, int left, int right);
   int partition(std::vector<int> &list, int left, int right);
}

quicksort.cpp

#include "quicksort.hpp"

namespace alg = algorithms;

void alg::quicksort(std::vector<int> &list)
{
   alg::quicksort(list, 0, list.size() - 1);
}

void alg::quicksort(std::vector<int> &list, int left, int right)
{
   if (left >= right) 
      return;

   int oldPivot = alg::partition(list, left, right);
   alg::quicksort(list, left, oldPivot - 1);
   alg::quicksort(list, oldPivot + 1, right);
}

int alg::partition(std::vector<int> &list, int left, int right)
{
   int pivot = list[left + (right-left)/2];
   while (true)
   {
      while (list[left] < pivot)
         left++;
      while (list[right] > pivot)
         right--;
      if (left >= right)
         return left;
      std::swap(list[left], list[right]);
   }
}

С вышеупомянутымИсходя из этого, у меня есть два вопроса.

Во-первых, для того, чтобы быть единственной реализацией Quicksort, правильно ли я использовал заголовочные файлы и правильно ли структурировал свой код?Например, хорошо ли, что алгоритм находится за пределами класса?

Во-вторых, как мне подходить к созданию разных версий этого алгоритма, избегая при этом дублирования кода и конфликтов имен?Например, должен ли я использовать классы или какую-либо другую языковую конструкцию?

Я был бы признателен, если бы ответ содержал минимальные фрагменты кода, поясняющие, как следует использовать любые подходящие языковые конструкции для достижения аккуратного кода.

Answer 1

Если вы считаете, что могут быть разные параметры (например, pivot и insertion), которые можно выбирать независимо, тогда вам следует рассмотреть enum s (или лучше enum class es).

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

namespace alg {

enum class pivot { first=0; last=1; middle=2};
enum class insertion { off=0; on=1 };

template <pivot p, insertion i>
int partition(std::vector<int> &list, int left, int right)
{
    int pivot;
    if constexpr (p==pivot::first)
        pivot = list[left];
    else if constexpr (p==pivot::last)
        pivot = list[right];
    else // if constexpr (p==pivot::first)
        pivot = list[left + (right-left)/2];

    while (true)
    {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        if (left >= right)
            return left;
        std::swap(list[left], list[right]);
    }
}

template <pivot p, insertion i>
void quicksort_section( std::vector<int>& list, int begin, int end )
{
   if (left >= right) 
       return;

   int oldPivot = partition(list, left, right);
   quicksort_section(list, left, oldPivot - 1);
   quicksort_section(list, oldPivot + 1, right);
}

template <pivot p, insertion i>
void quicksort(std::vector<int> &list)
{
    quicksort_section<p,i>(list, 0, list.size() - 1);
}

} // namespace alg

Обратите внимание, что шаблоны обычно реализуются в заголовочных файлах.

Это решает все ваши потребности.Он расширяемый и позволяет избежать дублирования кода, т. Е. Вам не нужно отдельно обрабатывать все возможности N_pivot * N_insertion.

Если вы используете старую версию C ++ (до C ++ 17), вы можете просто удалитьconstexpr (с использованием некоторого макро-трюка), потому что любой разумный компилятор устраняет возникающий мертвый код.

Answer 2

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

#include <iostream>

struct versionA{};
struct versionB{};

int fooA(versionA tag, int param)
{
    (void)tag;//Silences "unused parameter" warning
    return 2*param;
}

int fooB(versionB tag,int param)
{
    (void)tag;
    return 5*param;
}

int main()
{
    std::cout<<fooA(versionA{},5)<<'\n';
    std::cout<<fooB(versionB{},5)<<'\n';
//Outputs:
//10
//25
}

Компилятор может оптимизировать эти пустые неиспользуемые структуры, поэтому в этом нет никакого вреда.В качестве альтернативы можно использовать шаблоны с параметром template, являющимся типом тега, и полностью специализировать их для отдельных версий.Но у этого подхода есть несколько недостатков - реализация утечек в заголовочные файлы и функции шаблона не может быть частично специализированной, что не будет хорошо работать, если сами алгоритмы нуждаются в параметрах шаблона.А шаблоны, смешанные с перегрузками, не всегда могут привести к вызову ожидаемой функции.

Если {} в вызовах функции вас беспокоит, вы можете создать глобальные экземпляры этих структур и передать их вместо этого (путем копирования).

Чтобы ответить на первый вопрос: да, вы правильно их использовали.Очень маленькое примечание - #pragma once не является стандартным C ++, но все стандартные компиляторы все равно его поддерживают.Правильная альтернатива - использовать include guard.

Полный пример с тегами:

// header file
#include <vector>

namespace algorithms 
{
namespace ver
{

    struct FixedPivot_tag{};
    struct RandomPivot_tag{};

    const extern FixedPivot_tag FixedPivot;
    const extern RandomPivot_tag RandomPivot;
}

void quicksort(ver::FixedPivot_tag tag, std::vector<int> &list, int left, int right);
void quicksort(ver::RandomPivot_tag tag, std::vector<int> &list, int left, int right);
}
// cpp file
namespace algorithms
{
    namespace ver
    {
        constexpr const FixedPivot_tag FixedPivot{};
        constexpr const RandomPivot_tag RandomPivot{};
    }

void quicksort(ver::FixedPivot_tag tag, std::vector<int> &list, int left, int right)
{
    (void)tag;
    //...
}
void quicksort(ver::RandomPivot_tag tag, std::vector<int> &list, int left, int right)
{
    (void)tag;
    //...
}
}
// usage
int main()
{
    std::vector <int> vector{5,4,3,2,1};
    using namespace algorithms;
    quicksort(ver::FixedPivot,vector,0,4);
    quicksort(ver::RandomPivot,vector,0,4);
}