8

私は次のような簡単なことを試していました：

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

配列には 2 つの型パラメーター ( とtype)が必要なsizeようですが、事前にサイズを知らずに関数との間で渡すにはどうすればよいでしょうか?

4

3 に答える 3

20

一般に、コンテナーを渡したいとは思いません。で機能する同じアルゴリズムが、や などstd::array<T, N>の他のデータ構造でも機能します。その場合の C++ のアプローチは、反復子を渡し、アルゴリズムを [わずかに] 調整することです。std::vector<T>std::deque<T>

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

（アルゴリズムが実際に機能することは確認していませんが、アイデアはわかります）。

アルゴリズムは意図的にその場でシーケンスをソートすることに注意してください! ソートされたコピーを作成する場合は、コピーを作成してソートします。この方法では、過剰なメモリを必要とする可能性のあるアプローチを使用することを余儀なくされるのではなく、インプレースで実行するかどうかを選択できます (OK、シーケンスが大規模な場合、このアルゴリズムを使用したくないことは確かですが、それは別の問題です)。

于 2013-08-28T02:08:07.787 に答える
10

事前にタイプを知らずにオブジェクトを渡すのと同じように機能します。テンプレート パラメータを使用します。

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;
}
于 2013-08-28T01:56:29.473 に答える
3

IMO、テンプレート パラメーターとしてサイズを渡し、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();
}
于 2013-08-28T01:58:09.307 に答える