访问中间的 std::list
我有一个虚拟问题。我总是读到 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?
当我们说“在中间插入”时，我们真的意味着我们节省了从列表开头到所需点的线性时间（逐一遍历其间所有链接的元素）吗？
I have a dummy question. I always read that C++ std::list container has constant time for inserting elements at the beginning, at the end and in the middle:
Which is the correct way to insert an element directly in the middle of a std::list?
Is maybe this one?
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?
When we say 'inserting in the middle' do we really mean that we save linear time to go from the beginning of the list to the desired point ( traversing one by one through all linked elements in between)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以像这样一般地进行迭代器数学运算：
这适用于任何迭代器类型（OutputIterator 或 InputIterator 除外）
当然，它效率更高，
不幸的是，
l.insert(l. begin + (l.size()/2), value) 不起作用，因为列表迭代器不是随机访问，因此没有定义operator+（以防止性能意外） ！）。请记住，std::advance()可能是一个昂贵的操作，具体取决于迭代器类型（对于在其上实现的反向迭代器来说，它会很慢只向前的容器，例如）。You can do the iterator maths generically like this:
This will work for any iterator type (except OutputIterator or InputIterator)
Of course it is way more efficient to say
Unfortunately,
l.insert(l.begin + (l.size()/2), value)won't work because list iterators aren't random access, therefore don't haveoperator+defined (to prevent performance surprises!). Keep in mind thatstd::advance()might be a costly operation depending on iterator type (it will be slow for reverse iterators implemented on a forward-only container, e.g.).这里，“中间”意味着列表中的任意点，只要您已经有一个引用该点的迭代器即可。鉴于此，插入只需修改插入点周围的一些指针即可。
如果您还没有插入点的迭代器，并且它不是像开始或结束这样简单的地方，那么遍历列表来找到它将需要线性时间。
Here, "the middle" means an arbitrary point in the list, as long as you already have an iterator referring to that point. Given that, insertion is just a matter of modifying a few pointers around the insertion point.
If you don't already have an iterator for the insertion point, and it isn't somewhere simple like the beginning or the end, then it will take linear time to walk through the list to find it.
是的。
基本上，这意味着列表只需更改指针即可插入新元素，而不是导航整个列表或复制内容等。因此插入是恒定时间，因为不需要遍历列表或复制容器等。
Yes.
Basically, It means the list needs to just change pointers to insert a new element and not navigate the entire list or copy the contents etc.Hence the insertion is constant time, because there is no need of traversing the list or copying the containers etc.
插入列表的“中间”意味着插入除开头或结尾之外的其他位置。但是进行插入需要一个指向插入点的迭代器。一旦有了这样的迭代器，插入时间是恒定的，但首先获得这样的迭代器是一个单独的问题。
Inserting in the "middle" of a list means inserting somewhere other than the beginning or end. But doing an insertion requires an iterator to the insertion point. Once you have such an iterator, the insertion time is constant, but getting such an iterator in the first place is a separate issue.
不，当我们说“在中间插入”时，我们并不是说“根据遍历列表的整个或不确定部分的任何标准来查找插入点”。
No, when we say "inserting in the middle" we do not mean "finding the insertion point according to whatever criteria that takes traversing of the whole or indefinite part of the list".