c++ - 通过每次调整 vector 的大小在 vector 中插入一个元素是否需要更多时间？

Question

我在这里遇到了决策问题。在我的应用程序中，我需要合并两个 vector 。我不能使用 STL 算法，因为数据顺序很重要(不应该排序。)。

• 两个 vector 都包含有时可能相同或在最坏情况下有 75% 不同的数据。

• 目前我对两种方法感到困惑，

  Approach 1:
  
     a. take an element in the smaller vector.
     b. compare it with the elements in bigger one.
     c. If element matches then skip it (I don't want duplicates).
     d. If element is not found in bigger one, calculate proper position to insert.
     e. re-size the bigger one to insert the element (multiple time re-size may happen).
  
  
   Approach 2:
  
     a. Iterate through vectors to find matched element positions.
     b. Resize the bigger one at a go by calculating total size required.
     c. Take smaller vector and go to elements which are not-matched.
     d. Insert the element in appropriate position.
  

请帮助我选择合适的。如果有任何更好的方法或更简单的技术(如 STL 算法)，或比 vector 更简单的容器，请在此处发布。谢谢。

Answer 1

您不应该关注调整大小。在方法 1 中，您应该使用 use vector.insert() 这样您实际上不需要自己调整 vector 的大小。这可能会导致底层缓冲区的重新分配自动发生，但 std::vector 已谨慎实现，因此这些操作的总成本很小。

你的算法的真正问题是插入，也许是搜索(你没有详细说明)。当您在除末尾以外的任何地方进入 vector 时，插入点之后的所有元素都必须在内存中向上移动，这可能会非常昂贵。

如果您希望速度更快，您应该从两个输入 vector 构建一个新 vector ，方法是一次附加一个元素，中间不插入。