从理论上讲，您应该能够在O（1）时间中将列表的任意位置插入列表（根据您选择的索引）。但是，当使用STL列表时，您需要在迭代器位置插入，并且据我所知，迭代器位置必须增加O（n）次才能将其设置为所需的索引。我对为什么这样会感到du目结舌，我肯定弄错了，有办法更快地做到这一点吗？
我肯定是误会了
不，您没有记错。
有办法更快地做到吗？
只有通过捕获上一次插入调用的返回值来缓存要插入的位置，您才能更快地执行此操作。如果除了列表和要插入的索引之外没有其他信息，那么O(n)唯一的选择n就是要插入的索引。