如何检查传递的迭代器是否为随机访问迭代器？

Question

我有以下代码，它执行一些迭代器算术操作：

template<class Iterator>
void Foo(Iterator first, Iterator last) {
  typedef typename Iterator::value_type Value;
  std::vector<Value> vec;
  vec.resize(last - first);
  // ...
}

(last - first) 的表达式（据我所知）仅适用于随机访问迭代器（例如来自 vector 和 deque 的迭代器）。如何在代码中检查传递的迭代器是否满足此要求？

- Frank

---

您可以使用 distance(first, last) 来避免完全进行检查。 - Fred Larson

这可能适用于您特定的用例，但通常情况下，您不能依赖“随机访问”标记来表示迭代器指向的内存是连续的。请查看Microsoft的concurrent_vector类的文档。随机访问仅意味着您具有[]运算符，迭代器可以理解。此外，如何处理反向迭代器（它们是随机访问的）？我有一个类似的问题，我在这里发布了寻找答案：过滤迭代器 - Kent Knox

@KentKnox：谁说内存必须是连续的了？last-first适用于所有随机访问迭代器，包括std::deque::iterator，它绝对不指向连续的内存。 - Mooing Duck

Answer 1

如果Iterator是随机访问迭代器，则

std::iterator_traits<Iterator>::iterator_category

将会是std::random_access_iterator_tag。最干净的实现方式可能是创建第二个函数模板，然后让Foo调用它：

将会是std::random_access_iterator_tag。实现的最佳方式可能是创建另一个函数模板，然后由Foo调用它：

template <typename Iterator>
void FooImpl(Iterator first, Iterator last, std::random_access_iterator_tag) { 
    // ...
}

template <typename Iterator>
void Foo(Iterator first, Iterator last) {
    typedef typename std::iterator_traits<Iterator>::iterator_category category;
    return FooImpl(first, last, category());
}

这样做的优点是，如果需要，您可以为不同类型的迭代器重载 FooImpl。

Scott Meyers 在其中一本《Effective C ++》书中讨论了这种技术（我不记得是哪一本）。

- James McNellis

---

确实，这正是我正在查看的g++实现（4.3.2版本）中std::distance所使用的技术。 - Fred Larson

@Fred 和 std::advance() 也是。 - wilhelmtell

其他选项包括(a)添加一个无操作能力检查（例如first + 0;），(b)使用显式模板特化，或(c)使用SFINAE进行重载。然而，我认为这些选项都不如标签分派方法干净或直接。 - James McNellis

Answer 2

除了标签分派之外，您还可以使用std::is_same_v将类别直接与std::random_access_iterator_tag进行比较：

using category = typename std::iterator_traits<Iterator>::iterator_category;
if constexpr (std::is_same_v<category, std::random_access_iterator_tag>) {
  vec.resize(last - first);
}

如果只有实现的一小部分（例如保留向量大小）依赖于迭代器类别，则这有时会导致更清晰简洁的代码。

- vitaut

---

如果非随机访问迭代器会导致错误，可以使用static_assert。此外，我建议使用std::is_convertible_v而不是std::is_same_v，因为前者允许一些未来版本的C++通过继承拥有另一个也是std::random_access_iterator_tag类型标签的可能性。迭代器标签已经使用继承来表达is-a关系。 - Araeos

我肯定更喜欢这个答案，因为当我寻找这个答案时，我想使用它的主要原因是微优化，以确定是否可以便宜地计算要在vector中reserve（甚至不是resize）的大小，对于任何前向迭代器都可以正常工作的算法。如果我只是依赖摊销增长，就不必遍历两次，一次计算reserve大小，然后再基于它填充vector，这样做会很麻烦。将那个单行代码分解成一个全新的函数将是一种痛苦。 - ShadowRanger

@Araeos，你对继承的理解是正确的，但为什么不使用std::is_base_of_v<RequiredTag, ActualTag>呢？这更清晰地表明标签使用继承来建立层次结构，而不仅仅是可转换性。 - underscore_d