超速矢量 push_back

Question

我正在尝试加速 vector::push_back，但容量无法预测

当保留可用时，向量 push_back 将新元素写入容器的末尾，然后移动结束标记。使用完所有储备后，push_back 可能会触发重新分配，这是一个缓慢的过程。
为了加快速度，为即将到来的几个 push_back 重新生成储备，而无需在空时重新分配。您认为此代码如何帮助实现该目标？

#ifndef __VECTOR_HPP
#define __VECTOR_HPP
#include <exception>
#include "Concept.hpp" //Concept::RESA constant
#include <vector>
template <typename T>
class Vector : public std::vector<T> {
public :
  void push_back (T t) {
    if (std::vector<T>::size () == std::vector<T>::capacity ()) {
      std::vector<T>::reserve ((size_t) Concept::RESA);
    }
    std::vector<T>::push_back (t);
  }
};
#endif

测试程序：

#include "Vector.hpp"

int main (int argc, char* argv []) {
  {
    std::vector<size_t> v0;
    clock_t t (clock ());
    size_t duration (0);
    for (size_t i (0); i != 10000000; i++) {
      v0.push_back (i);
    }
    duration = (size_t) (clock () -t);
    std::cout << "duration old push_back == " << duration << " ticks" << std::endl;
  }
  {
    size_t duration (0);
    Vector<size_t> v1;
    clock_t t (clock ());
    for (size_t i (0); i != 10000000; i++) {
      v1.push_back (i);
    }
    duration = (size_t) (clock () -t    );
    std::cout << "duration new push_back == " << duration << " ticks" << std::endl;
  }
}

结果：

使用 Concept::RESA == 8192，并应用建议，这是在 Lenovo ThinkCentre icore5（Linux Debian，g++）上的结果：

持续时间旧 push_back == 105317 ticks

持续时间新push_back == 87156 刻

Answer 1

确实push_back可能触发重新分配，这是一个缓慢的过程。
它不会在每个 push_back 上都这样做，而是每次都会保留指数级的更多内存，因此明确 reserve 只有在您事先对结果向量大小有一个很好的近似值时才有意义。

换句话说，std::vector 已经处理了您在代码中提出的建议。

另一点：there is a reserve method 比插入和删除元素更能达到目的，最值得注意的是它不会创建和销毁实际对象。

具有讽刺意味的是，@Sopel 提到在 class 中将 insert/erase 替换为 reserve 会禁用 vector 的增长摊销，使您的代码成为几个错误（在某种程度上）相互抵消的一个很好的例子.

Answer 2

您的代码有几个问题。

您实质上是在定义一个与 std::vector 非常相似的类型，其中 std::vector 作为其唯一成员。为什么不首先使用 std::vector？
你的 push_back() 功能太糟糕了。让我先解释一下 std::vector<>::push_back() 实际上做了什么。
1. if size()<capacity()：它只是复制块末尾的新元素并增加 end 标记。 这是最常见的情况。
2. 仅如果size()==capacity()，需要重新分配并且
  1. 它分配一个新的内存块，通常是当前容量的两倍
  2. 它将所有数据移动到新块的开头
  3. 它取消分配旧的内存块
  4. 终于在数据末尾构造了一个新元素
现在让我们看看您的
```
void push_back (const T& t) {
  if (val_.size () == val_.capacity ()) {
    val_.insert (val_.end (), resa_.begin (), resa_.end ());
    auto i = val_.end();
    i -= (size_t) Concept::RESA;
    val_.erase (i, val_.end ());
  }
  val_.push_back (t);
}
```
如果 val_.size()==val_.capacity():
1. 它 insert() 是 val_.end() 处的默认构造元素。为此，std::vector::insert() 执行以下操作：
  1. 它分配一个新的内存块，足够大以容纳旧数据和要插入的数据，但可能更大。
  2. 它将所有数据移动到新块的开头
  3. 它取消分配旧的内存块
  4. 它复制要插入到旧数据末尾的元素
2. 它会破坏所有新插入的元素。
3. if最终在数据末尾构造了一个新元素（不需要重新分配）。
因此，您的函数也需要重新分配 与普通 std::push_back() 一样频繁并且完全 不必要地 复制构造然后销毁一大块元素。当你想要连续的内存布局（如std::vector所承诺的）时，无法避免重新分配和不知道提前确定最终尺寸。如果可以删除这些要求中的任何一个，则可以避免重新分配：通过 std::vector<>::reserve() 或使用具有非连续内存的容器，例如 std::deque.

超速矢量 push_back

speeding vector push_back

c++

push-back

stdvector