|
std::function 基本实现
std::function 是在 C++11 中新增的一个用于统一包装可调用对象的模板类型. 所谓统一包装, 就是无论被包装的内容的实际类型, 只要符合相应的函数调用签名, 都可以装入一个 std::function 对象中使用. 比如
Code Snippet 0-0
#include <iostream>
#include <functional>
// 全局函数
int fn_ptr(int x, int y)
{
return x + y;
}
// 包含 2 个 int 成员的函数对象类型
struct TwoInts {
TwoInts(int m_, int n_)
: m(m_)
, n(n_)
{}
int operator()(int x, int y)
{
return x + y + m + n;
}
int m;
int n;
};
int main()
{
// 使用 std::function 类型包装全局函数指针
std::function<int(int, int)> f(fn_ptr);
std::cout << f(1, 2) << std::endl; // 输出 3
// 使用 std::function 类型包装函数对象
std::function<int(int, int)> g(TwoInts(10, 20));
std::cout << g(1, 2) << std::endl; // 输出 33
return 0;
}
上面的使用例子中, 两个 std::function 对象定义都在栈上. 按照 C++ 的常识, 两个对象一定有相同的尺寸, 即对它们求 sizeof 得出的值一定相等. 但用于构造这两个 function 对象的材料却有着不同的尺寸, 也就是说 function 可以 "捕获" 任何尺寸的可调用对象, 这正是其奇妙之处. 下面就来简单分析 std::function 的实现方法. 虽然 std::function 是在 C++11 中引入的, 但作为一个基本实现的分析, 本文将排除所有 C++11 的特性以避免不必要的解释. 当然, 这样会产生一个硬伤: 由于可变参数模板特性也是 C++11 中引入的特性, 本文的实现中将不支持任意多个模板类型参数, 而是使用返回值类型加上 2 个参数的类型共计 3 个类型作为模板的类型参数列表. 亦即, 在 C++11 中, 下面的用法是可能的 std::function<double()> f; // 只有返回值类型 <double> 的特化
std::function<int(std::string)> g; // 有返回值类型和 1 个参数类型 <int, std::string> 的特化
std::function<void(int, float)> h; // 有返回值类型和 2 个参数类型 <void, int, float> 的特化
// 可以扩展为任意多个参数类型的特化, 这是 C++11 的新特性
Code Snippet 0-1
// 默认特化没有实现
template <typename T>
class function;
// 实现有返回值类型和 2 个参数类型的偏特化
template <typename Ret, typename Arg0, typename Arg1>
class function<Ret(Arg0, Arg1)> {
// ...
};
语法上, 类似上面的 function<int(int, int)>, class function<Ret(Arg0, Arg1)> 等类似函数签名的模板特化形式并不常见, 虽然它是 C++11 之前就一直存在的语法. 抛开语法层面的部分, function 实现中最重要的就是如何在内部维护不同类型不同尺寸的可调用对象.
Posted at Nov 25 2017 - 04:55:23
Permanent Link:
/p/525
Load full text
|
Post tags:
STL
C++11
C++
|
|
日常的算法 - 顺序统计
顺序统计指的是在一坨 并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同) template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
_Iterator min = begin;
for (++begin; begin != end; ++begin) {
if (*begin < *min) {
min = begin;
}
}
return min;
}
将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数. 在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出 +-------+-----------+-----
| begin | begin + 1 | ...
+-------+-----------+-----
| |
+--( < )--+
/ \
/ \
+----------+ +-------------+ +-----+
| less one | | greater one |--( < )--| max |
+----------+ +-------------+ +-----+
|
| +-----+
+-------------------------( < )--| min |
+-----+
这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率. 下面是实现的例子
Posted at Sep 30 2011 - 09:20:03
Permanent Link:
/p/426
Load full text
|
Post tags:
Generic Programming
STL
C++
Order Statistic
Algorithm
Template
|
|
头文件禁区: C++ 中的 ABI
在 上一篇文章中写到了 C 的 ABI ( application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及. 首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳. 对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到 陈硕老师的 C++ 工程实践: 二进制兼容性和 C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细. 撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. inline 函数或者 template 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如 class Date {
int month;
int day;
public:
int getDay() const;
int getMonth() const;
};
这种情况下, 在使用 Date* date /* initialize */;
date->getDay();
不必担心内存布局耦合, 因为作为非虚的成员函数, Date::getDay() const 这样的函数签名正如 getday(Date const*) 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 inline 一下能提高效率什么的, 而活生生地写成 class Date {
int month;
int day;
public:
inline int getDay() const
{
return day;
}
inline int getMonth() const
{
return month;
}
};
Posted at Aug 31 2011 - 06:52:02
Permanent Link:
/p/404
Load full text
|
Post tags:
C++
Template
ABI
STL
inline
|
|
STL 悲剧之 for_each
这篇文章谈一个我使用 STL 中 for_each 的负面心得. 我对这个东西在当前 C++ 语法下约束是否能广泛使用持有怀疑态度, 至于能否替代所有的 for 循环, 我持完全否定观点! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽. 在 Google 中输入 "for_each" 然后猛击 "I’m feeling lucky", 这时我幸运地跳转到大名鼎鼎的 sgi 的网站里, 页面中有个例子 template<class T> struct print : public unary_function<T, void>
{
print(ostream& out) : os(out), count(0) {}
void operator() (T x) { os << x << ' '; ++count; }
ostream& os;
int count;
};
int main()
{
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
print<int> P = for_each(A, A + N, print<int>(cout));
cout << endl << P.count << " objects printed." << endl;
}
从泛型党的视角看来, 这例子非常不错, 完备而规范地演示了 for_each 的用法. 从此泛型党成了大赢家, 除了 for_each 内部, 外面的代码再也不需要 for 这个关键字了. 而那些说写 C++ 代码像谈话一样简短, 基本上泛型编程完全不及格的程序员, 在写上面功能的时候一般会这样做 int main()
{
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
int i;
for (i = 0; i < N; ++i)
cout << A[i] << ' ';
cout << endl << i << " objects printed." << endl;
}
在喷这个改编版的丑陋之前, 不妨先淡定下来, 想想这个例子到底想做什么, 无非是给个数组 (或者其它什么容器) 把每个成员输出 (或者做个什么其它简单的操作), 并记录被操作的元素个数. 然而, 完成这个操作的代码量与它的功能相比, 臃肿得令人发指. 所以, 在用了几次 for_each 之后, 我完全丧失了当初的激情, 变得极其懒惰, 不愿意把简单的操作抽取到函数外部构造成一个对象然后传递给 for_each; 在维护自己以前写的代码时, 也会偷偷把 for_each 改回 for 循环, 因为有的时候我实在不知道伙伴们把我弄出来的那个函数对象类型给维护到哪里去了. 当然, 我并不认为这是 for_each, 或者 STL, 或者泛型的错. 在我心目中, 泛型思想是风骚的, for_each 的设计是超前的, 问题出在 C++ 语法这个悲剧帝身上, 或者说, 硬要用 C++ 这个传统的面向过程加面向对象语言的语法来包装对象, 来实现类似高阶函数这种函数式编程中的特性, 是悲剧的根源所在. 不仅是 for_each, 连 find_if 等类似的 STL 函数都差不多一样的下场, 与其构造一个精妙绝伦的函数对象类型, 程序员还不如老老实实写个破循环来得实在. 一个振奋人心的消息是, C++ 新标准即将发布了, 它会支持闭包对象, 那样的话, for_each 以及其它函数就不会像现在这么处境尴尬了.
Posted at Apr 17 2010 - 13:17:47
Permanent Link:
/p/81
Load full text
|
Post tags:
C++
STL
for_each
|
|
STL set 悲剧指导
这篇文章谈一个我使用 STL 中 set 容器的负面心得. 是的, 我已经被这丫的杀得超神了, 快来人阻止它吧! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽. 最坏对数时间插入, 删除, 查询, 迭代遍历, 这些听起来都无比诱人, 它们由 STL 中的 set 容器鼎力支持. 然而, set 的只读制度是非常龌龊的, 简而言之, 只要你敢往这个坑里面放, 你就得接受它们以后再也无法修改的命运. 比如下面这段例子 #include <set>
#include <string>
using std::set;
using std::string;
struct student {
string name;
int grade;
student(string const& name_, int grade_)
: name(name_)
, grade(grade_)
{}
bool operator<(student const& rhs) const
{
return name < rhs.name;
}
bool operator==(student const& rhs) const
{
return name == rhs.name;
}
};
int main(void)
{
set<student> students;
students.insert(student("Li Lei", 5));
students.insert(student("Han Meimei", 5));
students.insert(student("Jim Green", 5));
for (set<student>::iterator i = students.begin();
students.end() != i;
++i)
{
++(i->grade);
}
return 0;
}
student 类的 key 是 name, 跟 grade 没有关系, 原则上来说, 修改后者并不会破坏 set 的存储结构. 然而, 编译器一棒子打死, 不许改, 除非剩下的成员全部 mutable 修饰. 只读制度悲剧的根源在于, set 所谓的 key 撑死只是个假象, value_type 这玩意儿就是 key_type 本身. 伪 key 导致的不仅仅是不能改, 重要的是还不能查! 看看 set::find 函数的参数, 要的又是阴魂不散的 key_type. 这意味着什么? 意味着 Han MM 同学报出她名字的时候, 还查不出她几年级, 而必须要利用她的名字, 伪造一个充气娃娃放进去才能找到! 看到这里我就败了, 这明摆着就是不让我用 set, 让我转投 map 么? 一个也许可行的方案是 #include <map>
#include <string>
using std::map;
using std::string;
struct student_periphery {
int grade;
};
map<string, student_periphery> students;
这样建模的话也是够狗血的, 如果哪个函数拿着一份 student_periphery 问怎么查出学生姓名, 那就更悲剧了.
Posted at Mar 12 2010 - 08:34:52
Permanent Link:
/p/79
Load full text
|
Post tags:
set
C++
STL
|
