[置顶] 本站内容链接(2007-7-6 2:43:00)

您现在访问的是

算法驿站 powered by 编程爱好者网站

这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下，开始不叫这名字，后来才慢慢感觉到‘算法’的威力，而‘驿站’是指作者我也是在学习，大家一起学习的这个过程。

有这样一种说法，先不说它的正确与准确性，至少还是有些道理的，就是，程序=数据结构+算法，程序就是一段指令，看看现在的计算机技术，从硬件的描述语言，汇编，高级语言，脚本，其实可以都认为是‘程序’，及程序就是计算机的全部，就算你是做硬件的人，你用CAD吧，你会从逻辑门开始设计吗？可编程逻辑器件，什么Intel8253之类，你做单片机，你会从汇编开始吧，或者是C语言，你不会去做那个片（我国国内好像还不能做'片'），拿到一堆APIs就开始干活，无非是2个8位拼成16位，还不就是做程序，好，你做程序员，就算你做系统程序员，你写个OS之类的，下面也是用别人做好的指令，你不会去设计微指令吧，流水线也不用管，cache也透明，剩下的东西，还不就是编程，做应用程序员，站在XP上干活，站在linux上干活，到你去做的事情，还是编程。我想说的是，‘程序’可以代替一个词‘逻辑’，而逻辑就是计算机的全部，至少当前的冯计算机，不同的只是大家所处的层次不同（越低级的人越少，但是我不同意越赚钱）。

而程序是=数据结构+算法，数据结构是精心地准备好数据，将那些信息以一定的形式一定的逻辑组织在一起，以使算法的效用达到最大，算法是所有程序的核心，可以看成程序本身，也可以这样比，算法是无形的，而程序是有形的，不管你如何实现，算法是发挥最大作用的东西，而程序是算法的某个实例。

做IT这行，只要是做技术的，只要把算法学好，动手能力强，不管做哪一行（计算机行也分很多）都会很吃香，剩下的只是工具的问题，实现的具体环境，熟能生巧嘛，越是高级的工具其实越容易上手，少数可能门槛比较高，但也都没有算法本身重要。

好了不多说了，本文是想把小站的内容做个链接，做个目录，以下是目录。

目录

1 基础算法

排序由浅入深（一）::选择排序
排序由浅入深（二）::交换排序
排序是算法的切入点，这两篇可能也没什么深度，现在看，那些个经典的排序算法，要时刻牢记于心，那会是一种算法设计泛型，比如快排，归并，基数排序，桶排等。

穷举搜索::回溯与深搜
分酒问题-搜索解法
就是一个DFS，图的深度搜索，基础。后面是一个好玩的例子。

贪心算法::启发式搜索
马踏棋盘的贪心算法
当时有些不太清楚，其实贪心和启发式还是有区别的，贪心是一种分阶段决策，和DP很是相同，但是更简单，往往只要从一个有序元组中依次选择决策，或从堆中动态选择，常见的最小支撑树啊，最短路径Dijkstra，都算是贪心，贪心算法现在还没有充要条件可以判别，就是在何时可以贪心。启发式，实际上就是做局部最优选择，可以是在搜索过程中，比如那个马遍历,但他不同于多阶段决策。

分治的实现::递归程序设计
想表述一下‘递归’的思想，分治的思想是整个算法设计的精髓，最简单的二分，二进制，有很多优秀的或者说伟大的算法里都有这些思想的影子，比如FFT，快排等。

最短带权路径问题的解法::Dijkstra & Floyd
两个确定的基本的最短路径算法。

公历历法::星期算法
当时研究出来比较兴奋，也没学初等数论的基础，中国人应该了解一下同余理论，扫扫盲吧。这个算是很简单的，比起证明费马小定理是不是容易很多。

满足任意精度的概率事件发生器
产生任意范围内的等概率随机数
满足任意概率密度函数分布的随机变量生成算法
这三篇的水平只能算是中学对概率理解的水平，当时还没学《概率论》，对随机数的发生，其实现在还不完全了解，应该是用相关度描述的，至于很好的随机数发生器，要到了专门学密码学的时候才会了解到，不知道有没缘了。第三个，其实早有了蒙特卡罗方法，只要有了U[0，1]的随机数，再知道了概率函数的反函数，就可以简单模拟了，但实际中有很多概率函数是积分形式，反函数没有简单形式，就只好单独对待了，比如高斯分布，有一个函数变换的方法和一个蒙特卡罗方法，有时间写一篇吧。

树的计数公式推导
这个叫catalan数，写的时候还不知道这东西，和离散卷积有关系。

CRC循环冗余校验码
好像是计算机网络时学的，后来又学信息论认识到了，一种线性分组码。

模式匹配的KMP算法详解
带通配符*,?的模式匹配
模式匹配基础东西。如果是模式识别，以我现在的数学水平还不够研究。后一篇有BUG，感谢那位网友指出来。

最长递增子序列问题的求解（LIS）
我转来的一篇，重复的东西也不用写了，写得很好。

Euclid算法与RSA
主要是讲如何求解同余方程xa=1(mod b)的Euclid算法。有一位网上朋友联系过我，说用我的代码不能过OJ，他也没发现问题在哪，如果你发现了，请告诉我。

基础算法还缺一些内容，比如非常重要的程序设计泛型DP。

2 中级算法

和基础算法不同，有些算法比较偏，更像是某种数学或某个方面的专门算法。

最小二乘法线性回归
最小二乘算得上一种数学方法吧，用处非常广泛，又何止只能线性回归呢？我们泛涵考试的最后一题就是求L2[0,1]上exp(x)的最佳三次多项式，由于是2范线性空间，恰好就是最小二乘。

幂极数在近似计算上的应用
数学分析2考完时写的，算是我对数值分析的启蒙认识吧，用我们数分老师的话说，那门课就是‘泰勒级数打天下’，连续的东西化成离散的，其实都是相通的，理论数学慢慢向实用靠近了。

博弈与人工智能
最小最大原理与搜索方法
估值函数与优化搜索
置换表与迭代加深
一个暑假突然迷上了人机博弈，写得比较空洞，文章中没有具体代码。当时做了一个黑白棋，后来觉得估值估得好还真不容易，不过至少对一个没学过黑白棋的人是可以轻易下赢的，我让我大堂哥和她走，他的结论是很需要脑筋，经常被我的程序翻盘。听他评价我的程序，真是开心。PS，人机的对弈本质上还是搜索，对弈树的搜索。

了解遗传算法
就是简单的表达了一下，遗传算法是怎么样的，收敛性，收敛速度都没任何表述，还没到那水平。

关于人工神经网络
也是对神经网络非常朴实的认识。下学期有选这门专业课。在我看到的一篇论文里他和遗传算法、模拟退火算法、模糊数学一同被称为先进算法。可能是因为他们都是非常成功的算法，但都有一些理论上遗留的未解决的问题吧。

[转]模拟退火算法求解TSP问题
转载的，写得很通俗易懂，SAA用于组合优化的有效方法。

A*高效搜索算法
搜索方法小结
两篇讲搜索的。A*是一种带启发式高效搜索算法，它的启发式带有某种预见性，因此可看成是智能搜索算法。

牛顿插值算法与实现
多项式插值，牛插是很容易计算机实现的一种算法。

香农编码
照香农老大的说法，编码的平均最优码长是以它的信息熵为下界的，通常情况下，哈夫曼编码也不是最优编码，只能是近似最优，因为编码必须是整数个符号，而哈夫曼编码的缺点是编码长短不一，香农编码是另一种编码，还有扩展码等。

Romberg算法求数值积分的原理与实现
我已经在不止一次课程设计里使用过这个算法了。有着变步长，可控制精度，收敛速度快诸多优点。

Fibonacci数列的计算
比较了几种算法实现的优劣，主要是介绍一种矩阵算法。

Priority Queue - Binary Heap
FibonacciHeap的C++模板实现
优先队列，我最喜欢的数据结构之一。

单纯形法性规划问题求解器
LP问题的有效求解方法，虽然最差情况下是NP的，但LP问题不是NP的，相反有人提出的in P的算法在实际中还不如单纯形法有效。

简单方法算pi和e，计算到小数点后面一万位
FFT乘法和高精运算库(1)
FFT乘法和高精运算库(2)
高精度的算法。

解线性方程组的一些方法
直接消元的，迭代的，和一些解特殊方程的方法。

其它的还有一些OJ上的题解，但是我做得不多，没什么影响力，还有一些就是学工具的，比如VC啊之类，原谅我把这些也滥竽充数放在这里吧。

最后希望这个小站能够带您在算法的广阔空间里自由飞翔！再引一位网友的签名结尾吧：算法如此多娇,引无数天才竞折腰。

阅读全文(5568) | 评论:15 | 复制链接

泛型数值STL算法(2008-12-15 15:07:00)

iota(first, last, value)
返回void，对于0 <= n < (last - first)，*(first + n) = value + n

accumulate(first, last, init)
返回s，s = init + *first + *(first + 1) + ... + *(last -1)
accumulate(first, last, init, pred)
返回s，s = pred(pred(...pred(pred(init, *first), *(first + 1)),...), *(last - 1))

inner_product(first1, last1, first2, init)
返回s，s = init + *first1 * *first2 + *(first1 + 1) * *(first2 + 1) + ... + *(last1 - 1) * *(first2 + (last1 - first1) - 1)
inner_product(first1, last1, first2, init, pred1, pred2)
返回s，s = init pred1 *first1 pred2 *first2 ...

partial_sum(first, last, result)
返回result+(last-first)，对于0 <= n < (last-first)，*(result + n) = accumulate(first, first + n, 0)
partial_sum(first, last, result, pred)
返回result+(last-first)，对于0 <= n < (last-first)，*(result + n) = accumulate(first, first + n, 0, pred)

adjacent_difference(first, last, result)
返回result+(last-first)，*result = *first，对于1 <= n < (last-first)，*(result + n) = *(first + n) - *(first + n - 1)

adjacent_difference(first, last, result, pred)
返回result+(last-first)，*result = *first，对于1 <= n < (last-first)，*(result + n) = pred(*(first + n), *(first + n - 1))

power(x, n)
返回p，p = x * x * ... * x
power(x, n, pred)
返回p，p = x pred x pred ...

阅读全文(1611) | 评论:4 | 复制链接

SortingSTL算法(2008-12-15 15:05:00)

sort(first, last)
返回void，对[first, last)排序，要求随机访问迭代器
sort(first, last, comp)
返回void，对[first, last)排序，要求随机访问迭代器，使用comp比较（下略）

stable_sort(first, last)
返回void，稳定的排序，对于相等的元素排序前和排序后不会改变先后关系
stable_sort(first, last, comp)

partial_sort(first, mid, last)
返回void，局部排序，选最小的(mid-first)个元素放在有序的[first, mid)中，[mid, last)中的剩余元素顺序未定义
partial_sort(first, mid, last, comp)

partial_sort_copy(first, last, rfirst, rlast)
返回rfirst+n，n=min{(last-first), (rlast-rfirst)}，从[first, last)中选最小的n个元素放在[rfirst, rlast)中
partial_sort_copy(first, last, rfirst, rlast, comp)

is_sorted(first, last)
返回bool，true当[first, last)为升序，否则false
is_sorted(first, last, comp)

nth_element(first, nth, last)
返回void，相当于一次划分，以nth大元素为pivot的一次partition，其中[first, nth)中不存在元素i，*nth < *i，[nth, last)中不存在元素j，*j < *nth，他们中的元素不保证有序
nth_element(first, nth, last, comp)

lower_bound(first, last, value)
返回最远的i，使对于j在[first, i)中 *j < value is true
lower_bound(first, last, value, comp)

upper_bound(first, last, value)
返回最远的i，使对于j在[first, i)中 value < *j is false
upper_bound(first, last, value, comp)

equal_range(first, last, value)
返回make_pair(lower_bound(...), upper_bound(...))
equal_range(first, last, value, comp)

binary_search(first, last, value)
返回bool，true当[first, last)中存在value，否则false
binary_search(first, last, value, comp)

merge(first1, last1, first2, last2, result)
返回result + (last1 - first1) + (last2 - first2)，归并[first1, last1)和[first2, last2)
merge(first1, last1, first2, last2, result, comp)

inplace_merge(first, mid, last)
返回void，就地归并[first, mid)和[mid, last)为[first, last)
inplace_merge(first, mid, last, comp)

includes(first1, last1, first2, last2)
返回bool，true当[first2, last2)包含在[first1, last1)中，否则false
includes(first1, last1, first2, last2, comp)

set_union(first1, last1, first2, last2, result)
返回result+n，n个联合后的元素，联合不同于归并，相同的元素只联合一次
set_union(first1, last1, first2, last2, result, comp)

set_intersection(first1, last1, first2, last2, result)
返回result+n，n个求交后的元素，对[first1, last1)和[first2, last2)求集合交集
set_intersection(first1, last1, first2, last2, result, comp)

set_difference(first1, last1, first2, last2, result)
返回result+n，n个求差后的元素，对[first1, last1)和[first2, last2)求集合差
set_difference(first1, last1, first2, last2, result, comp)

set_symmetric_difference(first1, last1, first2, last2, result)
返回result+n，n个运算后的元素，对A=[first1, last1),B=[first2, last2)，结果为(A-B)并(B-A)
set_symmetric_difference(first1, last1, first2, last2, result, comp)

push_heap(first, last)
返回void，将*(last - 1)压入堆[first, last - 1)中，前提是[first, last - 1) is_heap
push_heap(first, last, comp)

pop_heap(first, last)
返回void，将最大的元素pop到*(last - 1)，[first, last - 1)仍然 is_heap，前提是[first, last) is_heap
pop_heap(first, last, comp)

make_heap(first, last)
返回void，生成一个堆[first, last)
make_heap(first, last, comp)

sort_heap(first, last)
返回void，对一个堆排序，前提是[first, last) is_heap
sort_heap(first, last, comp)

is_heap(first, last)
返回bool，true如果[first, last)是堆，否则false
is_heap(first, last, comp)

min(a, b)
min(a, b, comp)
max(a, b)
max(a, b, comp)
略

min_element(first, last)
返回i，区间[first, last)中最小
min_element(first, last, comp)

max_element(first, last)
返回i，区间[first, last)中最大
max_element(first, last, comp)

lexicographical_compare(first1, last1, first2, last2)
返回bool，true如果[first1, last1)按字典序列小于[first2, last2)
lexicographical_compare(first1, last1, first2, last2, comp)

lexicographical_compare_3way(first1, last1, first2, last2)
返回int，它是strcmp()的泛型，返回3种结果表示三种关系，小于，等于和大于。

next_permutation(first, last)
返回bool，true如果下一个排列存在，否则false，计算下一个排列
next_permutation(first, last, comp)

prev_permutation(first, last)
返回bool，true如果上一个排列存在，否则false，计算上一个排列
prev_permutation(first, last, comp)

阅读全文(1240) | 评论:3 | 复制链接

质变STL算法(2008-12-5 14:26:00)

copy(first, last, result)
返回result+(last-first)，拷贝[first, last)到[result, result + (last - first))，注意这些运算符：*result = *first; ++first, ++result

copy_n(first, n, result)
返回result+n，拷贝[first, first + n)到[result, result + n)

copy_backward(first, last, result)
返回result-(last-first)，拷贝[first, last)到[result - (last - first), result)

swap(a, b)
返回void，交换a,b

iter_swap(a, b)
返回void，等同于swap(*a, *b)

swap_ranges(first1, last1, first2)
返回first2+(last1-first1)，交换区间[first1, last1)，[first2, first2 + (last1 - first1))

transform(first, last, result, op)
返回result+(last-first)，对于0 <= n < (last - first)，*(result + n) = op(*(first + n))
transform(first1, last1, first2, result, bi)
返回result+(last-first)，对于0 <= n < (last1 - first1)，*(result + n) = bi(*(first1 + n), *(first2 + n))

replace(first, last, old_value, new_value)
返回void，替换[first, last)中*i == old_value的*i = new_value
replace_if(first, last, pred, new_value)
返回void，替换[first, last)中pred(*i) is true的*i = new_value

replace_copy(first, last, result, old_value, new_value)
返回result+(last-first)，对于0 <= n < (last - first)，if *(first + n) == old_value then *(result + n) = new_value, otherwise, *(result + n) = *(first + n)

replace_copy_if(first, last, result, pred, new_value)
返回result+(last-first)，对于0 <= n < (last - first)，if pred(*(first + n)) is true then *(result + n) = new_value, otherwise, *(result + n) = *(first + n)

fill(first, last, value)
返回void，对于i在[first, last)中，*i = value

fill_n(first, n, value)
返回first+n，对于i在[first, first + n)中，*i = value

generate(first, last, gen)
返回void，对于i在[first, last)中，*i = gen()

generate_n(first, n, gen)
返回first+n，对于i在[first, first + n)中，*i = gen()

remove(first, last, value)
返回new_last，删除对于i在[first, last)中*i == value的元素，[first, new_last)为结果，且保证原来有序的值继续有序（稳定的），未定义[new_last, last)的内容

remove_if(first, last, pred)
返回new_last，删除对于i在[first, last)中pred(*i) is true的元素，[first, new_last)为结果，且保证原来有序的值继续有序（稳定的），未定义[new_last, last)的内容

remove_copy(first, last, result, value)
返回result_last，删除对于i在[first, last)中*i == value的元素，[result, result_last)为结果，且保证原来有序的值继续有序（稳定的）

remove_copy_if(first, last, result, pred)
返回result_last，删除对于i在[first, last)中pred(*i) is true的元素，[result, result_last)为结果，且保证原来有序的值继续有序（稳定的）

unique(first, last)
返回new_last，删除i在[first + 1, last)中，*i == *(i - 1)的元素，[first, new_last)为结果
unique(first, last, pred)
返回new_last，删除i在[first + 1, last)中，pred(*i, *(i - 1)) is true的元素，[first, new_last)为结果

unique_copy(first, last, result)
返回result_last，删除i在[first + 1, last)中，*i == *(i - 1)的元素，[result, result_last)为结果
unique_copy(first, last, result, pred)
返回result_last，删除i在[first + 1, last)中，pred(*i, *(i - 1)) is true的元素，[result, result_last)为结果

reverse(first, last)
返回void，翻转[first, last)

reverse_copy(first, last, result)
返回result+(last-first)，翻转[first, last)后copy到[result, result + (last - first))

rotate(first, mid, last)
返回result_last=first+(last-mid)，视[first, last)为一个环，旋转后从mid开始为新的first，[first, result_last)为原来的[mid, last)，[result_last, last)为原来的[first, mid)
【VC2005中返回void】

rotate_copy(first, mid, last, result)
返回result+(last-first)，旋转后copy到[result, result + (last - first))，[first, last)不变

random_shuffle(first, last)
返回void，随机洗牌[first, last)

random_sample(first, last, ofirst, olast)
返回ofirst+n，n=min{(last-first), (olast-ofirst)}，随机抽样，每个样本只在[first, last)中抽一次

random_sample_n(first, last, out, n)
返回out+m，m=min{(last-first), n}，随机抽样
random_sample_n(first, last, out, n, rand)
返回out+m，m=min{(last-first), n}，随机抽样，随机函数由rand()指定

partition(first, last, pred)
返回middle，划分[first, last)序列，使i在[first, middle)中pred(*i) is true，而j在[middle, last)中pred(*j) is false

stable_partition(first, last, pred)
返回middle，划分[first, last)序列，使i在[first, middle)中pred(*i) is true，而j在[middle, last)中pred(*j) is false，并且是稳定的

阅读全文(1358) | 评论:3 | 复制链接

非质变STL算法(2008-12-3 19:03:00)

for_each(first, last, pred)
返回pred，对所有i在[first, last)中，执行pred(*i)

find(first, last, value)
返回第一个i在[first, last)中，*i == value

find_if(first, last, pred)
返回第一个i在[first, last)中，pred(*i) is true

adjacent_find(first, last)
返回第一个i, *i == *(i + 1)
adjacent_find(first, last, pred)
返回第一个i, pred(*i, *(i + 1)) is true

find_first_of(first1, last1, first2, last2)
返回第一个i在[first1, last1)中，且*i == *any[first2, last2)
find_first_of(first1, last1, first2, last2, pred)
返回第一个i在[first1, last1)中，且pred(*i, *any[first2, last2)) is true

count(first, last, value)
返回i的个数，*i == value
count(first, last, value, n)
返回void, n = count(first, last, value)

count_if(first, last, pred)
返回i的个数，pred(*i) is true
count_if(first, last, pred, n)
返回void, n = count_if(first, last, pred)

mismatch(first1, last1, first2)
返回第1个pair(i = first1 + n, j = first2 + n)，*i != *j
mismatch(first1, last1, first2, pred)
返回第1个pair(i = first1 + n, j = first2 + n)，pred(*i, *j) is false

equal(first1, last1, first2)
返回true当且仅当2序列完全相同，否则false
equal(first1, last1, first2, pred)
同上，相同函数由pred(*i, *j)比较是否相等

search(first1, last1, first2, last2)
返回第一个i在[first1, last1)中，equal(i, i + (last2 - first2), first2) is true
search(first1, last1, first2, last2, pred)
返回第一个i在[first1, last1)中，equal(i, i + (last2 - first2), first2, pred) is true

search_n(first, last, n, value)
返回第一个i在[first, last)中，且[i, i + n)全为value
search_n(first, last, n, value, pred)
返回第一个i在[first, last)中，且j在[i, i + n)中,pred(*j, value) is true

find_end(first1, last1, first2, last2)
返回最后一个i在[first1, last1)中，equal(i, i + (last2 - first2), first2) is true
find_end(first1, last1, first2, last2, pred)
返回最后一个i在[first1, last1)中，equal(i, i + (last2 - first2), first2, pred) is true

阅读全文(1039) | 评论:1 | 复制链接

很久没来了,喘个气(2008-9-10 16:15:00)

对多个资源操作时,一次全部申请(等待),是最简单的防止死锁的方法,一次全申请并不会影响性能,如果占有时间不长的话~

Semaphore是对一种资源可同时占用的数量的描述,即被多少个线程使用,如果最大数为1,就是一个Mutex, binary semaphore~

中秋快乐~~

阅读全文(1213) | 评论:1 | 复制链接

幻想中的typeof(2008-7-5 1:16:00)

我想我的BLOG是不是要改名字了，还是C++相关。

想研究boost::lambda源码，找到这篇文章：http://www.cppblog.com/shifan3/archive/2006/06/09/8334.html 还算写得不错，通俗啊，我写不出这样的文章，本来是带着一个问题去的，就是关于函数对象的返回类型如何确定。嗯，先从我对lambda库实现的想法说起吧。

简单描述，lambda库是用函数对象重新对程序进行编码。什么是程序的编码，程序是什么，C++程序？包括三个方面：面向类类型的表达式（泛型的），函数（包括成员函数）和控制语句（if,then,while等）。lambda的结果是，让‘程序’重新以‘函数’的方式存在。靠，C++语言并不是函数式语言，整个库出来实现函数式，太牛了。

1种幻想，如果lambda获得了成功，成了新的C++标准，那可否从C++语言的层面直接支持函数，比如定义一个函数本身就在定义一个函数对象！。。。不太可能，这需要支持和改变的东西太多了，是彻底的改变，那还要那些函数式语言干嘛~~

转到lambda的实现，那三个方面又是以表达式为核心的，绑定后的函数还是可以构造表达式，控制语句完了还是可以构造表达式。它的最基础的技术就是表达式模板技术。

表达式模板技术又不好一言两语说清楚，我写过一个Vector的表达式模板，有一些感悟。首先，确定构造后的表达式用来干什么，比如数组的表达式，用来数值计算，所以要定义哪些接口，这个接口是自上而下调用的，不管表达式有多复杂，都会自上而下的调用。lambda的表达式目的很明确，用来函数调用，所以要有operator()接口，那么它又多了一条本质，lambda表达式是一个函数对象。那你要问它有多少个参数？返回参数如何确定？多参数应该是不确定的，没有很好的方法，只能是定义足够用那么多，用宏控制，比如我定义最多十个参数的operator()，那就要从operator()(A1)一直定义到operator()(A1,A2,...A10)这么多。返回类型迟一点再说。

然后是设计托管的泛型的运算符类，比如：

template<typename Arg1,typename Arg2>
class Mult
{
  Arg1 arg1;
  Arg2 arg2;
};

表示运算符*的托管类，它有两个泛型的参数成员，这里有一个问题，构造问题，我们的目标是要让它‘轻量级’构造，用引用，引用构造，引用的本质是取地址，那对于一些常量，比如程序中的123，就不能取地址。我们用一个trait，它到底是一个引用还是原来类型，从trait里获得。此外，常量值我们最好还用一个类来专门托管。

所有的运算符托管类和常量托管类，都要是一个接口一致的函数对象。然后再构造表达式编码。

如果只有一种运算符托管类，我们要重载多少个它的运算符操作？如果是二元运算符，以Mult为例，包括Mult*Mult，Mult*常数，常数*Mult，三种。如果增加一种，比如Add，那要重载多少？增加的有：Add*Add,Add*常数，常数*Add，Add*Mult,Mult*Add，还有Add+Add,Add+常数，等，非常之多。如果再多重载一些，恐怕就算用宏生成代码也要一大堆代码，所以再在这之上包装一下，我的Vector里用的是Exp：

template<typename Rep>
class Exp : public Rep
{
public:
    Exp(Rep const& r): Rep(r) {}
    Rep& rep() { return *(Rep*)this; }
};

让它继承至Rep是很好的选择，即继承了Rep的所有接口，如果做成员，那还要在这里添加接口的实现了。Exp<T>本质即是T，有T的接口，也只有T在其内部，于表于里都是T。有了它就可以简化运算符的重载了，让所有的运算符都针对它重载即可。成员rep()是还原函数，解除封装，将*this指针简单转型即可，也没有其它浪费的内存。

关于占位符_1,_2等，它们是特殊的函数对象，对它们调用operator()的时候返回第X个参数的引用即可。

好了，到了关键的返回值类型了，这很头疼，比如Mult的operator()如下：

template<typename A1,typename A2>
XXX operator()(A1 const& a1, A2 const& a2);

两个什么玩艺相乘，结果是什么类型和这是两个什么玩艺有关，比如：1<<10和cout<<10，同样是operator<<，前者的返回类型是整型，而后者是ostream&。很无奈只能用trait，所以我才想能不能用typeof这样的好东西：

幻想中的typeof:

typeof(表达式)

在编译期计算表达式的返回类型，当然也可以模板化，最终具现的时候一一计算。这很容易实现，比如A1=Vector<int>,A2=int，然后又查找到Vector<int> operator*(Vector<int> const&,int);的申明，所以typeof(A1*A2)就是Vector<int>，所以就可以这样简单的写：

template<typename A1,typename A2>
typeof(A1*A2) operator()(A1 const& a1, A2 const& a2);

返回类型应该和运算符类型相关，如果用trait来实现的话，但是为了设置自己的类型的返回类型又要专门放在外面好一些。

最后一个问题是const和非const的问题，也很苦恼，简单的解决方法是统一一下。

阅读全文(1721) | 评论:0 | 复制链接

C++中的指针(2008-6-28 22:18:00)

C++的指针有4种：指向数据，指向函数，指向成员数据和指向成员函数；为什么不分两种，指向数据和指向函数，这个前2种和后2种不能一对一。可以这么分，指向非成员和指向成员，指向成员的简称成员指针。以下一一说明。

1，指向数据的指针

非常简单。例如：

int a = 100;
int *p = &a;
cout<<*p<<endl;

2，指向函数的指针

函数名可以看成是一个单身函数对象，取值后是函数的入口地址，如：

void foo(int a)
{
}

foo看成是一个类型是void (int)的单身对象，但是对名字foo取值后，它会退化成相应的指针类型void (*)(int)。注意那个括号不能少。当然如果对foo取地址也是这个类型（取两次？没考虑过~~哇靠~太绝了吧）。

所以指向函数的指针，申明起来比较怪，像这样：

void (*pf)(int) = &foo;

申明一个类型是void (*)(int)的函数指针pf，并初始化为&foo，这里的函数参数类型形式和返回类型要和foo的声明一致。再多一个例子吧：

int foo2(float a,double b)
{
    return 0;
}

int (*pf2)(float,double) = &foo2;

函数指针的使用，两种方式：

(*pf)(100);

即，先引用*，打括号，再传实参调用，或者直接，pf(100)。

函数指针的意义：一个函数可以看成是一个策略，对于一个问题，可以采用不同的策略和方法，这种对策略的选择推迟到运行期，即用一个变量保存起来，在程序跑起来的时候，决定使用什么策略，其本质即是动多态，对一个函数的调用延迟到运行时决定。

3，指向成员数据的指针

在要说成员指针之前，要先明确一个概念：名称的受限。C++有一套自己的名称查找机制，一个名称可以是一个类名，对象名，函数名等。受限是指是否用::,->,.中的一种符号作用。

看一般的成员数据访问：

struct A{int a;};

A a;
A* p=&a;
cout<<a.a<<p->a<<endl;

当然类A的定义和下面三条语句不是在一起的，a.a是正确的名称，第一个a没有受限，指对象a，第二个a受限了，是在一个前提下进一步指成员A::a，这里就是a的成员A::a。再举个例子：

struct A
{
    A(int a)
    {
        this->a=a;
    }
    int a;
};

受限的名称要受前面的名称作用，如果a没有确定，那a.a就不能确定，确定a可以使用指针，当然确定a.a也可以使用指针，即成员指针。题外话，在模板中如果一个名称被一个包含模板参数的表达式限制，即被一个不确定的东西限制，那它的绑定将延迟到模板的实例化时，如果表示类型，要前加typename，如果表示成员模板，要在.和->后加template。比如一个模板类（或者叫类模板）中的成员函数中的this指针，实际上它的类型是不确定的，如：

template<typename T>
class V
{
};

的this是V<T>*类型的。

转到正题。成员指针实质上是成员数据的偏移。像这样定义：

int A::*p;

它不能直接指向一个数据，因为它必须要是一个受限的名称，它只能指向一个类的成员，它像这样赋值和初始化：

p=&A::a;

它不能单独使用，因为单独使用的时候是非受限的，要先定义一个A的对象，再限制使用：

A a(100);
cout<<a.*p<<endl;

它必须放在一个限制式的右边。用几个例子来说明一下：

A a(100);
A *p1=&a;
int A::*p2=&A::a;
cout<<p1->*p2<<endl; //实际访问了a.a

另外一个含内套类的复杂一些的例子：

struct A
{
    A(int _a,int _b): a(_a),b(_b)
    {
    }
    struct B
    {
        B(int _b): b(_b)
        {
        }
        int b;
    };
    int a;
    B b;
};

int main()
{
    A a(1,2);
    A *p1=&a;
    A::B A::*p2=&A::b;
    int A::B::*p3=&A::B::b;
    cout<<*p1.*p2.*p3<<endl;
    return 0;
}

4，指向成员函数的指针

如果（3）弄清楚了这个也应该很明白了，成员函数默认绑定this指针，即成员函数名也是一个受限的名称。它的定义和一般的函数定义类似，只是在指针前加上一个类名和::。

struct A
{
    A(int a)
    {
        this->a=a;
    }
    void foo(int)
   {
   }
    int a;
};

A a;
void (A::*pf)(int) = &A::foo;
(a.*pf)(100);// 相当于调用a.foo(100)

使用和（3）一样，完了再括起来传参调用函数，这个时候不能使用另外一种调用形式了，即不能这样调用：a.pf(100)，即使pf是A的成员数据也不可以，例如：

struct A
{
    A(): pf(&A::foo1) {}
    A(int): pf(&A::foo2) {}
    void foo1(int)
    {
        cout<<"foo1 is called"<<endl;
    }
    void foo2(int)
    {
        cout<<"foo2 is called"<<endl;
    }
    void foo()
    {
        (this->*pf)(0);
    }
    void (A::*pf)(int);
};

int main()
{
    A a,b(0);
    a.foo();// 输出 foo1 is called
    b.foo();// 输出 foo2 is called
    return 0;
}

为什么不能默认使用pf呢？pf是A的成员，按理说会有隐含的this->在前面，如果foo()里换成：(*pf)(0);，会编译错误。原因是，pf是成员，但*pf不是，如果像后者那样调用，它相当于：(*(this->pf))(0)。直接引用了成员指针。

另外，static成员数据和成员函数不能用成员指针，它们不认为是对象的一部分，它们可以直接用一般指针访问，当然它们也是受限的名称，但是受一个类名限制和对象名无关。

阅读全文(2190) | 评论:0 | 复制链接

Who's my friend[C++友元点滴](2008-6-20 21:13:00)

我不知道关于C++关键字friend的全部议题有多少，我只对我了解的做个小结。

1，friend申明一个友元

friend一般为一句申明式，它位于一个类的内部，它申明一个类或者一个函数为该类的友元。friend并不是定义一个成员函数，所以friend放在public,protected或者private前都可以，完全是一样的。做为一个友元，即表示在该类或者该函数内部可以访问这个类的私有成员，你和朋友之间是不是应该没有什么隐藏的呢。例子：

class A
{
public:
 A(int _a) : a(_a) {}
 friend void test(A&);
 friend class B;
private:
   int a;
};

void test(A& x)
{
 x.a=100;//拥有私有成员a的访问权限
}

class B
{
public:
  void foo();
};

如果friend申明式为一般的非模板类或者函数，则该处可以为首次申明。对于一个类，只能是申明式，对于函数，可以是它的定义式。

class A
{
public:
 A(int _a) : a(_a) {}
 friend void test(A& x)
 {
    x.a = 100;//定义::test()友元函数
 }
 friend class B;
private:
   int a;
};

注意尽管将函数的定义式放在类内部，但它并不是一个成员函数，对于省略受限的定义形式它将成为一个全局函数::test()，当然你也可以申明另外一个类的成员函数为友元，如：

class A
{
public:
 A(int _a) : a(_a) {}
 friend void B::foo();
private:
   int a;
};

总的来说，如果你想在哪里访问类A的私有成员，就在类A内写上一句该处的申明式，并在前面加上friend关键字。

这是一般情况，很简单，但是它会破坏封装的初衷，所以尽量少用；Effective C++中有一个应用的例子，对一个类定义的二元操作符，如果你希望它能对操作数都进行隐式转化，那么就定义一个全局函数，并申明成该类的友元。

2，模板函数作友元

先给一个模板函数，它是一个模板，并不是一个函数：

template<typename T>
void foo1(T);

在定义foo1为某类的友元时，或者要实例化模板参数T，或者给出可演绎的申明式，而且就算是可以演绎的，一对尖括号也不能省。如：

class A
{
public:
  friend void foo1<char>(char);
  friend void foo1<>(double);
};

或者给出限制符::：

class A
{
public:
  friend void ::foo1(char);
};

当然，如果有一般函数具有这种形式，那会优先于模板函数匹配。最后这里的申明式都不能是定义式，必须前至申明（定义）。

3，模板类里的友元

模板类里也能申明2中的友元，但是模板类有模板参数，如果利用了这个模板参数的友元申明，就属这种情形。

template<typename T>
class A
{
public:
  friend void foo1<T>(T);
};

但是，在这里，必须要求foo1在这里是可见的，即不能是首次申明式。如果不使用模板参数，那会是一种有趣的情形。

template<typename T>
class A
{
public:
  friend void foo(){}
};

注意这里是一个定义式，它定义了一个::foo()函数为该模板类的友元，在该模板类具现的时候，::foo()也被具现出来，即：

A<int> a1;// ::foo()首次定义
A<char> a2;// ::foo()第二次定义，违背C++一次定义原则

4，友元模板

如果想定义一系列函数为该类的友元，可以使用友元模板。它和模板的申明式类似，只是在template<>后加了friend关键字。

class A
{
public:
 template<typename T>
 friend void foo();
};

5，能否做为定义式

能做为定义式的情况是：非受限，没有前至::，没有模板参数列表，没一对尖括号。如果是模板申明式，不能是首次申明，在该处必须是可见的。

6，一个完整的例子

template<typename T>
class Rat
{
public:
    Rat(T _a, T _b) : a(_a), b(_b) {}
    friend Rat<T> operator*<T>(Rat<T>&,Rat<T>&);
private:
    T a,b;
};

template<typename T>
Rat<T> operator*(Rat<T> & x, Rat<T> & y)
{
    return Rat<T>(x.a*y.a,x.b*y.b);
}

Rat<T>为T类型的有理数类，定义它的相乘运算，定义一个全局函数，并申明为友元，该函数也应该是模板，希望有如上的程序通过编译。在friend式之前没有operator*()的申明，所以这里不能是首次申明，在前面必须加上申明式：

template<typename T>
Rat<T> operator*(Rat<T> & x, Rat<T> & y);

在这之前又没有Rat<T>的申明，再加上：

template<typename T>
class Rat;

通过编译，或者改成友元模板：

template<typename T>
class Rat
{
public:
    Rat(T _a, T _b) : a(_a), b(_b) {}
    template<typename U>
    friend Rat<U> operator*(Rat<U>&,Rat<U>&);
private:
    T a,b;
};

template<typename T>
Rat<T> operator*(Rat<T> & x, Rat<T> & y)
{
    return Rat<T>(x.a*y.a,x.b*y.b);
}

有细微的不同，Rat<T>申明了一系列友元operator*<U>，当然没必要，只要operator*<T>就够了，但是形式上简单一些。还有一种更简单的形式，就是将定义式放在里面，正是Effective C++里使用的方法：

template<typename T>
class Rat
{
public:
    Rat(T _a, T _b) : a(_a), b(_b) {}
    friend Rat<T> operator*(Rat<T>&x,Rat<T>&y) //定义并申明了::operator*()
    {
        return Rat<T>(x.a*y.a,x.b*y.b);
    }
private:
    T a,b;
};

[完]

rickone 2008/06/20

阅读全文(2881) | 评论:0 | 复制链接

C++的const关键字(2008-6-9 18:29:00)

想小结一下const的种种用法和相关知识

1,const修饰数据

见文:const指针和引用

2,const修饰成员函数

表示该成员函数为常量对象调用，首先来看C++的对象和绑定的成员函数是如何实现的。

class A
{
public:
    void Test(int _a)
    {
        a = _a;
    }
private:
    int a;
};

A::Test(int)是A的成员函数，一个函数是一段可执行代码，它和对象的数据是两回事，它只需要一份拷贝，相当于它们是静态的不变的（static），而非static数据成员是可以有多份拷贝，它们是动态的可变的，它们之间如何关联起来？通过this指针，在成员函数内对成员变量调用时会省略this指针，上面的语句相当于‘this->a = _a’而this指针是如何传进成员函数的？this指针如何传进去这不是程序员关心的，有的编译器通过函数第一个参数，比如上面的A::Test(int)实际上是A::Test(A* this,int);函数参数的压栈顺序是反的，从汇编的角度看，就是通过系统栈传递this指针，当然，有的还会通过寄存器，如何传进去的不用担心，结果是它已经传进去了。所以可以这样理解下面的C++代码：

A a;
a.Test(100);

理解为：

A a;
A::Test(&a,100);

好了，这样理解是最好的了，我们来看const成员函数，如果上面代码中a是常量，看看有什么问题：

const A a;
A::Test(&a,100);

由于Test()的第一个参数是A*，&a的结果是const A*，不能将一个指向常量的指针赋给一个一般指针，编译错误。所以简单在Test定义式中尾部加一个const：

    void Test(int _a) const
    {
        a = _a;
    }

就行了，它相当于第一个this参数的类型换成了const A*，即A::Test(const A* this,int);而一个A*指针是可以赋给const A*的。那这样的话，它和没有const修饰的成员函数可以重载了，对，这两种形式是可以重载。

好继续考虑，如果这样的话，const修饰的成员函数有什么不同？

this是一个指向常量的指针，所以this->将得到一些常量类型的成员，即在const修饰的成员函数内，是不能修改成员变量的。（外话，如果你硬要修改也是可以的，可以作const_cast转型，MSDN中有例子；或者由关键字mutable改变）

好了，我把由const修饰的成员函数的作用讲清楚了，两点：1，常量对象调用；2，不能修改成员变量。

设计的时候，是不是不管三七二十都上一个const和非const成员函数？对于一个接口，最小化后的接口集，从一个方面考虑，如果允许常量对象，你会把哪些接口对它开放，将开放的函数先改成const版，看能否全全工作，如果不能再重载一个非const版本。（1）如果你设计的类不允许有常量对象（思考，如何阻止不能产生常量？），所有接口都非const（2）允许有常量对象，对‘常量性操作’开放const成员函数。

3,const和static

const如果和static一起修饰会是什么后果？先看看static吧。它指‘静态的’，和‘常量的’是近义词，但是在程序中的实际意义相差蛮远。一份数据，首先有一个名字，但是同样一个名字，可能有多份数据，而且在不同时刻，数据所在存储区也是可变的，比如一般函数内的局部变量：

int foo(int x)
{
    int a;
    a = x*x;
    return a;
}

这里的a就是可变的，它在运行期只是一个偏移量，从foo()调用的时候，系统栈的栈顶到变量a的偏移量。它随着调用的时刻不同，将在栈中不同的位置出现，甚至在一个递归的函数中，它可以同时在栈中出现多份数据。但是它只有一个名字a，它是‘动态的’。相对这种‘动态’，用static修饰的变量，将只有一份拷贝，即它的名字只指一份数据，在一个程序的一次运行中。但是这个唯一的静态数据，不一定是常量，它可以是变量。const约束一份数据不能被修改，static表明一份数据是独一无二的（static修饰成员函数时表示它们是和对象不相关的，没有this指针，修饰成员数据时表示这份数据只存在一个拷贝，不存在于不同的对象当中）。在类内部使用静态常量，可以像enum或者#define一样用，但是如果你非要取它们的地址，那就必须有它们的定义式，否则将引发连接错误，比如在一个类内部定义了静态常量，可以不在类外部做静态变量定义，而直接使用它们，就像真常量一样。这样说可能比较难理解，看例子吧：

class A
{
public:
    static const int c = 100;
};

void foo(int const& x)
{
}

...
foo(A::c); // 引用传递需要取地址，连接错误
foo(0+A::c);// ok
...

相比于‘真常量’，比如enum和#define，它们只能是右值，即不能取地址，不能修改，甚至是运行期不存在的，而静态常量有同样的效果，如果你不给出它的定义式，如果取了地址就会有连接错误，不取地址就跟真常量一样，是编译期常量，可用于元编程中。一般const修饰只是约束了一般变量，这种约束只在编译期，为了让程序员不要犯错误，要善于利用const，让编译器查出尽可能多的错误；类内静态常量可以只有带初始化的申明式，利用它可以代替真常量。

阅读全文(2126) | 评论:1 | 复制链接