数据类型未知时如何声明数组

Question

我正在实施 merge_sort。由于合并无法就地完成（根据我目前的知识），我必须声明一个 temporary array 来在合并时存储值。

由于是泛型算法，数据类型可以是任何类型

有什么可能的解决方案..?

回答。一种方法是采用另一个模板参数 T 并获取数据类型，但我真的不想更改我的函数结构，因为它就像我在 STL 上找到的那样。

这是我的代码：

template <class RandomAccessIterator>
void merge (RandomAccessIterator first,int N1,RandomAccessIterator second,int N2)
{
    int i,j,k;

    // How to declare the sorted_list array when data type is not known....

    i = 0;   // Inedex Of The First List
    j = 0;  // Index Of The Second List
    k = 0; // Index Of The Sorted List

    while (i<N1 && j<N2)
    {
        if (first[i] < second[j])
            sorted_list[k++] = first[i++];
        else
            sorted_list[k++] = second[j++];

    }
    if (i == N1)
    {
        while (j < N2)
            sorted_list[k++] = second[j++];
    }
    else
    {
        while (i  < N1)
            sorted_list[k++] = first[i++];
    }

}

template <class RandomAccessIterator>
void merge_sort (RandomAccessIterator begin,RandomAccessIterator end)
{
    int N = end - begin + 1;
    int N1,N2;

    if (N == 1)
        return;

    RandomAccessIterator mid = (begin + end)/2;

    merge_sort (begin,mid);
    merge_sort (mid+1,end);

    N1 = end - begin + 1;
    N2 = end - mid;

    merge (begin,N1,mid+1,N2);
}

Answer 1

您可以使用 std::iterator_traits 获取迭代器值类型。

具体来说，std::iterator_traits<RandomAccessIterator>::value_type。

Answer 2

在 C++11 中，您可以使用 decltype:

std::vector<decltype(*begin)> tmp_array;

数据类型未知时如何声明数组

how to declare array when data type is not known

c++

generics

custom-data-type