使用C++ vector::insert()在向量末尾添加元素

Question

我正在编写一小段代码，需要将值插入到C++ STL向量的某个特定位置，具体位置由向量元素的值决定。我使用insert()函数来完成这个操作。我知道当我想要在向量末尾添加新元素时，我可以简单地使用push_back()函数。但为了让我的代码看起来更好，我想要专门使用insert()函数。这个函数需要一个指向期望插入点之后的元素的迭代器和要插入的值作为输入。如果将其作为参数传递的迭代器的值是v.end()，其中v是我的向量，那么这是否与push_back()函数相同呢？

非常感谢！

- Nick Van Hoogenstyn

---

如果你发现自己在向向量(vector)中频繁插入数据，那么你可能使用了错误的数据结构。考虑（例如）使用双端队列(deque)。当然，如果这个向量很小，那么就不会有问题。 - user2100815

@Nick：是的，它会。一个简单的实验就可以告诉你这个答案。 - Björn Pollex

我不明白一个实验如何能告诉他那个结果。如果它是无效的，他会得到UB，在这种情况下，他的程序可能会看起来正常工作。 - user2100815

@unapersson：如果大多数插入操作是在序列的开头或结尾，那么双端队列会很有帮助。如果只在序列末尾进行插入操作，那么使用向量也可以达到同样的效果。 - Björn Pollex

对于在开头插入元素，使用双端队列效果更好。但对于除了开头和结尾以外的任何插入操作来说，它几乎肯定比向量更差（都是线性时间，但双端队列的常数因子显著更大）。而向量中间插入的成本通常被夸大了，至少是如果向量中的类型是POD类型的话。（插入的真正“成本”通常在于使迭代器失效。只有std::list避免了这个问题，但std::list在其他方面非常昂贵。） - James Kanze

Answer 1

a.push_back(x)被定义为对于支持它的序列容器，其语义与(void)a.insert(a.end(),x)完全相同。

请参阅ISO/IEC 14882:2003 23.1.1/12 [lib.sequence.reqmts]中的表68。

关于vector.push_back(x)和vector.insert(vector.end(), x)的运行时间，请考虑加粗部分：

表68列出了一些顺序容器提供的序列操作，但其他容器类型没有。实现应为“容器”列中显示的所有容器类型提供这些操作，并将它们实现为摊销的常数时间。

- CB Bailey

---

快速提问，就性能而言，我想知道push_back是否更快？我测试了一些东西，显示插入有点慢。我只是想确认一下...谢谢。 - Saman

push_back() 不会返回新插入元素的迭代器。std::list<T>::end() 会返回一个失效的迭代器。 - peterh

如果您包含所引用的标准部分，那么您的答案会更好。 - Jon McClung

@JonMcClung：嗯，但答案已经包含了那个信息了？ - CB Bailey

我指的是引用。我不知道如何从章节标记或您提供的任何内容中查找标准的随机部分。 - Jon McClung

Answer 2

在push_back返回void的情况下，insert会返回刚插入的元素的iterator。

另外，还有一种验证它们是否执行相同操作的方法：编译以下代码。

int main()
{
    std::vector<int const> v;
    v.push_back(0);
    return 0;
}

编译器会输出许多令人烦恼的消息，仔细阅读您将发现push_back调用了insert（如果没有，请尝试编译v.insert(v.end(), 0)以查看它们是否调用相同的插入函数）。

- neuront