采用迭代器的类型安全模板函数

Question

我正在编写不同的排序函数，它需要两个迭代器和排序序列。我想为任何类型的向量实现它们并使其类型安全，如下所示：

template <typename T>
void itsort(std::vector<T>::iterator begin, std::vector<T>::iterator end)
{
    // code
}

但是由于错误，我只能实现一些类型不安全的东西：

template <typename T>
void itsort(T begin, T end)
{
    // code
}

如何实现类型安全的模板函数，它需要两个向量迭代器？

PS：目前不需要比较器，所有类型都适用于不同类型的数字。

Answer 1

确定某个东西是否是向量的迭代器很困难，而且大多毫无意义。

向量迭代器的类型在标准下是极其自由的。 在某些实现中它们甚至可以是裸指针。

更重要的是，产生迭代器的向量的类型可能无法从迭代器推导出。 例如，

std::vector<int, some_allocator>::iterator

可能与

std::vector<int>::iterator

是不同或相同的类型。 它们可能都是

int*

，或者它们可能是包裹在指针周围的某个类。 它们可以是相同类型，也可以是不同类型。 （如果您想找到有关它的讨论，则对不同容器类型使用相同类型的技术称为 SCARY 迭代器）。

一般来说，你无法确定给定的迭代器是否是向量迭代器。

如果给定的迭代器不是随机访问迭代器，您可以编写将失败的代码，并推导出类型

T

。 首先，一些样板代码可以让访问

iterator_traits

变得不那么冗长：

namespace iterators {
  template<class It>
  using iterator_category =
    typename std::iterator_traits<It>::iterator_category;

  template<class It>
  using value_type =
    typename std::iterator_traits<It>::value_type;
}

现在我们这样做：

template<class It>
void itsort(It begin, It end)
{
  using T = iterator::value_type<It>;
  using category = iterator::iterator_category<It>;
  static_assert(
    std::is_base_of<std::random_access_iterator_tag, category>::value, "This function only supports random-access iterators"
  );
}

此“失败较晚”，因为错误不会在重载解析 (SFINAE) 时发生，但它会为您检查类型。

您还可以访问迭代器的基础值类型。

以 SFINAE 友好的方式执行此操作很困难，因为

iterator_traits

不强制要求 SFINAE 友好，而

iterator_traits

是确定迭代器特征的强制方法。 作为一个具体的例子，

void*

通常会匹配空的

iterator_traits

作为指针，但随后它会失败，因为它不是迭代器。

Answer 2

似乎你正在寻找这样的东西：

#include <iostream>
#include <vector>
#include <list>
#include <iterator>

template< typename T >
void itsort(T, T, std::bidirectional_iterator_tag)
{
    std::cout << "itsort called for bidirectional iterator\n";
}

template <typename T>
void itsort(T, T, std::random_access_iterator_tag)
{
    std::cout << "itsort called for random-access iterator\n";
}


template< typename T >
void alg(T first, T last)
{
   itsort(first, last, typename std::iterator_traits<T>::iterator_category());
}


int main()
{
    std::vector<int> v;
    alg(v.begin(), v.end());

    std::list<int> l;
    alg(l.begin(), l.end());
}

Answer 3

可以使用

std::enable_if

类型特征来约束函数，仅当指定类型是

type

容器迭代器时，该特征才定义有效的

std::vector

。

此时，有必要实现一个专用的类型特征（

is_vector_iterator

）来实现这一目标。

示例：

template <typename InIter, typename = typename std::enable_if<is_vector_iterator<InIter>::value>::type>
void itsort(InIter, InIter);

基本思想是创建一个辅助类型特征，它接受两种不同的类型作为模板参数。它是部分特化的，用于第二个参数与

std::vector <U>::iterator

相同的情况，其中类型

U

是迭代器的 value_type。因此，助手仅专门针对

T

类型。如果上述类型不是

std::vector

容器迭代器，则选择第一个类；否则，选择第二个。

示例：

namespace detail {
    template <typename, typename>
    struct is_vector_iterator
     : public std::false_type {};
    
    template <typename T>
    struct is_vector_iterator<T, typename std::vector<typename std::iterator_traits<T>::value_type>::iterator>
     : public std::true_type {};
}

template <typename T>
struct is_vector_iterator
 : public detail::is_vector_iterator<T, T> {};