1 
template<typename T>
void Merge_Sort(vector<T>::iterator begin, vector<T>::iterator end) {

size_t length = end - begin;
if (1 >= length) return;

size_t mid = length/2;

Merge_Sort(begin, begin + mid);
Merge_Sort(begin + mid, end);
inplace_merge(begin, begin + mid, end);
}

関数をテンプレート化しようとしていますが、vector::iterator の前に typename がないというエラーが表示されます。この関数テンプレートを作成することについて、誰かアイデアをお持ちですか?

要約すると、イテレータ パラメータをテンプレートとして作成しようとしています。

4

3 に答える 3

5

std::distance, std::next(または c++03 では std::advance) を使用して計算を行う必要があります。

また、ハードコーディングは一般的なvectorものにするのとは正反対です、IYAM

template<typename It>
void Merge_Sort(It begin, It end) {
    size_t length = std::distance(begin, end);
    if (1 >= length) return;

    size_t mid = length/2;

    auto pivot = std::next(begin, mid);

    Merge_Sort(begin, pivot);
    Merge_Sort(pivot, end);
    inplace_merge(begin, pivot, end);
}

完全を期すために、比較述語を統合し、 Coliru でライブで降順にソートするものを次に示します。

#include <algorithm>
#include <vector>
#include <iterator>

template<typename It, 
    typename Cmp = typename std::less<typename std::iterator_traits<It>::value_type> >
void Merge_Sort(It begin, It end, Cmp cmp = Cmp()) {
    size_t length = std::distance(begin, end);
    if (length<2) return;

    size_t mid = length/2;

    auto pivot = std::next(begin, mid);

    Merge_Sort(begin, pivot, cmp);
    Merge_Sort(pivot, end, cmp);
    std::inplace_merge(begin, pivot, end, cmp);
}

#include <iostream>

int main()
{
    std::vector<int> v { 1,3,7,-3,4,99,-13 };

    Merge_Sort(begin(v), end(v), std::greater<int>());

    for(auto i : v)
        std::cout << i << " ";
}
于 2013-08-08T23:50:53.367 に答える
1

私はこれを打ち出しただけではありません。古いソースファイルにありましたが、これがあなたがやろうとしていたことだと思います。固定配列と指定された長さの任意のベース ポインターを並べ替えるための 2 つのインターフェイスを追加しました。それが役に立てば幸い：

#include <iterator>
#include <algorithm>

// general mergesort algorithm
template <
  typename Iterator,
  typename Compare=std::less<typename std::iterator_traits<Iterator>::value_type>
>
void mergesort(Iterator first, Iterator last, const Compare& cmp=Compare())
{
    size_t n = std::distance(first, last)/2;
    if (n == 0)
        return;

    Iterator mid = std::next(first, n);
    mergesort(first, mid, cmp);
    mergesort(mid, last, cmp);
    std::inplace_merge(first, mid, last, cmp);
}

// front-loader for static arrays
template<typename Item, size_t N>
void mergesort(Item (&ar)[N])
{
    mergesort(std::begin(ar), std::end(ar));
}

// front-loader for size-specified base-pointer arrays
template<typename Item>
void mergesort(Item *ptr, size_t N)
{
    mergesort(ptr, ptr+N);
}
于 2013-08-08T23:50:40.517 に答える
1

vector::iterator の前に typename がないというエラーが表示される

typenameエラーが示すように、前に行方不明ですvector<T>::iterator：

void Merge_Sort(typename vector<T>::iterator begin, typename vector<T>::iterator end)
                ^^^^^^^^                            ^^^^^^^^

これは、依存型名を指定するときに必要です。テンプレート引数に依存する、テンプレートにネストされた型の名前です。テンプレートがインスタンス化されるまで、コンパイラは名前が何を表しているか分からないため、型の名前を指定する必要があります。

要約すると、イテレータ パラメータをテンプレートとして作成しようとしています。

次に、それを行う方が良いかもしれません：

template <typename Iter>
void Merge_Sort(Iter begin, Iter end);
于 2013-08-08T23:52:06.537 に答える