Effective STL 学习笔记 Item 26: Prefer Iterator to reverse_iterator and const_rever_itertor
我常用的 Python 调试工具 - 博客 - 伯乐在线

Effective STL 学习笔记 Item 30: 保证目标区间足够大

tubo posted @ 2014年9月03日 00:13 in 未分类 , 284 阅读
Effective STL 学习笔记 Item 30: 保证目标区间足够大

1 容器区间与算法

STL 容器吸引人的地方之一在于它能够自动管理内存,在有新的元素插入时候(通过 push_back(), push_front(), insert() )可以自动分配空间。但要注意的是,如果新的元素不是通过上述的 navive method 加进来的话,容器不会自动分配内存,例如下面的代码:

1: int transmogrify(int x); // this function produces some new value from x.
2: vector<int> values;
3: vector<int> results
4: 
5: transform(values.begin(), values.end(), results.end(), transmogrify);

这里有两个问题:

  • 第五行代码会直接向 results 的尾部写入数据,而尾部的内存未知,会引发问题
  • 直接的操作不会改变容器内部记录的 size & capacity ,从而破坏的容器。

2 back_inserter

我们应该想办法调用 push_front,push_back or insert 来插入数据:

int transmogrify(int x); // this function produces some new value from x.
vector<int> values;
vector<int> results

transform(values.begin(), values.end(), back_inserter(results), transmogrify);

3 front_inserter

如果上面的代码中使用的是可以双向插入数据的容器( deque or list ),还可以使用 push_front

1: int transmogrify(int x); // this function produces some new value from x.
2: list<int> values;
3: list<int> results
4: 
5: transform(values.begin(), values.end(), front_inserter(results), transmogrify);

上面的代码还有个问题,由于每个数据都会被插到头部,实际上最后得到的 results 里面数据的顺序和 values 里面是相反的,我们可以反向遍历 values:

int transmogrify(int x); // this function produces some new value from x.
list<int> values;
list<int> results

transform(values.rbegin(), values.rend(), front_inserter(results), transmogrify);

4 inserter

front_inserter & back_inserter 可以向前或者向后插入数据,而 inserter 则可以向任意位置插入数据:

int transmogrify(int x); // this function produces some new value from x.
vector<int> values;
vector<int> results

transform(values.begin(), values.end(),
          inserter(results, results.begin() + results.size()/2),
          transmogrify);

5 inserter & reserve

Item 14 中提到过,vector 插入式数据可能会引起内存的重新分配,从而影响性能,对于前面的几个例子来说,我们可以预先算出插入新的数据后 vector 有多大,因此可以是所有 Item 14 中提到过的方法来优化:

int transmogrify(int x); // this function produces some new value from x.
vector<int> values;
vector<int> results

result.reserve(result.size() + values.size());
transform(values.begin(), values.end(),
          inserter(results, results.begin() + results.size()/2),
          transmogrify);

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter