C++中两个迭代器间的数学运算机制详解（含代码示例）

一、迭代器相减的结果是什么？ #

你的代码里，find返回的迭代器减去inorder.begin()，得到的是目标元素在vector中的下标位置（或者说两个迭代器之间的元素个数差）。
比如你的inorder数组是{4, 2, 7, 5, 8, 1, 3, 9, 6}，元素1是第6个元素（从0开始计数的话下标是5），所以这个减法的结果就是5。

二、为什么要执行这个减法？ #

这段代码是典型的二叉树前序+中序遍历重构场景：

• preorder[0]是二叉树的根节点（前序遍历第一个元素即为根）
• 在inorder里找到根节点的位置后，这个位置mid把inorder分成两部分：[inorder.begin(), inorder.begin()+mid)是左子树的所有节点，[inorder.begin()+mid+1, inorder.end())是右子树的所有节点
• mid的数值同时也是左子树的节点总数，后续可以用它分割preorder数组，取出左、右子树的前序遍历序列，递归构建整个二叉树。

三、迭代器间数学运算的原理 #

只有随机访问迭代器（比如vector、array、deque的迭代器）支持减法运算，核心原因是：

• 这类容器的元素在内存中连续存储，迭代器底层实现和指针几乎一致
• 两个随机访问迭代器相减，本质和指针相减逻辑相同：先计算内存地址的字节差，再除以单个元素的字节大小，最终得到两个迭代器之间的元素个数差。

注意：像list、forward_list这类容器的迭代器属于双向/单向迭代器，不支持减法运算——因为它们的元素不是连续存储的，无法直接计算两个迭代器间的距离。

代码示例 #

vector<int> preorder {1, 2, 4, 5, 7, 8, 3, 6, 9};
vector<int> inorder {4, 2, 7, 5, 8, 1, 3, 9, 6};
auto mid = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();

内容的提问来源于stack exchange，提问作者Sudhanshu Tiwari