0

I want to write my own is_sorted function template implementation instead of using std::is_sorted. Could you give me any idea about how to do it? I want to use it only for arrays. So I want to make declaration like this: 

template <typename T, size_t N>
bool is_sorted (const T (&array)[N]); and 

bool operator>(const A &, const A &); is declared.
4

2 回答 2

4

显而易见的方法是将每个项目与其后面的项目进行比较，看看它是否 <= 与那个项目。

不过，您可能不想直接这样做。首先，对于排序，客户端通常只需要确保a < b已定义，因此您希望<使用<=. 其次，您希望允许（但不要求）用户传递他们自己的比较器，以防<未直接为某些类型定义或所需的排序使用与<定义不同的标准。

因此，您可能想要定义两个版本is_sorted，一个<直接使用，另一个使用用户传递的比较器。

#include <iterator>
#include <functional>

template <class InIt>
bool is_sorted(InIt b, InIt e) {
    if (b == e)           // No items -- sorted by definition
        return true;

    typename std::iterator_traits<InIt>::value_type first = *b;
    ++b;
    while (b != e) {    // skip if e-b == 1 (single item is sorted)
        if (*b < first)
            return false;
        first = *b;
        ++b;
    }
    return true;
}

template <class InIt, class Cmp>
bool is_sorted(InIt b, InIt e, Cmp cmp) { 
    if (b == e)
        return true;

    typename std::iterator_traits<InIt>::value_type first = *b;
    ++b;
    while (b != e) {    // skip if e-b == 1 (single item is sorte)
        if (cmp(*b, first))
            return false;
        first = *b;
        ++b;
    }
    return true;
}

老实说，一些测试代码，包含已排序、未排序、相同和反转的元素，使用std::vector, std::deque,std::array和内置数组：

#ifdef TEST
#include <array>
#include <vector>
#include <iostream>
#include <deque>

int main() { 
    std::vector<int> sorted{1, 2, 3, 4, 6, 100};
    std::deque<int> unsorted{1, 5, 2, 7, 4};
    std::array<int, 7> ident = {1, 1, 1, 1, 1, 3, 3};
    int rev[] = {5, 4, 3, 2, 1};

    if (!is_sorted(std::begin(sorted), std::end(sorted)))
        std::cout << "Sorted array detected as un-sorted\n";
    if (is_sorted(std::begin(unsorted), std::end(unsorted)))
        std::cout << "Un-sorted array detected as sorted\n";
    if (!is_sorted(std::begin(ident), std::end(ident)))
        std::cout << "sorted array with duplicated detected as un-sorted\n";
    if (!is_sorted(std::begin(rev), std::end(rev), std::greater<int>()))
        std::cout << "Reverse sorted array detected as un-sorted\n";
    return 0;
}
#endif

这对我来说适用于 gcc 4.7.2。该is_sorted代码似乎也可以在 VC++ 2012 中正常工作（尽管测试代码需要进行一些小的修改，例如，以消除它尚不支持的统一初始化的使用）。

编辑：如果您不介意对迭代器有更严格的要求（前向迭代器而不是输入迭代器），您可以使代码更简单且通常更高效。例如，代码可以简化为这样的：

template <class FwdIt>
bool is_sorted(FwdIt b, FwdIt e) {
    if (b == e)           // No items -- sorted by definition
        return true;

    for (FwdIt first = b; ++b != e; first = b) 
        if (*b < *first)
            return false;    
    return true;
}
于 2013-05-14T05:16:50.950 回答
2

确保容器中<=的每个元素都是下一个元素。

如果您只有一个<比较器（像大多数 STL 算法一样），请确保容器中没有给定元素是<前一个元素的元素。

于 2013-05-14T03:47:13.663 回答