在向量的前面插入元素

Question

iterator insert ( iterator position, const T& x );

这是std::Vector类中插入运算符的函数声明。

该函数的返回类型是指向已插入元素的迭代器。我的问题是，在考虑速度至关重要的大型程序中，鉴于此返回类型，插入到开头的最有效方式是什么（因此我正在寻找最具计算效率的方法）。它是以下内容吗？

//Code 1
vector<int> intvector;
vector<int>::iterator it;
it = myvector.begin();
for(int i = 1; i <= 100000; i++){
    it = intvector.insert(it,i);
}

或者，

//Code 2
vector<int> intvector;
for(int i = 1; i <= 100000; i++){
    intvector.insert(intvector.begin(),i);
}

基本上，在 Code 2 中，参数是,

intvector.begin() 

与Code 1中返回的迭代器相比，计算上评估起来比较“昂贵”/耗费成本，或者两者应该同样便宜/昂贵？

- Tryer

---

在向向量的前面添加元素时，需要将其他所有元素向后移动。如果您需要频繁进行前插入操作，建议使用list或deque。 - wkl

了解如何加速程序的唯一方法是进行性能剖析。你应该先编写程序，然后进行剖析并找出优化的方法。停止猜测，直接进行第二步，这样更加规范。显然，这种微观优化往往不会有太大作用；比如说，你应该使用一个能够更快地在前面插入元素的容器，例如 deque。 - GManNickG

您还可以使用IgushArray（https://github.com/igushev/IgushArray），它像数组一样具有快速的常数时间访问操作，但插入/删除操作仅需要O（N ^ 1/2）时间。请注意，该结构对reserve（）非常敏感。 - Edward Igushev

有一个版本的vector::insert函数，它接受一个范围（两个迭代器）作为参数，而不是一个值。获取一个迭代器（最好是随机访问，但至少是前向访问），以生成您想要添加的整数，并进行一次插入调用：这样，向量将进行单个重新分配和洗牌，以为所有新值腾出空间。 - Marc Glisse

std::vector<T>::insert() 可能会导致向量重新调整大小，因此可能会使您的迭代器无效。 - ipapadop

如果您需要在向量开头插入大量数据，可以先将其反转，然后将它们插入到末尾，最后再将其反转回来。但是，如果不知道您的问题的确切性质，很难说这是否是一种成本有效的方法。 - Nicholas Hamilton

Answer 1

如果你的程序有一个关键需求，需要在容器的开头插入元素: 那么你应该使用 std::deque 而不是 std::vector。 std::vector 只适合在末尾插入元素。

在C++11中引入了其他容器。我应该开始寻找一个更新的图表，其中包含这些新容器，并在此处插入它们。

- Stephane Rolland

---

只有当你需要使用 splice 成员函数时，才需要使用 list。否则，请使用 deque。 - Billy ONeal

根据这个图表，在中间插入时，我们应该使用 std::list。 - Stephane Rolland

@Billy -- 这不是使用列表的唯一情况。如果您需要经常在列表中间插入或删除元素，或调用需要这些操作的函数（如splice或sort），则使用列表。 - Benjamin Lindley

@PigBen: 实际上，在列表上排序会更慢，因为排序并不会真正删除任何东西——它只需要比较和交换。（好吧，如果您的对象很大，交换操作可能会稍微便宜一些，但这是一个异常用例）“在中间插入”的问题在于要到达列表的中间需要线性时间。如果您可以保留迭代器指向所需位置，请务必使用列表。然而，我认为我从来没有见过有人使用列表来完成这个目的；通常想要的是deque。 - Billy ONeal

好像原文在这里...？http://linuxsoftware.co.nz/cppcontainers.html - Roddy

Answer 2

获取插入点的效率并不重要——相比每次插入时不断洗牌现有数据的低效率，它微不足道。

在这种情况下，请使用std:：deque，因为它是为此而设计的。

- Mark Ransom

Answer 3

虽然这是一个旧帖子，但在谷歌搜索中却成为了同事桌面上的第一个搜索结果。

有一种使用双端队列之外的备选方案值得考虑：

std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
  foo.push_back(T());
std::reverse( foo.begin(), foo.end() );

相较于deque，使用vector可提高性能，但其设计更为复杂。此外，交换操作（如reverse函数所使用的）相当有效率，但复杂度会相应增加50%。

在决定如何处理时，请务必进行测量。

- Happy Green Kid Naps

---

人们谈论 deque，但问题是关于 vector 的。我认为这个回答最合适。 - Danil

Answer 4

很可能像其他人建议的那样，deque是合适的解决方案。但为了完整起见，假设您只需要进行一次前插入，在程序中的其他地方不需要在前面执行其他操作，并且否则vector提供了您需要的接口。如果所有这些都是正确的，您可以使用非常高效的push_back添加项目，然后reverse向量以按顺序获取所有内容。这将具有线性复杂度，而插入到前面时则具有多项式复杂度。

- Mark B

---

如果解决了这个问题，请给个赞。也许在代码的后面使用向量很重要。此外，最好使用reserve来预留内存并避免不断重新预留造成的开销。 - ezdazuzena

Answer 5

如果你想要在计算效率方面更高效地在前面插入，那么你可能希望使用deque而不是vector。

- Tim Rupe

---

谢谢。我会研究deque。我希望像vector类一样，deque类也允许通过object[index]访问其元素。在我的应用程序中，插入是问题的一部分...访问元素是另一个问题。 - Tryer

@Tryer，是的，deque支持通过[]符号进行快速访问。虽然不如vector快，但对于大多数情况来说已经足够了。 - Mark Ransom

Answer 6

当你使用一个向量时，通常你知道它实际上将要有多少元素。在这种情况下，预留所需数量的元素（在你展示的例子中为100000），并通过使用[]运算符来填充它们是最快的方法。如果你确实需要在前面进行高效的插入操作，可以使用deque或list，具体取决于你的算法。

你还可以考虑颠倒你的算法逻辑，在末尾插入元素，这通常对于向量来说更快。

- Diego Sevilla

---

Operator[] 不比任何迭代器相关的方法，或者填充容器的任何其他方法（例如 std::generate_n）更快。保留并不能真正解决这里发生的问题。是的，你可以节省一些分配内存的时间，但是你仍然有一个平方级别的操作。 - Billy ONeal

@Bill：是的，操作符并不比迭代器或生成函数更快。我只是想指出，在开始时（如果他或她知道需要多少空间），预留所需的空间，然后通过操作符访问它也可以节省时间，并且通常使算法更清晰。但再次强调，这取决于算法。 - Diego Sevilla

Answer 7

如果你真的想在开头插入数据，我认为你应该更改容器的类型。这就是为什么vector没有push_front()成员函数的原因。

- Hongseok Yoon

Answer 8

直觉上，我同意@Happy Green Kid Naps的观点，并进行了一个小测试，结果显示对于小容量（1<<10个基本数据类型元素以下）没有区别。然而，对于更大的容器大小（1<<20以下），std::deque似乎比翻转std::vector性能更高。因此，在决定之前，请进行基准测试。另一个因素可能是容器的元素类型。

测试如下：

• 测试1：将(a) 1 << 10或(b) 1 << 20个uint64_t推入 std::deque
• 测试2：将(a) 1 << 10或(b) 1 << 20个uint64_t推入 std::vector，然后执行std::reverse

结果如下：

• 测试1 - deque (a) 19 µs
• 测试2 - vector (a) 19 µs
• 测试1 - deque (b) 6339 µs
• 测试2 - vector (b) 10588 µs

注：µs指微秒

- Marie Hoffmann

Answer 9

这可能会引起一些人的不满，因为它并没有直接回答问题，但是要记住，从std::vector中以相反的顺序检索项目既简单又快速。

- Bob Pretzker

---

这将更有用，作为原始帖子下的评论。 - AFOC

Answer 10

您可以支持以下操作：

1. 在前面插入。
2. 在末尾插入。
3. 更改任何位置的值（不会出现在deque中）
4. 访问任何索引处的值（不会出现在deque中）

所有上述操作的时间复杂度为O(1)

注意：您只需要知道它可以在左侧和右侧达到的max_size的上限即可。

class Vector{
public:
    int front,end;
    int arr[100100];   // you should set this in according to 2*max_size
    Vector(int initialize){
        arr[100100/2] = initialize; // initializing value 
        front = end = 100100/2;     
        front--;end++;
    }
    void push_back(int val){
        arr[end] = val;
        end++;
    }
    void push_front(int val){
        if(front<0){return;} // you should set initial size accordingly
        arr[front] = val;
        front--;
    }
    int value(int idx){
        return arr[front+idx];
    }
    // similarity create function to change on any index
};

int main(){
    Vector v(2);
    for(int i=1;i<100;i++){
        // O(1)
        v.push_front(i);
    }

    for(int i=0;i<20;i++){
        // to access the value in O(1)
        cout<<v.value(i)<<" ";
    }
    return;
}

- Kartik Punjabi