如何在避免代码重复和冲突名称的同时实现同一算法的多个版本？

Question

我用C++开发了Insertion Sort和Quicksort算法.现在,我打算创建至少四种Quicksort算法的变体.它们在选择数据透视的方式以及是否对小列表使用插入排序方面会有所不同.在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

您可以类似地使用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
}

编译器可以优化这些空的未使用的结构,这样就没有任何危害.另一种方法是使用模板参数作为标签类型的模板,并为各个版本完全专门化它们.但是这种方法几乎没有缺点 - 对头文件和模板函数的泄漏实现不能部分专门化,如果算法本身需要模板参数,这将无法很好地发挥作用.与重载混合的模板可能并不总是导致调用预期的函数.

如果{}函数调用困扰您,您可以创建这些结构的全局实例并通过它们(通过复制).

要回答第一个问题:是的,您正确使用了它们.非常小的注意事项 - #pragma once不是标准的C++,但无论如何所有标准编译器都支持它.适当的替代方案是使用包括警卫.

标记的完整示例:

// 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);
}