在中间访问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?

当我们说'插入中间'时,我们是否真的意味着我们保存线性时间从列表的开头到所需的点(逐个遍历所有链接的元素)？

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()可能是一个代价高昂的操作(例如,对于仅向前容器上实现的反向迭代器,它会很慢).

Answer 2

这里,"中间"表示列表中的任意点,只要您已经有一个指向该点的迭代器即可.鉴于此,插入只是修改插入点周围的几个指针.

如果你还没有插入点的迭代器,并且它不像开头或结尾那样简单,那么需要线性时间来遍历列表才能找到它.