c++ - 测试容器是否实现 .at() 成员访问/std::sort 兼容的正确方法

Question

我正在寻找确定容器是否通过 .at() 实现随机元素访问的最佳/正确方法.在不同 (STL) 容器相对于彼此排序的场景中(比如排序容器 std::vector<int> ，相对于 std::vector<double> )，我这样做:

std::sort(toOrder.begin(), toOrder.end(), [&orderBy](int i, int j) -> bool {
    return orderBy.at(i) > orderBy.at(j);
});

在哪里

std::vector<int> toOrder;
std::vector<double> orderBy

我可以将其包装在模板函数中，但我不确定限制或测试具有随机访问迭代器/.at() 的容器的最佳方法(如果没有，则需要做一些昂贵的事情).

我有这个

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

template <typename T, typename U>
void sorty(T& a, U const x) {
    std::sort(a.begin(), a.end(),
              [&x](int i, int j) -> bool { return x.at(i) > x.at(j); });
}

int main() {

    std::vector<int> toOrder(10);
    std::iota(toOrder.begin(), toOrder.end(), 0);
    std::vector<double> orderBy{0.2, 9.8,  4.0,  0.01,  15.1,
                                3.3, 9.01, 9.11, 100.1, 2.03};

    std::unordered_set<double> orderBy_s(orderBy.begin(),
                                         orderBy.end()); // no .at()

    sorty(toOrder, orderBy);

    for (auto i : toOrder) {
        std::cout << i << "\t";
    }

    return 0;
}

演示代码here

更新: 我没有编辑标题就匆忙发布了。我关心任何 容器类型，而不仅仅是 STL。为了方便和可重现性，我的示例使用了 STL 容器。

Answer 1

基本上，这不是通用 algorithms 的正确方法。应该实现。通常，人们会使用 iterator s和 std::iterator_traits 以确定基础类型和允许的操作。如果您想根据容器提供的接口(interface)(随机访问、非随机访问)执行不同的算法(具有不同的复杂度)，您应该执行以下操作。

首先，您的通用算法应该在范围 而不是容器 上运行。也就是说，这应该类似于 <algorithm> 中的任何一个。的功能:

template <typename Iterator>
void sorty(Iterator first, Iterator last);

其次，您应该编写应用不同排序方法的辅助函数，以尽可能利用容器的接口(interface)，以最有效的方式工作:

// O(N*lgN) complexity sorting
template <typename Iterator>
void sorty_helper(Iterator first, Iterator last,
                  std::random_access_iterator_tag);

// O(N*N) complexity sorting
template <typename Iterator>
void sorty_helper(Iterator first, Iterator last,
                  std::forward_iterator_tag);

现在，您的原始 sorty函数实际上应该只将迭代器转发到适当的辅助函数，基于通过 std::iterator_traits 获得的迭代器类型:

template <typename Iterator>
void sorty(Iterator first, Iterator last)
{
    sorty_helper(first, last,
                 typename std::iterator_traits<Iterator>::iterator_category());
}

DEMO 1

另一种方法是使用 SFINAE 技术启用/禁用函数模板:

#include <iterator>
#include <type_traits>    

template <typename Iterator>
typename std::enable_if<
    std::is_same<typename std::iterator_traits<Iterator>::iterator_category, std::random_access_iterator_tag>::value
    >::type
    sorty(Iterator first, Iterator last)
{
    // O(N*lgN) complexity sorting
}

template <typename T> struct AlwaysFalse : std::false_type {};

template <typename Iterator>
typename std::enable_if<
    !std::is_same<typename std::iterator_traits<Iterator>::iterator_category, std::random_access_iterator_tag>::value
    >::type
    sorty(Iterator first, Iterator last)
{
    // other sorting algorithm or print out a user-friendly error
    static_assert(AlwaysFalse<Iterator>{}, "Iterator must be a random-access iterator!");
}

DEMO 2

在哪里enable_if和 is_same是 C++11 的类型特征，在 C++03 中可以定义如下:

template <bool b, typename T = void>
struct enable_if {};
template <typename T>
struct enable_if<true, T> { typedef T type; };
template <typename T, typename U>
struct is_same { static const bool value = false; };
template <typename T, typename U>
const bool is_same<T, U>::value;
template <typename T>
struct is_same<T, T> { static const bool value = true; };
template <typename T>
const bool is_same<T, T>::value;

另一方面，如果您只想检查 at 是否存在成员函数，并据此做出编译时决策，您可能需要使用表达式 SFINAE 技术:

template <typename Container>
auto sorty_helper(Container&& container, int)
    -> decltype(void(std::forward<Container>(container).at(0)))
{
    // O(N*lgN) complexity sorting
}

template <typename Container>
void sorty_helper(Container&& container, void*)
{
    // O(N*N) complexity sorting
}

template <typename Container>
void sorty(Container&& container)
{
    sorty_helper(std::forward<Container>(container), 0);
}

DEMO 3

在C++03中，验证给定签名的成员函数是否存在需要手写特征:

template <typename T>
struct has_at
{
    typedef char (&yes)[1];
    typedef char (&no)[2];

    template <typename U, U u>
    struct SFINAE {};

    template <typename U>
    static yes test(SFINAE<typename U::reference(U::*)(std::size_t), &U::at>*);

    template <typename U>
    static no test(...);

    static const bool value = sizeof(test<T>(0)) == sizeof(yes);
};

可与 enable_if 结合使用:

template <bool b, typename T = void>
struct enable_if {};

template <typename T>
struct enable_if<true, T> { typedef T type; };

template <typename Container>
typename enable_if<has_at<Container>::value>::type
    sorty(Container& container)
{
    // O(N*lgN) complexity sorting
}

template <typename Container>
typename enable_if<!has_at<Container>::value>::type
    sorty(Container& container)
{
    // O(N*N) complexity sorting
}

DEMO 4