你如何传递std :: array？

Question

我正在尝试这样简单的事情:

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

好像数组需要两个类型参数(type以及它size),所以我如何在不知道前面的大小的情况下将它传递给函数？

Answer 1

一般来说,你真的不想传递容器!std::array<T, N>适用于其他数据结构的相同算法,例如,std::vector<T>或std::deque<T>.在这种情况下,C++方法是传递迭代器并[稍微]调整算法:

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

(我没有验证算法是否真的有效,但你明白了).

请注意,算法会故意对序列进行排序!如果要创建排序副本,请创建副本并对其进行排序:这样您就可以选择是否就地执行此操作而不是强制使用可能需要过多内存的方法(好的,当序列为大,你肯定不想使用这个算法,但这是一个单独的问题).

Answer 2

它的工作方式与传递对象的方式相同,但不知道前面的类型.您使用模板参数:

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