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

Question

我在C++中开发了插入排序和快速排序算法。现在，我打算创建至少四个变体的快速排序算法。它们将在选择枢轴的方式以及是否对小列表使用插入排序等方面有所不同。在Java或C#中，为了避免代码重复和名称冲突，我将在一个单独的类文件中实现快速排序算法的每个版本，并使用继承。具体来说，我要创建以下类：

• QuicksortFixedPivot
• QuicksortRandomPivot
• QuicksortFixedPivotInsertion -最多包含k元素的子数组使用插入排序进行排序。
• QuicksortRandomPivotInsertion

然而，根据我的理解，快速排序之类的“独立”算法通常不是在C++中的类中实现的。

下面是快速排序的初步实现。

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

基于上述背景，我有两个问题。

首先，作为一个单独的快速排序实现，我是否适当地使用了头文件并以一种良好的方式构造了我的代码？例如，算法在类之外是好的吗？

其次，如何在避免代码重复和命名冲突的同时创建该算法的不同版本？例如，我应该使用类或其他语言构造吗？

如果答案中包含最小的代码片段，说明如何使用任何相关的语言结构来实现简洁的代码，我将不胜感激。

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

Answer 2

如果您认为可以独立地选择不同的参数(如pivot和insertion)，那么您应该考虑enums (或更好的enum classes)。

您可以将信息作为参数传递(使用标准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++版本(pre C++17)，您只需删除constexpr (使用一些宏技巧)，因为任何合理的编译器都可以避免出现死代码。