如何重载模板函数以匹配特定容器？

Question

我有以下函数来检索n容器的元素 - O(n):

template<typename Container>
const typename Container::value_type& getNthElement(const Container& container, size_t n) {
    auto itr = cbegin(container);
    for (auto i = 0u; i < n; ++i) {
        ++itr;
    }
    return *itr;
}

因为vectors我有这个超载 - O(1):

template<typename T>
T getNthElement(const vector<T>& container, size_t n) {
    return container[n];
}

现在,如果我想使用deque(也有O(1)实现),将使用O(n)实现调用第一个模板函数.

第二个过载功能如何适应vectors和deques？
我的问题来自这篇文章.

Answer 1

简单的方法是基于迭代器类别标记dipatch,即,像这样:

template <typename It>
typename std::iterator_traits<It>::value_type
nth_element(It begin, It end, std::size_t n, std::input_iterator_tag) {
    for (std::size_t i(0); it != end && i != n; ++i) {
        ++i;
    }
    return it != end? *it: throw std::runtime_error("out of range");
}
template <typename It>
typename std::iterator_traits<It>::value_type
nth_element(It begin, It end, std::size_t n, std::random_access_iterator_tag) {
    return n < std::size_t(end - begin)? it[n]: std::runtime_error("out of range");
}
template <typename C>
typename C::value_type
nth_element(Container const& c, std::size_t n) {
    return nth_element(c.begin(), c.end(), n,
                       typename std::iterator_traits<C>::iterator_category());
}

如果不是因为n可能太大,你实际上可以std::advance()做到这一点:

template <typename C>
typename C::value_type
nth_element(Container const& c, std::size_t n) {
    auto it = c.begin();
    std::advance(it, n);
    return *it;
}

使用C++ 11扩展SFINAE,即使没有特征,您也可以嗅出这种功能是否可用.