how to declare array when data type is not known

Question

I am implementing merge_sort. As the merging cannot be done in place (according to my current knoweledge), i have to declare a temporary array to store the values while merging.

Since it is a generic algorithm, the data type can be anything.

What can be a possible solution..?

Ans. One way to do it is to take another template argument T and get the data type, but i really dont want to change my function structure as it is like the ones i found on STL.

Here is my code :

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

pls read the question carefully...i have also put the thing in bold "i really dont want to change my function structure" — Rohith R, Jan 23 '15 at 20:57
How is `sorted_list` declared? Can you make a second copy of it? — Thomas Matthews, Jan 23 '15 at 20:57
`sorted_list` is just a temporary array i wish to declare so as to keep the sub-array's sorted before merging them — Rohith R, Jan 23 '15 at 20:59
Now that we know it is a temporary array, how is it defined or declared? — Thomas Matthews, Jan 23 '15 at 21:01

score 3 · Accepted Answer · answered Jan 23 '15 at 21:01

3

You can use std::iterator_traits to get the iterator value type.

Specifically, with std::iterator_traits<RandomAccessIterator>::value_type.

answered Jan 23 '15 at 21:01

Nick Strupat

4,928
4
44
56

Giving This error :`error: need ‘typename’ before ‘std::iterator_traits<_Iter>::value_type’ because ‘std::iterator_traits<_Iter>’ is a dependent scope std::iterator_traits::value_type *sorted_list = new std::iterator_traits::value_type [N1+N2]; ` – Rohith R Jan 23 '15 at 21:13
Well, the error is telling you that you need to add ‘typename’ before ‘std::iterator_traits<_Iter>::value_type’. The error is accurate. – Nick Strupat Jan 23 '15 at 21:16
@PRP http://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords – sbabbi Jan 23 '15 at 21:17
Ah, good question. C++ doesn't have strong enough type propagation rules in that particular case, requiring that you explicitly tell the compiler that you promise it's a valid type. – Nick Strupat Jan 23 '15 at 21:17

score 2 · Answer 2 · answered Jan 23 '15 at 21:06

2

In C++11, you can use decltype:

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

answered Jan 23 '15 at 21:06

jxh

69,070
8
110
193

Notice that the `iterator_traits` is more likely to be the correct thing. Although `RandomAccessIterator::begin` is required to always return a `value_type&`, it is not unlikely for a non-conforming user-defined iterator to return a proxy reference. – sbabbi Jan 23 '15 at 21:13
@sbabbi: In the case of a non-conforming user-defined iterator, `iterator_traits` won't work at all. – jxh Jan 23 '15 at 21:32
Yep, please ignore my previous comment. – sbabbi Jan 23 '15 at 21:39

how to declare array when data type is not known

2 Answers2