C++迭代器 - 为什么我必须添加.begin()来获得二进制搜索中间点？

Question

如果我尝试编译以下代码,则会出错:

  vector<string> articles;

  articles.push_back("Article 1...");
  articles.push_back("Article 2...");
  articles.push_back("Article 3...");
  articles.push_back("Article 4...");

  vector<string>::iterator beg = articles.begin(), end = articles.end();
  vector<string>::iterator mid = (end - beg) / 2;

并且只有在我改为mid时编译:

  vector<string>::iterator mid = articles.begin() + (end - beg) / 2;

.begin()初始化有什么变化？

此外,以下代码不应该给出中间点吗？(添加了.begin(),因为没有它就不能编译)

  vector<string>::iterator mid = articles.begin() + articles.size() / 2;

它给出了相同的结果.

谢谢.

Answer 1

end - beg给你的距离之间的beg和end.它是一个数字,而不是迭代器.然后你将它除以2得到那个距离的一半.然后你必须将该距离转换回迭代器.为此你添加它beg

mid = beg + (end - beg) / 2

例如,如果您的向量中包含10个元素,那么(end - beg) / 2将评估为5.现在你必须创建一个指向向量中第5个元素的迭代器.这是完成的beg + 5.

当你说通过将向量的大小的一半添加到向量的开始迭代器时可以获得相同的结果时,你是对的.然而,正如你自己所说的那样,这是迭代二进制搜索算法的一部分,这意味着它必须mid在每次迭代二进制搜索时计算beg并且end不再指向原始向量的开始和结束.这就是为什么beg + (end - beg) / 2公式是计算中间迭代器的更通用的方法.