CODEWITHSUNDEEP
c++c++11
sircodesalot
sircodesalot

Reputation: 11439

How do you pass a std::array?

I was trying out something simple like this:

template<class T>
array insertionSort(array<T> arr) {

    for (int index = 1; index < arr.size(); index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}

void main() {
    array<int, 10> mine = { 1, 0, 2, 9, 3, 8, 4, 7, 5, 6 };

    array result = insertionSort<int>(mine);

    cin.get();
}

It seems as though array requires two type parameters (the type as well as the size), so how do I pass it to and from a function without knowing the size up front?

Upvotes: 8

Views: 5061

Answers (3)

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153830

In general, you don't really want to pass containers around! The same algorithm which works for std::array<T, N> also works for other data structures, e.g., std::vector<T> or std::deque<T>. The C++ approach in that case is to pass iterator and to [slightly] adjust the algorithm:

template<typename BidrectionalIterator>
void insertionSort(BidirectionalIterator begin, BidirectionalIterator end) {
    for (BidirectionalIterator it(begin); it != end; ++it) {
        for (BidirectionalIterator insertion(it), tmp(insertion);
             begin != insertion && *--tmp > *insertion; --insertion) {
             std::swap(*tmp, *insertion);
        }
    }
}

(I didn't verify that the algorithm actually works but you get the idea).

Note that the algorithm deliberately sorts the sequence in-place! If you want to create a sorted copy, create the copy and sort that: this way you have the choice to do it in-place or not rather than being forced to use an approach which may require excessive memory (OK, when the sequence is large you surely don't want to use this algorithm but that's a separate question).

Upvotes: 20

user1551592
user1551592

Reputation:

IMO, you should just pass the size as a template parameter and use it in the loop instead of arr.size():

template<class T, size_t size>
array<T, size> insertionSort(array<T> arr) {

    for (int index = 1; index < size; index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}

void main() {
    array<int, 10> mine; mine.fill(0);

    array<int, mine.size()> result = insertionSort<int, mine.size()>(mine);

    cin.get();
}

Upvotes: 3

Nicol Bolas
Nicol Bolas

Reputation: 473427

It works the same way as passing the object without knowing the type up front. You use a template parameter:

template<class T, size_t arrSize>
std::array<T, arrSize> insertionSort(std::array<T, arrSize> arr) {

    for (int index = 1; index < arrSize; index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}

Upvotes: 10

Related Questions