算法调用
优先于手工循环
STL算法内部都是循环
, 意味着你的手工循环
大多数可以用STL算法来完成
用STL算法 更高效、更安全、更清晰/可维护
[1] 类库
实现者优化了对容器的遍历
, 类库使用者很难做到
[2] 很多STL算法使用了复杂的数学特殊算法
, 非一般C++程序员能达到
[3] client 调用可能重复
for(list<Widget>::iterator iter = wLst.begin();
iter != wLst.end(); // 每次循环都要调用 -> 低效 -> 放出去用临时变量记录
++iter)
iter->redraw();
for_each(wLst.begin(), wLst.end(),
mem_fn_ref(&Widget::redraw) );
insert
可能导致容器重新分配 => 所有迭代器失效
, 使用
无效的迭代器 => undefined behavior
vector<double>::iterator iterPos = iv.begin();
// wrong: insert() => 可能使所有迭代器失效(容器重新分配) -> undefined behavior
for(size_t i = 0; i < N; ++i)
vec.insert(iterPos++, data[i] + 10);
// right
for(size_t i = 0; i < N; ++i)
{
// Note: 必须更新 insert 返回的迭代器
iterPos = vec.insert(iterPos, data[i] + 10);
++iterPos;
}
transform(data, data + N,
inserter(v, v.begin() ),
bind2nd(std:plus<double>(), 10) );
成员函数
优先于同名算法
关联容器提供了 count/find/lower_bound/upper_bound/equal_range
list 提供了 remove/remove_if/unique/sort/merge/reverse
大多数情况下, 你应该使用这些成员函数, 而不是相应的STL算法
与容器(特别是 关联容器)的一贯 行为保持一致
(1) 对数时间
性能, 而非线性时间
性能
(2) 可用等价性
来确定两个值是否"相同"
, 而等价性是关联容器的本质定义
破坏容器的排序性
, 与容器的行为不一致map/multimap
时, 将很自然地 只考虑元素的 keyPart
, 而不是完整的(key,value) pair
remove/remove_if/unique/sort/merge/reverse
拷贝
list容器中的对象
; 而list成员函数则无须任何对象拷贝
, 只是简单地维护
好那些将list节点连接起来的指针
, 维护指针的开销
比拷贝对象低得多count/find/binary_search/lower_bound/upper_bound/equal_range
相等性排序
还是 等价性排序
, 选择用 count/find
还是 else成员函数
未排序
, 只能用
前2种count/find 及其 _if 版本
: 线性时间相等性
判 相同
[1] count: 特定值 是否存在
? 存在的话 有多少个
?
[2] find : 特定值 是否存在
? 存在的话 在哪
?
排序
, 后4种 更快: 对数时间等价性
判 相同
[1] binary_search
只回答 "是否存在"
一对迭代器
第1/2个迭代器 等于 lower_bound/upper_bound 返回的迭代器(等价区间的 前闭端/后开端)
=> 标识了一个子区间, 其中的值与你所查找的值等价
=> 完成了 find + count
功能
VWIterPair vWIterpair =
equal_range(vw.begin(), vw.end(), w);
cout << std::distance(vWIterpair.first, vWIterpair.second)
<< " elems in vw equivalent to w.\n";