2014-11に記述,stable_sortの独自実装

stable_sort.cpp

// -*- flycheck-clang-language-standard : "c++14"; -*-
// clang++ -std=c++14 -stdlib=libc++
// clang version 3.5.0 (tags/RELEASE_350/final)

#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>

namespace reinvention
{
    template<typename I, typename O, typename Compare = std::less<typename std::iterator_traits<I>::value_type>>
        constexpr void merge(const I left_begin, const I left_end, const I right_begin, const I right_end, const O output, const Compare pred)
    {
        if(left_begin != left_end)
        {
            if(right_begin != right_end)
            {
                if(pred(*left_begin, *right_begin))
                {
                    *output = *left_begin;
                    reinvention::merge(left_begin + 1, left_end, right_begin, right_end, output + 1, pred);
                }
                else
                {
                    *output = *right_begin;
                    reinvention::merge(left_begin, left_end, right_begin + 1, right_end, output + 1, pred);
                }
            }
            else
            {
                *output = *left_begin;
                reinvention::merge(left_begin + 1, left_end, right_begin, right_end, output + 1, pred);
            }
        }
        else
        {
            if(right_begin != right_end)
            {
                *output = *right_begin;
                reinvention::merge(left_begin, left_end, right_begin + 1, right_end, output + 1, pred);
            }
        }
    }

    template<typename I, typename O, typename Compare = std::less<typename std::iterator_traits<I>::value_type>, typename Difference_type>
    constexpr void help_stable_sort(const I begin, const I end, const O output, const Compare pred, const Difference_type length)
    {
        using T = typename std::iterator_traits<I>::value_type;
        switch(length)
        {
        case 0:
            break;
        case 1:
            *output = *begin;
            break;
        case 2:
            if(pred(*begin, *(begin + 1)))
            {
                *output       = *(begin);
                *(output + 1) = *(begin + 1);
            }
            else
            {
                *output       = *(begin + 1);
                *(output + 1) = *(begin);
            }
            break;
        default:
            const auto left_length  = (length)     / 2;
            const auto right_length = (length + 1) / 2;

            std::vector<T> left (left_length);
            std::vector<T> right(right_length);
            reinvention::help_stable_sort(begin, end - right_length, left.begin(), pred, left_length);
            reinvention::help_stable_sort(begin + left_length, end, right.begin(), pred, right_length);
            reinvention::merge(left.begin(), left.end(), right.begin(), right.end(), output, pred);
        }
    }

    template<typename I, typename O, typename Compare = std::less_equal<typename std::iterator_traits<I>::value_type>>
        constexpr void stable_sort(I begin, I end, O output, const Compare pred = Compare())
    {
        if(begin == output)
        {
            throw std::exception();
        }
        const auto length = std::distance(begin, end);
        reinvention::help_stable_sort(begin, end, output, pred, length);
    }
}

int main()
{
    constexpr std::size_t max_length = 10;
    const std::size_t digit = std::ceil(std::log10(max_length) + 1);

    std::array<double, max_length> sec;
    std::for_each(sec.begin(), sec.end(), [](double& x){std::cin >> x;});

    using record = std::pair<std::size_t, double>;
    std::array<record, max_length> indexed_sec;

    for(size_t i = 0; i < sec.size(); ++i)
    {
        indexed_sec.at(i) = std::make_pair(i, sec.at(i));
    }

    std::array<record, max_length> ordered_indexed_sec;
    reinvention::stable_sort(indexed_sec.begin(), indexed_sec.end(), ordered_indexed_sec.begin(),
                             [](const record& a, const record& b)
                             {
                                 return a.second <= b.second;
                             }
        );

    std::array<double, max_length> ord;

    for(size_t i = 0; i < ordered_indexed_sec.size(); ++i)
    {
        ord.at(ordered_indexed_sec.at(i).first) = i;
    }

    for(size_t i = 0; i < ord.size(); ++i)
    {
        std::cout << std::setw(digit) << i + 1 << "番のプレイヤーは" <<
            std::setw(digit) << ord.at(i) + 1 << "位でした." <<
            std::endl;
    }

    std::cout << std::endl;

    for(size_t i = 0; i < ordered_indexed_sec.size(); ++i)
    {
        std::cout << std::setw(digit) << i + 1 << "位のプレイヤーは" <<
            std::setw(digit) << ordered_indexed_sec.at(i).first + 1 << "番でした,スコアは" <<
            std::fixed << ordered_indexed_sec.at(i).second << "秒でした." <<
            std::endl;
    }
}