How do you pass a std::array?

Question

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?

Answer 1

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).