在中间访问std::list

Question

我有一个基础问题。我一直读到C++的 std::list容器在插入元素时，无论是在开头、结尾还是中间，都具有常数时间： 那么在 std::list中直接将一个元素插入到中间位置，应该如何操作？ 是这样吗？

  std::list<int> l;
  l.push_back(10);
  l.push_back(20);
  l.push_back(30);
  l.push_back(40);
  l.push_back(50);
  l.push_back(60);
  l.insert( l.end()- l.begin() /2 ); //? is this 
  // inserting directly in the middle?

当我们说“在中间插入”时，我们是否真的意味着我们节省了线性时间，以便从列表开头到达所需点（通过遍历所有中间链接元素逐个进行）？

- Abruzzo Forte e Gentile

---

他们并不是指确切的中间位置，只是相对于开头或结尾的其他位置。 - Vaughn Cato

嗨，Vaughn！感谢澄清……我越做这份工作，就越觉得现在是时候开始阅读一些好的老式冒险小说了……放松一下，不要过于关注严格的含义。干杯！AFG - Abruzzo Forte e Gentile

Answer 1

你可以像这样通用地进行迭代器数学计算：

 std::list<int>::iterator it = l.begin();
 std::advance(it, std::distance(l.begin(), l.end())/2);
 l.insert(it, value);

这将适用于任何迭代器类型（除了OutputIterator或InputIterator）

当然，明显更加高效的做法是

 std::advance(it, l.size()/2);
 l.insert(it, value);

很遗憾，l.insert(l.begin + (l.size()/2), value)不能工作，因为列表迭代器不是随机访问的，因此没有定义operator+（以防止性能问题！）。请记住，std::advance()可能是一种昂贵的操作，具体取决于迭代器类型（例如，在仅向前容器上实现反向迭代器时它将变得缓慢）。

- sehe

---

实际上，对于std::list来说，.size()版本并不比其他版本更高效。它们的效率大致相同，只是在输入时可以节省一些标记。 - jpalecek

在C++11中，它的效率要更高，时间复杂度为常数级别，而在C++03中，size()的时间复杂度是依赖于具体实现的，但distance()基本上必须是线性的。 - Mike Seymour

@MikeSeymour：啊，谢谢你的解释！看起来在C++03中是一样的，但在原始的SGI STL中不同（而后者要求splice是常数时间）。 - jpalecek

Answer 2

这里的“中间”指的是列表中的任意点，只要您已经有一个引用该点的迭代器。因此，插入只是在插入点周围修改一些指针的问题。

如果您没有插入点的迭代器，并且它不像开头或结尾那样简单，则需要线性时间遍历列表以找到它。

- Mike Seymour

Answer 3

当我们说“在中间插入”时，我们真正意味着节省线性时间从列表开头到所需点（通过所有链接元素逐个遍历）吗？

是的。基本上，这意味着列表只需要更改指针以插入新元素，而不需要遍历整个列表或复制内容等。因此，插入是常数时间，因为不需要遍历列表或复制容器等。

- Alok Save

---

嗯...解释正确，但这不更像是“不”，而不是“是”吗？ - Michael Krelin - hacker

@MichaelKrelin-hacker：OP说“我们真的是指我们节省了线性时间从..”。 是的，因为这里没有导航，只有指针重新排列。 - Alok Save

我理解你的观点。不过，我持有不同意见，因为 OP 的意思是在正中间插入，这需要我们在实际找到这个点之前进行一些搜索。 - Michael Krelin - hacker

Answer 4

不，当我们说“在中间插入”时，并不意味着“根据遍历整个或不确定部分列表的任何标准找到插入点”。

- Michael Krelin - hacker

Answer 5

在列表的“中间”插入意味着在开头或结尾以外的某个地方进行插入。但是，进行插入需要一个指向插入点的迭代器。一旦您拥有这样的迭代器，插入时间就是恒定的，但首先获得这样的迭代器是一个单独的问题。

- Vaughn Cato