14.使用reverse避免重新分配

Posted on | In

(本章内容笔者认为可通过合理的初始化完成）

vector与string可以动态增长，其增长操作大概等价于realloc，分为4个部分（关于具体实现，C++ Primer 以及 数据结构·向量篇 均有涉及）

  1. 分配当前cap*2的内存
  2. 把元素拷贝到新内存起始处
  3. 销毁旧有对象
  4. 收回原内存

这些步骤的开销极大，并且执行了这些后同时还需要更新现在正在使用的迭代器或者指针之类。reserve可以最大幅度避免这些开销。

在说reverse之前，首先复习4个vector或string的成员函数

  • size：当前容器内的元素个数
  • capacity：最大容纳个数
  • resize：强制将元素个数变为n个，调用构造或者析构，不影响cap.如果n>cap,则realloc.
  • reserve：将cap改为至少n，如果n<cap,无动作，否则realloc.同时不改变size.

为了避免大量的realloc操作，我们可以一旦建立容器就立刻reserve到一个合适的大小（为啥不好好初始化）

1
2
vector<int> v;
for (int i = 1; i <= 1000; ++i) v.push_back(i);

上述操作大约会导致2到10次重新分配。
1
2
3
vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);

这则不会导致重新分配。

通常有两种情况可以使用reverse来避免重新分配：

  1. 你了解容器最终大致的元素个数（不如好好初始化 然后赋值 不过一旦估算少了会越界）
  2. 保留你可能需要的最大空间，添加完成后修整掉多余的容量。（修整操作见Effective STL 17）