C++不需要使用递归排序算法的数组长度

Question

有些人可能知道或者可能不知道您可以使用以下代码获取函数的数组参数的大小:

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
  ...
  return;
}

其中SIZE可用于表示数组中元素的数量,允许程序员使用您的函数将数组作为参数传递,而无需显式传递长度.例如,程序员可以这样做:

SortingAlgorithm( arrayToBeSorted ); //the length is not passed here, which is fine

对于可以相对容易地以迭代方式实现的算法,这很好.但我试图用其他递归算法来做这件事.每个代码的代码可能如下所示:

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
  DataType newArray[SIZE];
  memcpy(newArray,array, SIZE);  //copy to a new array
  SortingAlgorithm( newArray );
  ...
  return;
}

但是这每次都会抛出一个错误,说程序期望一个不同的参数类型,类型转换失败,并且显示尝试多次为newArray数组类型化SIZE说明符,并且程序失败.但是,如果在进行递归调用之前使用实际值来定义newArray的大小,它不会吐出这些错误,如下所示:

DataType newArray[10]; //arbitrary number, but the compiler accepts this.

为什么变量大小的数组会导致错误？无论如何还要实现一个递归算法,它接受一个数组作为输入,但不要求数组的长度作为参数,因为它可以在函数调用中每次确定数组的长度？

Answer 1

创建一个大小的辅助函数,它可以由你的其他函数在内部使用,没有人必须知道它.例如:

template<typename DataType>
void SortingAlgorithm_helper(DataType * ptr, size_t size)
{
    ...
    SortingAlgorithm_helper(ptr + 1, size - 1);
    ...
}

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
    ...
    SortingAlgorithm_helper(newArray,SIZE);
    ...      
}

根据您的意见,您正在考虑切换到矢量.好吧,你不必在这里做出选择.您可以使代码更通用以处理这两者.我们传入两个指定范围的迭代器,而不是将指针和大小传递给辅助函数.然后我们修改main函数来接受任何容器,只要std::begin和std::end它一起工作.

template<typename Iterator>
void SortingAlgorithm_helper(Iterator first, Iterator last)
{
    ...
    SortingAlgorithm(++first, last);
    ...
}

template<typename Container>
void SortingAlgorithm(Container & c)
{
    ...
    SortingAlgorithm_helper(std::begin(c), std::end(c));
    ...
}

这应该处理内置数组std::vector,std::array和std::deque.如果将对迭代器执行的操作限制为双向(++和 - ),那么它也应该处理std::list.