我有一个愚蠢的问题。我总是读到 C++std::list容器在开头、结尾和中间插入元素的时间是固定的：在 a 中间直接插入元素的正确方法是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?
当我们说“在中间插入”时，我们真的意味着我们节省了从列表的开头到所需点的线性时间（一个一个地遍历其间的所有链接元素）吗？
您可以像这样进行迭代器数学运算：
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()可能是一个昂贵的操作，具体取决于迭代器类型（例如，在只进容器上实现的反向迭代器会很慢）。
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.
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".
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.