博文

泛型数值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) = *(f......

阅读全文(4388) | 评论: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(fir......

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

质变STL算法(2008-12-05 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......

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

非质变STL算法(2008-12-03 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 e......

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

幻想中的typeof(2008-07-05 01: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;
  Ar......

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

C++中的指针(2008-06-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<&l......

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

Who's my friend[C++友元点滴](2008-06-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;

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

C++的const关键字(2008-06-09 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
    {
 ......

阅读全文(5205) | 评论:2 | 复制链接

C++转型操作符(2008-06-06 22:42:00)

摘要:C++有四种转型操作符,以下小结一下: 1,static_cast<>() 用得最多的,如果转换的是类型,则调用转型函数:比如int转float,float转int等基本数据类型的转型,如果是一个类,就调用类型转换函数,比如: #include <iostream> using namespace std; class A
{
public:
    explicit A(int _a = 0) : a(_a) {}
    operator int() const
    {
        return a;
    }
private:
    int a;
};
int main()
{
    A a(100);
    int b = static_cast<int>(a);
    cout<<b<<endl;
    system("PAUSE");
    return 0;
}; 可以转换一个基类指针到子类指针的转型,但是不做动态类型检查,可以不存在虚函数,因此转型可能是不安全的,但是是快速的。 2,dynamic_cast<>() 专门用于C++类的指针转型,且是用于多态继承体系中的类。public继承体现了‘is-a’的类关系,一个基类指针,可以指向子类对象,它的子类类型是动态类型,dynamic_cast<>()就是将基类指针转型成它动态类型的子类指针,如果类型不对,结果就是空。 #include <iostream> using namespace std; class B
{
public:
   ......

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

数独程序(sudoku boy 2)设计报告(2008-05-07 01:52:00)

摘要:因为一些原因,又把原来写过的数独程序重新翻出来改写。有朋友说原来的就写得不错了,还要改,我改的目的主要是想实践一下C++,尤其是设计方面。 1 面向对象吗? 不知道原来的程序算不算面向对象,一个类,比如class sudoku,有构造函数,求解函数,显示函数,等等,但是总是觉得有些乱,一但有了新的需求,整个代码就看起来像盘散沙。 经过这次的实践,我总结出来的规律是,一个类的设计,要使接口最小化,就是说接口集最小,接口数目最少,为了做到这一点,对类本身就要求,只完成功能上最小单位的部分,一个类,要么封装一些数据(容器),要么封装一个数据(元素),要么做一件事情(功能),容器类,只要设计元素的访问方法,元素类只要一个最小数据结构本身(不包括帮助函数算法的辅助数据结构),数据结构的算法留给专门的类设计(功能)。如何融合它们,数据+算法,干净的数据+干净的算法,用帮助函数,别小看写在类外面的帮助函数,有时候它们比成员函数好用得多,成员函数要么设计得好,要么就是累赘。而帮助函数可以看成是粘合剂,把用户的使用和数据+算法很好的接合起来,同时,又容易改写。还有,容器的设计包含迭代器的设计,这可以为算法更好的抽象出来,算法面向迭代器,迭代器组织数据关系。算法的设计体现在,用仿函数做嵌入式,比如sudoku的构造函数,你可以写这样一个初始化函数: sudoku::init(char* str){...} 实现的时候,就会问,用什么样的格式初始化呢?这样吧: 4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........ 但是有的人做的数独软件就不是这样,比如 400030000
000600800
000000001
000050090
080000600
070200000
000102700
503000040
900000000 那就不好了,你又要重载一个,这样做就相当于,为你的软件增添了‘规则’,而规则越多,越使接口复杂化。解决方法,1,可以是为专门的数据写适配器,把自己的数据定为标准;2,将这件事情,移给高层解决,用仿函数在外面完成。像下面这样: class init_functor
{
publ......

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