高效实现 std::vector-like 容器的构造函数

Question

std::vector

有一个构造函数，其形式为

template< class InputIt >
vector( InputIt first, InputIt last,
        const Allocator& alloc = Allocator() );

那么，如果迭代器不是随机访问迭代器，如何实现这个构造函数呢？
我想出了两个候选人...

1. 在循环中，调用

   push_back(*first)

   （假设push_back已经实现），同时first！=last。
2. 通过

   std::distance(first, last)

   ,
   计算元素数量 然后分配足够的内存，然后复制构造所有元素。

哪个更好？或者您还有其他想法吗？

补充：
糟糕的是，如果迭代器是一个 input_iterator，想法 2 甚至是不可能的。

Answer 1

通常的实现是这样的

private:
template<class input_iterator>
std::size_t size_if_possible(input_iterator first, input_iterator last, std::input_iterator_tag) {
}
template<class input_iterator>
std::size_t size_if_possible(input_iterator first, input_iterator last, std::forward_iterator_tag) {
    return std::distance(first, last);
}

public:
template<class input_iterator>
vector(input_iterator first, input_iterator last) {
    reserve(size_if_possible(first, last, std::iterator_traits<input_iterator>::tag{}));
    while (first != last) {
        emplace_back(*first);
        first++;
    }
}

这允许它在您传入前向迭代器时进行保留，并在您传入单遍输入迭代器时有效地跳过保留，从而为您提供两全其美的效果。