如何重載模板函數以匹配特定容器？

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]; 
} 

現在，如果我想用一個雙端隊列（其中也有O(1)實現），將使用O(n)實現調用第一個模板函數。

第二重載功能如何適應vectors和deques？
我的問題摘自this文章。

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，你可以嗅出這個功能是否可用，即使沒有特徵。