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

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

但是，根据我的理解，像 Quicksort 这样的“独立”算法通常不会在 C++ 的类中实现。

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

快速排序.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);
}

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

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

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

最佳答案

你可以像 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);
}

关于c++ - 如何在避免代码重复和名称冲突的同时实现同一算法的多个版本？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54901297/