为何template<class InputIt> deque::deque迭代器构造函数性能欠佳？

这个问题问到点子上了，我们从迭代器特性、标准要求和实现权衡三个角度来拆解：

1. 两次扫描的直接原因：迭代器类型的限制 #

std::list的迭代器属于双向迭代器（Bidirectional Iterator），而非随机访问迭代器（Random Access Iterator）。对于随机访问迭代器（比如std::vector的迭代器），std::distance()可以在O(1)时间内算出两个迭代器之间的元素数量；但双向迭代器不行，std::distance()只能通过逐个遍历的方式计数——这就是第一次扫描的由来。

而std::deque的范围构造函数，为了避免频繁扩容带来的开销，会先尝试获取元素总数：

• 如果是随机访问迭代器，直接O(1)拿到数量，一次性准备好合适的分段缓冲区（deque的内存是分段式的），再复制元素；
• 如果是双向/输入迭代器，就只能先调用std::distance()遍历一遍计数（第一次扫描），再遍历一遍复制元素（第二次扫描）。

2. 这不是C++标准的固有缺陷 #

C++标准并没有强制要求必须做两次扫描，它只规定了构造函数的最终行为：把[first, last)范围内的元素复制到deque中。

理论上，实现可以针对双向迭代器做优化——比如一边遍历元素一边插入到deque中，这样只需要一次扫描。但主流库（libstdc++、libc++）没这么做，是实现层面的性能权衡：
deque的逐个插入会触发多次缓冲区扩容（虽然deque的扩容比vector高效，但仍有开销），而预先知道元素总数后，实现可以一次性分配足够的分段缓冲区，减少内存分配和数据移动的次数，整体效率反而更高。所以两次遍历是为了换取更低的内存开销，是一种取舍选择。

你可能会好奇：C++11之后std::list的size()是O(1)的，为什么实现不直接用list.size()代替std::distance()？
答案是：deque的范围构造函数是通用模板，它接受任意类型的输入迭代器，实现无法直接判断传入的迭代器是否来自std::list。除非专门为std::list的迭代器做模板特化，但标准并没有要求这么做，主流库目前也没有添加这个特化优化。

3. 手动绕过两次扫描的方法 #

如果你想避免两次扫描，可以手动利用list的O(1) size()来预先分配deque空间，再复制元素：

std::list<int> v = {4, 3, 2, 1};
std::deque<int> d;
d.resize(v.size());
std::copy(v.begin(), v.end(), d.begin());

这样只需要一次遍历复制，就能达到同样的效果。

内容的提问来源于stack exchange，提问作者Alexandr Konovalov