2

私は独自のソート アルゴリズムを定義する強力なユース ケースを持っていますO(n)。

これまでのところ問題はありませんが、問題は、いくつかの重要な概念が適用される限り、任意のタイプのコンテナなどにT*適合する汎用インターフェイスを提供したいということです。std::vector<T>

  • コレクションの要素にアクセスできる有効な演算子 [] があります
  • コレクションの要素は、比較可能な「未満」の概念をサポートしています。

アイデアを得るために、ヘッダー ファイルに移動し、 1 つの詳細を除いて探しているものと正確に一致する以下の関数インターフェイスを見つけました。コンテナーを無視し<std_algo.h>て、基になるループをどのように自動ベクトル化するかわかりません。_RandomAccessIteratorタイプして、これが私の質問です...すべてを取得する方法はありますか? 自動ベクトル化 + ジェネリック インターフェイスは基になるコレクション型を無視しますか?

以下のコードは、「非正規」ループ パターンwhile (__last - __first > int(_S_threshold))と条件のために自動ベクトル化されないと思いますif (__depth_limit == 0)が、これは最後のアルゴリズムでは必要ありません。したがって、自動ベクトル化は、非標準タイプのループによって妨げられることがわかります。

template<typename _RandomAccessIterator, typename _Compare> 
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
    _ValueType>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
    {
        std::__introsort_loop(__first, __last,
        std::__lg(__last - __first) * 2, __comp);
        std::__final_insertion_sort(__first, __last, __comp);
    }
}

問題のループは次のようになります。

// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare> 
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
{
    while (__last - __first > int(_S_threshold))
    {
        if (__depth_limit == 0)
        {
            _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
            return;
        }
        --__depth_limit;
        _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
        std::__introsort_loop(__cut, __last, __depth_limit, __comp);
        __last = __cut;
    }
}
4

2 に答える 2

2

標準 C++ ライブラリは、sort() などの標準アルゴリズムで反復子を使用します。これにより、アルゴリズムの実装は、基になるコンテナーの正確な詳細を無視できます。また、このアプローチでは、operator[]().

このことを踏まえて、次の 2 つの提案を検討してください。

operator[]()1)コンテナー内の要素にアクセスするのではなく、反復子を使用するように特殊な並べ替えを修正します。目的の O(n) 速度を維持できる場合、これはおそらく柔軟性の点で最も望ましい方法です。

2) テンプレート化されたコンテナ クラスを使用して並べ替えを実装します。何かのようなもの

template <class Container, class Compare>
void sort(Container cont, Compare comp);

トリックを行う必要があります。

于 2012-07-23T14:49:52.740 に答える
0

テンプレートの素晴らしい点は、テンプレートの型が入力されるまで完全にコンパイルされないことです。そのため、コンパイラは最終的なコードに基づいて最適化を適用できます。ポインターは、ランダム アクセス反復子に必要なすべてのT*プロパティを満たし、それらを必要とする任意のテンプレート コードで簡単に使用できます。

vector<float> v;
// load v
sort(&v[0], &v[v.size()]); // same as sort(v.begin(), v.end()) but possibly optimized better
于 2012-07-23T21:39:48.480 に答える