历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

$\Huge\color{SkyBlue}{$}\color{Gold}{\textit{闪电STL—— 仿函数&编程}}\color{SkyBlue}{$}$

作者：

Okamasa店老板 , 2022-04-19 01:14:20 , 所有人可见 , 阅读 583

5

2

前言

STL在C++开发中的重要性无需多言。它设计精妙，性能卓越，功能方便。

大多数时候，它都易于使用。但利刃能开几分光，还要依赖使用者的修养。提修养，多读书。《Efficient STL》中给出了关于STL的50条建议。

这些规则分为以下七个部分：

$\color{blue}{【Container(容器)】}$
$\color{blue}{【vector\&string(列表和字符串)】}$
$\color{blue}{【associate container(关联型容器)】}$
$\color{blue}{【Iterator(迭代器)】}$
$\color{blue}{【Algorithms(算法)】}$
$\color{blue}{【Function(函数)】}$
$\color{blue}{【编码实践】}$

本文将介绍最后两部分的内容。希望它们提供快如闪电的性能，同时照亮使用过程中的疑惑。

Functor 仿函数

函数通常以函数指针的形式传入；如果作为Predictor(返回值为true, false) 传参给remove_if等函数，需要保证他是无状态的函数；

有些函数对象接口需要特定的typedef。

对not1, not2, bind1st, bind2nd, 要求定义argumenCtype, firscargumenCtype, second_argument_type, 和 result_type；

可以调用ptr_fun对函数进行封装, 或者构造继承自unary_function, binary_function来实现定义

//原始的operator:

list<Widget*> widgetPtrs;

//ptr_fun形式

bool isInteresting(const Widget *pw);

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), not1(ptr_fun(isInteresting)));

//继承unary_function形式

template <class T>

class MeetsThreshold: public std::unary_function<Widget, bool> {

private:

const T threshold;

public:

MeetsThreshold(const T& threshold);

bool operator()(const Widget&) const;

...

};

list<widget> widgets;

...


list<Widget>::reserve_iterator i1=find_if(widgets.rbegin(), widgets.rend(), not1(MeetsThreshold<int>(10)));

//继承binary_function形式

struct WidgetNameCompare:

std::binary_function<Widget, Widget, bool> {

bool operator()(const Widget& lhs, const Widget& rhs) const;

};

list<Widget>::iterator i2=find_if(widgets.begin(), widgets.end(), bind2nd(WidgetNameCompare(), w));

关于ptr_fun, mem_fun, mem_fun_ref的作用：

ptr_fun: 为函数加一些typedef

mem_fun: 如果容器里存的是类的指针，需要用mem_fun传类函数参数

vector<Widget*> wv;
for_each(wv.begin(),wv.end(),mem_fun(&Widget::print));

mem_fun_ref: 如果容器里存的是类，需要用mem_fun_ref传类函数参数

vector<Widget> wv;

for_each(wv.begin(),wv.end(),mem_fun_ref(&Widget::print));

使用STL编程

尽量使用algorithm代替手写的循环。algorithm效率更高，可读性更好。

以下是一个例子：

deque<double>::iterator insertLocation = d.begin();

//手动循环

for (size_t i=0; i<numDoubles; ++i) {

insertLocation = d.insert(insertLocation, data[i] + 41);

++insertLocation;

}

//STL的transform方式

transform(data, data + numDoubles, inserter(d, d.begin()), bind2nd(plus<int>(), 41));

尽量使用member function，代替同名的algorithm。

std::find(set)将会遍历set，而set.find()可以利用set本身的平衡树结构，在logN时间复杂度下查询；

list的member function行为与algorithm内的同名函数不同，list的merge，remove, remove_if会移除对象；list也不能作为algorithm中sort的参数

查找算法的使用：

无序的序列：查找元素是否存在用find, 统计出现次数用count

有序序列：查找元素是否存在用binary_search; 查找元素位置, lower_bound会返回元素的位置或元素不存在时应插入的位置；equal_range会返回一组pair，表示lower_bound, upper_bound返回的值；如果两个值相等，则说明key不存在；

关联容器可以使用容器自身的find来查找

详细信息可参见下表：

使用函数对象代替函数指针作为algorithm的参数可以获得更高的效率。函数对象的operator是inline的，编译器会直接展开代码。函数则传递了函数指针，编译器无法将函数代码内联。同时，这样可以避免语法上的歧义。

使用嵌套的STL函数需要注意可读性可维护性，避免写出write-only代码。

//write-only代码示例

//删除满足vi < x && i > last_i, last_i 是最后一个大于y的位置

vector<int> v;

int x, y;

v.erase(

remove_if(

find_if(v.rbegin(), v.rend(), bind2nd(greater_equal<int>(), y)).base(), //找到last_i

v.end(),

bind2nd(less<int>(), x)), //找到小于x的位置

v.end()

);

STL头文件规律：

几乎所有容器都在名字对应的头文件里，比如使用list需要#include [HTML_REMOVED]

除了accumulation, inner_product, adjacent_difference, partial_sum，其他算法都在[HTML_REMOVED]里声明；这四个函数声明在[HTML_REMOVED]中

迭代器声明在[HTML_REMOVED]中

functor(less[HTML_REMOVED])和functor adapter(not1, not2, mem_fun) 在functional中声明

STL编译错误诊断：

string是一个typedef，与它有关的编译错误通常包含类似basic_string[HTML_REMOVED], allocator[HTML_REMOVED] >的形式，将它替换为对应的类型编译错误会更清晰

对vector和string而言， iterator通常是指针，如果编译错误提到了指针，可能是迭代器相关的错误

一些函数有复杂的模板构造参数，可以直接把模板构造参数忽略，让报错信息更清晰

包含back_insert_iterator, front_insert_iterator, insert_iterator的错误通常是在调用对应的inert操作时出错了

如果错误信息包含binder1st, binder2nd，则是执行对应的bind1st, bind2nd出错了

如果出现了algorithm中的exception，通常是算法的传参错误，比如iterator类型不对