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

Question

我用 C++ 开发了插入排序和快速排序算法。现在，我打算创建至少四种快速排序算法的变体。他们在如何选择主元以及是否对小列表使用插入排序方面会有所不同。在 Java 或 C# 中，为避免代码重复和名称冲突，我会在单独的 class 文件中实现每个版本的 Quicksort 算法并使用继承。具体来说，我将创建以下 classes:

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

但是，根据我的理解，"standalone" 像 Quicksort 这样的算法通常不会在 C++ 的 classes 中实现。

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

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 实现，我是否适当地使用了头文件并以一种好的方式构建了我的代码？例如，算法在 class 之外是否好？

其次，我应该如何在避免代码重复和命名冲突的同时创建该算法的不同版本？例如，我应该使用 classes 还是其他一些语言结构？

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

Answer 1

你可以像 std 那样做，例如execution policy 用于算法。它使用可以通过结构轻松完成的标记：

#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++，但所有标准编译器都支持它。正确的替代方法是使用 include guards。

带标签的完整示例：

// 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++ 版本（C++17 之前），您可以删除 constexpr（使用一些宏技巧），因为任何合理的编译器都会消除出现的死代码。

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

How can I implement multiple versions of the same algorithm while avoiding code duplication and conflicting names?

c++

structure