Effective STL [5] | 尽量使用区间成员函数代替它们的单元素兄弟

Example

Q：给定两个 vector，v1 和 v2，使 v1 的内容和 v2 的后半部分一样的最简单方式是什么？

A：

1

v1.assign(v2.begin() + v2.size() / 2, v2.end());

这个测验设计为做两件事:

1. 它提供给我一个机会来提醒你 assign 成员函数的存在

太多的程序员没注意到这是一个很方便的方法。它对于所有标准序列容器（vector，string，deque 和 list）都有效。

无论何时你必须完全代替一个容器的内容，你就应该想到赋值。

如果你只是拷贝一个容器到另一个同类型的容器，operator= 就是选择的赋值函数，但对于示范的那个例子，当你想要给一个容器完全的新数据集时，assign 就可以利用，但 operator= 做不了。

2. 演示为什么区间成员函数优先于它们的单元素替代品。

区间成员函数是一个像 STL 算法的成员函数，使用两个迭代器参数来指定元素的一个区间来进行某个操作。

不用区间成员函数来解决这个条款开头的问题，你就必须写一个显式循环，可能就像这样:

1
2
3
4
5
6

vector<Randy> v1, v2; // 假设v1和v2是Randy的vector
v1.clear();
for (vector<Randy>::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end(); ++ci) {
    v1.push_back(*ci);
}

写这段代码比写 assign 的调用要做多得多的工作。

copy 替代循环

1
2

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1))

虽然在这段代码中没有表现出循环，在 copy 中的确存在一个循环 。

效率损失仍然存在。

几乎所有目标区间是通过插入迭代器（比如，通过 inserter，back_inserter 或 front_inserter）指定的 copy 的使用都可以 —— 应该 —— 通过调用区间 成员函数来代替。

比如这里，这个 copy 的调用可以用一个 insert 的区间版本代替：

1

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());

这个输入量稍微比调用 copy 少，但它发生的也比说的要直接：数据插入 v1。

这里 insert 也比 copy 好，因为字面上 insert 表示有数据插入到了 v1 中，而 copy 的使用把它变得晦涩。

关于东西被拷贝这个事实并没有什么好关注的，因为 STL 构建在东西会被拷贝的假定上。拷贝对 STL 来说很基本。

小结

我们已经确定 3 个尽量使用区间成员函数代替它们的单元素兄弟的理由。 ● 一般来说使用区间成员函数可以输入更少的代码。 ● 区间成员函数会导致代码更清晰更直接了当。

效率

当处理标准序列容器时，应用单元素成员函数比完成同样目的的区间成员函数需要更多地内存分配，更频繁地拷贝对象，而且 / 或者造成多余操作。

对此，我之前还做了个单元素兄弟插入和批量插入的效率比较的文章《vector 用 insert 批量插入效率高还是 emplace_back 效率高》，也证实了这个观点。

标准要求区间 insert 函数直接把现有元素移动到它们最后的位置，也就是，开销是每个元素一次移动。总共开销是 n 次移动，numValues 次容器中的对象类型的拷贝构造函数，剩下的是类型的赋值操作符。

相比单元素插入策略，区间 insert 少执行了 n*(numValues-1) 次移动。

花一分钟想想。这意味着如果 numValues 是 100，insert 的区间形式会比重复调用 insert 的单元素形式的代码少花费 99% 的移动！

仅当可以不用失去两个迭代器的位置就能决定它们之间的距离时，一个区间 insert 函数才能在一次移动中把一个元素移动到它的最终位置。

这几乎总是可能的，因为所有前向迭代器提供了这个功能，而且前向迭代器几乎到处都是。

所有用于标准容器的迭代器都提供了前向迭代器的功能。非标准的散列容器的迭代器也是。

在数组中表现为迭代器的指针也提供了这样的功能。事实上，唯一不提供前向迭代器能力的标准迭代器是输入和输出迭代器。

单元素插入的问题

• 当你试图去把一个元素插入内存已经满了的 vector 时，这个 vector 会分配具有更多容量的新内存，从旧内存把它的元素拷贝到新内存，销毁旧内存里的元素，回收旧内存。然后它添加插入的元素。

• 每当用完内存时，大部分 vector 实现都使它们的容量翻倍，所以插入 numValues 个新元素会导致最多$\log_2{numValues}$ 次新内存的分配。

• 每次一个地插入 1000 个元素会导致 10 次新的分配（包括它们负责的元素拷贝）。

与之对比的是，一个区间插入可以在开始插入东西前计算出需要多少新内存（假设给的是前向迭代器），所以它不用多于一次地重新分配 vector 的内在内存。

刚才进行分析是用于 vector 的，但同样的理由也作用于 string。

deque

对于 deque，理由也很相似，但 deque 管理它们内存的方式和 vector 和 string 不同，所以重复内存分配的论点不能应用。

但是，关于很多次不必要的元素移动的论点通常通过对函数调用次数的观察也应用到了（虽然细节不同）。

list

在这里使用 insert 区间形式代替单元素形式也有一个性能优势。

关于重复函数调用的论点当然继续有效，但因为链表的工作方式，拷贝和内存分配问题没有发生。

取而代之的是，这里有一个新问题：过多重复地对 list 中的一些节点的 next 和 prev 指针赋值。

每当一个元素添加到一个链表时，持有元素的链表节点必须有它的 next 和 prev 指针集，而且当然新节点前面的节点（我们叫它 B，就是 “before”）必须设置它的 next 指针，新节点后面的节点（我们叫它 A，就是 “after”）必须设置它的 prev 指针

当一系列新节点通过调用 list 的单元素 insert 一个接一个添加时，除了最后一个以外的其他新节点都会设置它的 next 指针两次，第一次指向 A，第二次指向在它后面插入的元素。每次在 A 前面插入时，它都会设置它的 prev 指针指向一个新节点。

如果 numValues 个节点插入 A 前面，插入节点的 next 指针会发生次多余的赋值，而且 A 的 prev 指针会发生 numValues-1 次多余的赋值。合计次没有必要的指针赋值。当然，指针赋值很轻量，但如果不是必须，为什么要为它们花费呢？

** 避免开销的关键是使用 list 的 insert 区间形式。** 因为那个函数知道最后有多少节点会被插入，它可以避免多余的指针赋值，对每个指针只使用一次赋值就能设置它正确的插入后的值

区间函数

参数类型 iterator 意思是容器的迭代器类型，也就是 container::iterator。

参数类型 InputIterator 意思是可以接受任何输入迭代器。

• 区间构造

所有标准容器都提供这种形式的构造函数：

1
2

container::container(InputIterator begin, // 区间的起点
InputIterator end); // 区间的终点

如果传给这个构造函数的迭代器是 istream_iterators 或 istreambuf_iterators，你可能会遇到 C++ 的最惊异的解析，原因之一是你的编译器可能会因为把这个构造看作一个函数声明而不是一个新容器对象的定义而中断。

• 区间插入

所有标准序列容器都提供这种形式的 insert:

1
2
3

void container::insert(iterator position, // 区间插入的位置
InputIterator begin, // 插入区间的起点
InputIterator end); // 插入区间的终点

关联容器使用它们的比较函数来决定元素要放在哪里，所以它们了省略 position 参数。

1

void container::insert(lnputIterator begin, InputIterator end);

当寻找用区间版本代替单元素插入的方法时，不要忘记有些单元素变量用采用不同的函数名伪装它们自己。比如，push_front 和 push_back 都把单元素插入容器，即使它们不叫 insert。如果你看见一个循环调用 push_front 或 push_back，或如果你看见一个算法 —— 比如 copy—— 的参数是 front_inserter 或者 back_inserter，你就发现了一个 insert 的区间形式应该作为优先策略的地方。

• 区间删除

每个标准容器都提供了一个区间形式的 erase，但是序列和关联容器的返回类型不同。

序列容器提供了这个：

1

iterator container::erase(iterator begin, iterator end);

关联容器提供这个:

1

void container::erase(iterator begin, iterator end);

Q：为什么不同？

A：解释是，如果 erase 的关联容器版本返回一个迭代器（被删除的那个元素的下一个）会招致一个无法接受的性能下降。

这个条款的对 insert 的性能分析大部分也同样可以用于 erase。单元素删除的函数调用次数仍然大于一次调用区间删除。当使用单元素删除时，每一次元素值仍然必须向它们的目的地移动一位，而区间删除可以在一个单独的移动中把它们移动到目标位置。

关于 vector 和 string 的插入和删除的一个论点是必须做很多重复的分配。（当然对于删除，会发生重复的回收。）那是因为用于 vector 和 string 的内存自动增长来适应于新元素，但当元素的数目减少时它不自动收缩。

• 区间赋值

所有标准列容器都提供了区间形式的 assign:

1

void container::assign(InputIterator begin, InputIterator end);

结论

几乎所有目标区间被插入迭代器指定的 copy 的使用都可以用调用的区间成员函数的来代替 。

尽量使用区间成员函数来代替单元素兄弟的三个可靠的论点。区间成员函数更容易写，它们更清楚地表达你的意图，而且它们提供了更高的性能。那是很难打败的三驾马车。

ref:
[1]. https://mp.weixin.qq.com/s?__biz=MzUyMDc2MDMxNg==&mid=2247490705&idx=1&sn=830797e69b61fe9693bf4aaea72df4b3&chksm=f9e42202ce93ab1437ad36c37e141b0794328495c0c584d808d0f4ad36251680dbfba257b060&cur_album_id=3009999611861975043&scene=189#wechat_redirect