読者です 読者をやめる 読者になる 読者になる

C++11でstaticな関数群を抽象化するための設計メモ

C++

C++を始めて3週間くらいになります.gccのエラーを読むのがしんどいです.そろそろTBBを使いたい.


前回(http://qiita.com/items/16532cbb20ce15e622ed) のSorterクラスの設計を少しまともにしてみた.


http://github.com/y-uuki/cpp-sorter


やったこと

  • Template展開によりint型以外のデータ型に対応した.
  • std::greater<>()などのプレディケートを指定できるようにした.
  • 関数テンプレートのデフォルト引数(C++11)により,デフォルトのプレディケートのstd::less<>()にした.
  • ソートに状態とかいらないし,抽象クラスによる抽象化をやめて代わりに,名前空間 namespace mysorter内にstatic関数をおくだけにした.
呼び出し側コード
int main() {
    std::vector<int> a = {30, 40, 10, 70, 20, 90, 50, 60, 80};
    std::cout << "original:\n";
    print(a);

    std::cout << "heap_sort:\n";
    auto g(a);
    mysorter::heap_sort(g.begin(), g.end(), std::greater<>);
    print(g);

    return 0;
}
実装側コード
/////////// Heap Sort ///////////
namespace _impl_hsort {

    template <
        class RandomAccessIterator,
        class Predicate = std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >
    >
    static void heapify(RandomAccessIterator first, RandomAccessIterator last, const RandomAccessIterator idx, const Predicate pred)
    {
        auto const left = first + 2 * std::distance(first, idx) + 1;
        auto const right = first + 2 * std::distance(first, idx) + 2;
        auto largest = idx; // largest or smallest

        if (left < last and pred(*idx, *left)) {
            largest = left;
        }

        if (right < last and pred(*largest, *right)) {
            largest = right;
        }

        if (largest != idx) {
            std::iter_swap(idx, largest);
            heapify(first, last, largest, pred);
        }
    }

    template <
        class RandomAccessIterator,
        class Predicate = std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >
    >
    static void build_heap(RandomAccessIterator first, RandomAccessIterator last, const Predicate pred)
    {
        const size_t n = std::distance(first, last);
        for (auto it = std::next(first, n/2 - 1); it >= first; --it) {
            heapify(first, last, it, pred);
        }
    }

}

template <
    class RandomAccessIterator,
    class Predicate = std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >
>
static void heap_sort(RandomAccessIterator first, RandomAccessIterator last,
        const Predicate pred = std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >())
{
    _impl_hsort::build_heap<RandomAccessIterator, Predicate>(first, last, pred);
    for (auto it = last - 1; it > first; --it) {
        std::iter_swap(first, it); // move largest value to a part of sorted array
        _impl_hsort::heapify<RandomAccessIterator, Predicate>(first, it, first, pred); // first becomes largest
    }
}

```

課題

現状の実装だと,テストコードを書くときに各ソートアルゴリズムごとに同一入力のテストを書かなければならないし冗長になる,
そこで,(C++11 (他) 入門) に書かれているTag Dispatchで抽象化したい.

traitで型を取得するためのイディオムが長いし,もう少しなんとかならないものか.
typename std::iterator_traits::value_type