九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

vector成员转换为char输出的六种方法,STL的学习过程乱想

容器输出函数printCon测试过程中,想到的,那就是把vector<int>容器换成char形式输出,一下子想到很多方法,都列出来,主要目的当然还是测试printCon函数,另外想到Linus提到的C++复杂到让人有心智障碍了,说是用C++选择太多,功能太多,导致不知道用什么好的一种耽误编程效率的东西,看到实现一个如此简单的东西,方法都如此之多,实在是可以想象,为什么有人,而且是如同Linus这样的牛人会提出这样的观点了。唉,选择多也是罪过啊。。。。。比如我好东西不学习,把时间浪费在想这个简单的东西到底还有别的方法实现没有上去了。。。。如此推知,可知为什么有人批评C++太过学院派,社团以钻研奇怪的看似尖端的技术为乐,实际应用程序编写的简化却一直没有太多进展。。。。。既然方法那么多,我不如不选。。想到怎么实现就怎么实现啊。。。。。作为C++程序员是那么注重效率,一定会研究哪个效率最高的。。。。于是时间又流失了。。。。。。啊门………….下面的printCon函数来自于myself.h这个我自己平时使用的库,可以参考置顶文件。

 

 


#include "stdafx.h"

#include <iostream>

#include <memory>

#include <vector>

#include "myself.h"

using namespace std;

 

int main()

{

      vector<int> ivec;

      for(int i = '1'; i <= 'z'; ++i)

           ivec.push_back( i );

      myself::printCon(ivec,"ASCII value: ");

 

      //利用char类型的流迭代器输出

      cout<<"ASCII type one: ";

      copy( ivec.begin(),ivec.end(),ostream_iterator<char>(cout," ") );

      cout<<endl;

 

      //不知道说利用了什么,其实本质就是利用operator<<的不同重载版本

      vector<char> cvec( ivec.size() );  //通过ivec的大小构建cvec再复制的方法

      copy( ivec.begin(),ivec.end(),cvec.begin() );//复制到cvec后输出就自然变成char

      myself::printCon(cvec.begin(),cvec.end(),"ASCII type two: ");

 

      //考虑到上面提及的情况,应该可以直接调用operator<<char版本

      //原理诈唬,其实不过一个强制转换

      cout<<"ASCII type three: ";

      vector<int>::iterator iIter;

      for(iIter = ivec.begin(); iIter != ivec.end(); ++iIter)

      {

           cout<< static_cast<char>(*iIter)<<" ";

      }

      cout<<endl;

//另外,发现没有强制容器转换的操作符,没有办法,实现一个函数。

//因为不能在main里面实现,所以在最后实现,并在这里声明。

      extern vector<char> ivtocv(const vector<int> &int_vec);

      myself::printCon(ivtocv(ivec),"ASCII type four: ");

 

//当然,其实,直接利用构造函数创建也不是不可以

      myself::printCon(vector<char>(ivec.begin(),ivec.end()),"ASCII type five: ");

 

 

//其实再考虑一下,不知道C++除了强制转换对象外,还有没有强制调用某重载函数的方法

//无聊之极,重载<<输出操作符试试,因为不能在main里面实现,并且不希望干扰前面的操作

//所以在最后实现,并在这里声明。

      extern ostream& operator<<(ostream &os, const vector<int> &int_vec);

//如此,则可以直接输出vector<int>char

      cout<<"ASCII type five: ";

      cout<<ivec;

      return 0;

}

 

vector<char> ivtocv(const vector<int> &int_vec)

{

      vector<char> char_vec;  //另一种通过复制创建char_vec的方法

      copy( int_vec.begin(),int_vec.end(),back_inserter(char_vec));

      return char_vec;

}

 

 

ostream& operator<<(ostream &os, const vector<int> &int_vec)

{

      copy( int_vec.begin(),int_vec.end(),ostream_iterator<char>(os," ") );

      cout<<endl;

      return os;

}

     

 

阅读全文....

C++可怜的内存管理机制漫谈及奇怪补救auto_ptr介绍

       一直以来C++遵循着一种哲学式的美学设计。很重要的一条就是不为你不需要的付出代价。就我目前所知,整个C++仅仅只在虚函数和多重继承中违背了这条原则。很多非常有用的东西都因为这条原理而否定了。因此C++才能保持着一条定律,那就是只要程序员足够厉害,C++可以足够的快,因为程序员几乎掌握着一切可以用来优化的东西。其中,资源回收系统就是因为这样被否决了。以前一直不觉得怎么样,因为C++社群的舆论导向,甚至有目前看来几乎自虐的想法,那就是不因为其他语言容易学而C++难学就说C++不好,还有,C++给了你完全的控制,自由的世界,自然要付出代价!

      当然,很多代价我都可以接受,我也一直接受着小心翼翼的newdelete。无数次,我看到各种类型各种层次的C++书籍,语重心长地告诉我,要避免内存泄露,无数次看到书中指出看似平常的代码中也可能存在的内存泄露问题。今天看《C++ STL》介绍auto_prt的时候,又一次碰到了这个问题。看到书中作者提出的各种灾难后果的时候,心中竟然像看到鬼故事一样的心悸,眼前似乎如看到核武器爆炸一样的恐怖,一时竟然有心惊肉跳的感觉。突然觉得这样下去,不知道什么时候会心脏病发作。

       什么,你笑我连个delete都忘记?假如加上个delete就万无一失那我就什么都不怕了。类似如下代码:

int f()

{

       classA *ptr = new classA;

       switch()

       case:

              return 0;

       case:

              ...   //do some thing

       delete ptr;

}

       一个需要返回的函数碰到分支返回是很正常的,你必须要保证每个分支返回前都必须先delete,而不是放在最后。假如说这种情况还可以通过小心弥补的话。那么看下面的代码:

void f()

{

       classA *ptr = new classA;

       ...   //do some thing

       delete ptr;

}

       即便这样,你也是不能保证内存不泄漏的。计算你不在中途返回,一旦中途出现异常,此函数就会自动终止,内存一样泄漏。如之奈何?

继续小心?保证中途不抛出异常,当然在很长的程序中这是让你痛苦的,不过也不是不能做到。但是看下面的代码:

void f()

{

       classA *ptr = new classA;

       ...   //do some thing,throw()

       g();  //call g()

       delete ptr;

}

       在一个程序中,一个函数调用另一个函数不少见吧,这样你就必须保证g()也不抛出异常,不然效果一样,内存泄漏了!什么?你也去查看g()的代码,保证没有异常抛出?那g()调用了h()呢?如此下去,我只能告诉你,C++中根本就不该加入异常,因为你没有机会使用。

       说了这么多,你能体会到我对内存泄漏的恐惧之情了吗?还没有?继续:

void f()

{

       classA *ptrA = new classA;

       classB *ptrB = new classB;

       delete ptrA;

       delete ptrB;

}

       我如此害怕出问题,我连用都不敢用,赶紧把刚才new出来的家伙都delete了,很遗憾,这还是有可能内存泄漏!当第二条new抛出异常的话,你什么都delete不了了,哪怕你使用程序从来不用异常机制,很遗憾得告诉你,异常机制是深入C++骨髓的,就算你不用,它自己还是时不时会使用的。暂时这么多吧,体会我的感受了吧。。。。。。。。。。。。

       因为C是我学习第一个语言,尔后接着我学习了名字与其比较像的进阶语言,一直没有改过,虽然后来知道,C++不过名字取得比较好,比较像C语言的继承者而已,JAVA其实也是由C演化来的,并且对面向对象的控制比C++好很多,也容易学很多,还有就是现代的程序语言大多都有C的影子。我也从来没有移情别恋,改用JAVA或哪怕更进一步似乎类似C++继承者的C#了。想起偶尔使用的微软托管代码,一个一个在用惯了C++的我看来潇洒无比的new,一个一个无所顾忌的new,真是一下被震撼了,想起自己每次用到new时的心惊胆颤,一时语塞。当然,我不愿放弃对系统的控制,我不愿放弃对内存的操作,但是就一定要接受这样的事实吗?我并不是每次都需要为一个程序进行多么高深的优化啊,特别是对此程序内存中的操作。因为我要掌握住任何对象的生存期,因为我不愿为我不需要用到new时付出任何代价,我就要在我用到new时付出这样惨重的代价。甚至我们不得不用上如auto_ptr这样有着特性的对象来避免内存的泄漏。我不得不说,auto_ptr的特性真的是可以称得上“特”性了。有人会讽刺我,要想那么轻松就直接去用C#算了。从C++转移到C#阵营的又怎么是少数啊,有人甚至说C++正成为边缘化语言,成为学术化语言,C++社群似乎也以C++的难学自豪,以钻研华而不实只能用来演示的技术为爱好。还好,已经听说在C++ 0X标准中已经考虑加入一个可选的自动废料收集了。。。。。。。。哪怕C++ 0X不做其他任何改变,我也非常期待C++ 0X的时代的到来。

C++可怜的内存管理机制中有个奇怪补救措施:标准中唯一的smart point(智能指针)auto_ptrauto_ptr作为标准中智能指针的独苗,实在是太被人呵护和爱戴了。以至于它脾气生得倔强异常,放在C++中怎么看都是各从别的地方突然闯入的异类。为了避免我们心里都被内存泄漏带进可怕的阴影,auto_ptr横空出世了,因为横的利害,我们必须小心的避免它的很多问题,当然,这些问题比起内存泄漏来说,给我们心里造成创伤的机会还是少很多的。

       auto_ptr在《C++ PL》中只有很少的内容,《C++ Primer》中提及也不算太多,《Effective C++》中论及的反而算是比较多了,一直没有太深的了解,所以平时还是用普通的指针比较多,今天在《C++ STL》中才算看到比较详尽的内容,想到以后我的程序似乎应该有所改变了才是,不能老是用*搞指针了,用复杂的对象吧。

       首先,auto_ptr是为了防止内存泄漏而生的,的确,这本来是个好消息,特别是被内存泄漏吓怕了的我来说。auto_ptr是个类似指针的对象,它重载了*,->等操作符。可以和指针进行类似的取值操作。但是它有如下几点要注意:1。它不能用作数组或容器的对象。2。它不能进行一般意义的赋值和复制。3。它的指针算数没有意义。4 。你最好不要用它来传递参数,当不得不用的时候必须用const引用才行。5。同时不能有两个以上的auto_ptr指向同一个值。这以上五点都必须注意,不然《C++ STL 》作者的警告是:“如果你的误用行为没有导致全盘崩溃,你或许会暗自庆幸,而这其实是真正的不幸,因为你或许根本就没有意识到你已经犯了错误。”我看这话怎么看怎么就像恐吓。本来准备大面积用auto_ptr的我,一下子不敢用了。auoto_ptr的最大特点就是所有权概念。并且此所有权只能移交,不能复制。首先,你不能使用惯用的赋值来初始化,只能用函数形式的。

       std::auto_ptr<classA> ptr(new classA);

还好,我们也不是太不习惯。

void f()

{

       std::auto_ptr<classA> ptr1(new classA);

       std::auto_ptr<classA> ptr2(ptr1);

       std::auto_ptr<classA> ptr3;

       ptr3 = ptr2;

}

执行完第二个语句时,ptr1就为NULL了,因为它的所有权都移交给ptr2了。最后ptr2也为空了,因为所有权给ptr3了。这里要注意另外一点,

ptr3 = new classA;

语句是非法的,因为虽然auto_ptr可以用new来初始化,但只能用auto_ptr赋值。

当你对任何已经为NULLauto_ptr做取值运算*的时候,都会导致未定义的操作,可能导致程序的崩溃。没有崩溃?参考上面的警告。

权利的移交其实还算好记,但是请不要用auto_ptr传递参数,因为默认的参数传递方式就是复制,然后会导致你不知道的权利移交。这里有个技巧,当你把一个auto_ptr声明为const的时候,就可以制止一切权利的移交。但是却可以改变其值,类似const指针。

如下例子演示了权利的移交机制和利用const auto_ptr引用传递参数的方法。

 

#include "stdafx.h"

#include <iostream>

#include <memory>

using namespace std;

 

template <class T>

ostream& operator<< (ostream& os,const auto_ptr<T> &p)

{

       if(p.get() == NULL)

              os<<"NULL";

       else

              os<< *p;

       return os;

}

 

int main()

{

       auto_ptr<int> p(new int(34));

       auto_ptr<int> q;

       cout <<"At first:"<<endl;

       cout <<"p: "<<p<<endl;

       cout <<"q: "<<q<<endl;

       q = p;

       cout <<"Later:"<<endl;

       cout <<"p: "<<p<<endl;

       cout <<"q: "<<q<<endl;

       *q = 43;

       p = q;

       auto_ptr<int> h(p);

       cout <<"At last:"<<endl;

       cout <<"p: "<<p<<endl;

       cout <<"q: "<<q<<endl;

       cout <<"h: "<<h<<endl;

       return 0;

}

 

       此例子来自《C++ STL》中的类似例子,你会发现所有的情况下,实际只有一个auto_ptr拥有所有权。

       最后讲讲auto_ptr的作用,因为auto_ptr是一个类,不抛出异常,并且有析构函数释放资源,所以在使用auto_ptr替代普通指针时上述的几种内存泄漏情况都有所缓解。道理在于一旦出现问题,因为auto_ptr是个局部临时对象,那么自然会调用析构函数,哪怕突然抛出异常这点也不例外。所以,当使用auto_ptr后,你可以稍微感受到一点光new而不delete的快感,可惜的是,语法复杂了很多,而且还要注意很多很多问题。当然,已经难能可贵了。因为这些都没有牺牲C++语言的特性,仅仅是一个库。

       假如我有什么不对,请指教。

 

阅读全文....

看《C++ STL》发现的关于异常说明的问题

今天开翻《C++ STL》一书,就发现一个问题,那就是目前的编译器好像尚不支持C++的异常说明,源代码如下:

#include "stdafx.h"

#include <iostream>

#include <string>

using namespace std;

 

class c1

{

public:

    c1()

    {

       c1str = "error 1";

    }

    string c1str;

};

class c2

{

public:

    c2()

    {

       c2str = "error 2";

    }

    string c2str;

};

 

void fn() throw (c1)

{

    cout<<"have problem"<<endl;

    throw c2();

}

 

int main()

{

    try

    {

       fn();

    }

    catch (const c2& err)

    {

        cout << err.c2str<<endl;

    }       

    cout <<"Done"<<endl;

    return 0;

}

 

VS 2005中异常说明会得出警告: warning C4290: 忽略C++ 异常规范,但指示函数不是__declspec(nothrow)

警告MSDN中的原文解释如下:

警告消息

忽略 C++ 异常规范,但指示函数不是 __declspec(nothrow)

使用异常规范声明函数,Visual C++ 接受但并不实现此规范。包含在编译期间被忽略的异常规范的代码可能需要重新编译和链接,以便在支持异常规范的未来版本中重用。

有关更多信息,请参见 Exception Specifications

使用 warning 杂注可避免出现此警告:

 

意思大概就是异常说明VS 2005仅仅是接受,而并没有实现,也就是相当于没有这个功能,但是不报错。此源代码在Dev 4.9.9.0可以得出正确结果。提示程序在运行时被非正常终结,并且仅仅只输出have problem;VS 2005把所有的东西都输出了。据说VS 2005已经非常符合标准了,就我的学习过程的确是这样,今天看来,还尚有为尽之处,不过,但是也没有人说它完全符合标准,好像也就97%多吧。

 

将此事进一步研究,发现如下代码:

#include <iostream>

#include <string>

using namespace std;

 

class c1

{

public:

    c1()

    {

       c1str = "error 1";

    }

    string c1str;

};

class c2

{

public:

    c2()

    {

       c2str = "error 2";

    }

    string c2str;

};

 

void fn() throw (c1,bad_exception)

{

    cout<<"have problem"<<endl;

    throw c2();

}

 

int main()

{

    try

    {

       fn();

    }

    catch (const c2 &err)

    {

       cout << err.c2str <<endl;

    }

    catch (const bad_except  ion&)

    {

        cout << "catch bad_exception"<<endl;

    }

    catch (...)

    {

        cout << "catch another exception"<<endl;

    }                

    cout <<"Done"<<endl;

    return 0;

}

 

当然在VS中还是只能捕捉到异常c2,而在DEV中奇怪的是确还是中断了,按《C++ STL》书中的说法,此时应该捕捉到异常bad_exception才对,另外,有一点想说的是,《C++ Primer》一书第4版中我没有找到关于bad_exception的介绍,而其它类型的异常倒还是有。再另外,我在VS 2005exception头文件的源代码中的确发现了bad_exception异常,其注释为base of all bad exceptions。在DEV中源代码注释为f an %exception is thrown which is not listed in a function's %exception specification, one of these may be thrown.This declaration is not useless,如此,就不是异常的捕捉代码有问题,而是的确程序没有正常抛出了。则我,书,和DEV三者中必有一错,希望高人指出。

 

阅读全文....

又很久没有来了

又很久没有来了,一则玩兴大发,玩了一段时间,二则稍微看了些Windows下多鼠标输入技术的资料。当然,查阅这些资料其实和玩有关,上次另买了1USB鼠标,发现游戏中无法识别出两个鼠标可以同时操作,就连Windows下面也只能用一个指针,甚为不满,作为立志于成为技术型人才的我自然不能善罢干休,^^(仅自己如此认为而已),于是决定实现Windows下面的多鼠标操作,发现国内少有资料,国外资料尚有一些,经过一段时间的学习,虽然仍然学的肤浅,但已经基本可以应付一些小问题了。过段时间应当会有数文详细介绍这个。

 

阅读全文....

(N1744)给C++ 0x标准的大整数库提案 粗略翻译稿

N1744=05­0004

 

C++ 0x标准的大整数库提案

 

 

九天雁翎粗略翻译稿

 

原文链接:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1744.pdf

 

 

 

引言

这个提案目标是给 N1692提案提供一个标准的行话。本提案原意是独立成文的,但是一些实现可能仍然得益于提案N1692提供的背景。

假如本提案能加入TR1,它最适合加入第5数值工具。它是一个属于第二大类(“在完全新的头文件中声明的新的库组件(类型和函数)”)的扩展。然而,在那个环境里,long long类型不能被假设已经包含,所以必须用long来替代。已经提交的改变

A.增加<integer> 17.4.1/2 11

B.如下改变 26/2:

下面这些条款描述了包含在ISO C 库里面的复数类型数值数组无限长整数和相关函数工具。它们被总结在 表 79中:

表 79 数值库总结

Subclauses

条款

Headers

头文件

26.1 Requirements 需求

 

26.2 Complex numbers 复数

<complex >

26.3 Numeric arrays 数值数组

<valarra y>

26.4 Generalized numeric operations

通用数值操作

<numeric >

26.5 Unlimited range integer

无限长整数

 

<integer>

26.56 C library

C的库

<cmath>

<cstdlib >

 

 

C增加如下段落到 26.4 通用数值操作后面

26.5 无限长整数

1.    头文件<integer>定义了一个和很多函数用来表示和操作长度仅仅受限于可用内存的整数。

2.    要点所有返回一个临时integer整数的操作和很多成员操作符可能因为没有足够的内存而失败。这样的错误会作为一个overflow_error异常被报告。

(作为以可用内存来定义边界的整数类)。

 

 

 

 

 

 

以下主要是源代码,所以没有翻译,间杂的英文翻译起来工作量太大:

。。。。。。。。。。。。。。。。。。。

请参考原文。

 

 

1.         这个整数类表示一个整数。[要点这个不是一个基础类型因此一个带符号整数类在3.9.1最后的要点中是没有意义的]

 

 

D重编号 26.5 C 库到26.6:

26.6 C语言库                                                                                                                      

1.     80 81 描述了头文件 <cmath><cstdlib>

 

 

基本原理:

这个类将更适合在<complex> 26.2,但是这将使26.3<valarray>26.4<numberic>重编号。然而,26.5(C语言库)是一个太不同的部分,应该一直保持不变。因此,这个提案插到26.5<numberic>段落后面。

 

就像std::string 引入了一个可变长字符串到char[N]一样这个类引入了一个没有确定大小的integer类。就像 std::string,没有新的概念被创造出来。这个类也可以用string字符串常量来初始化,例如:std::integer foo  =  12345 67 89 0 12 3 4 5 6 7 8 9 0 ;

std::string,这样的初始化可以在编译时优化。这个优点在这里更大,作为一个调用了基础转换但是它仍然是一个 Qol 问题。(Qol我不知道究竟是什么)

这个unsiged_integer额外的复杂性在于为节省一个符号位考虑了太多。这个后置操作 operator++(int) 必须创建一个临时变量这个操作是一个开销O(n)的操作。因此它没有被包含,operator--(int)也是这样。

   许多函数有重载long long int的版本。这些函数有更好的复杂边界典型的以N为因子。加入对 long int,plain int 与/或 short int 的重载将只是提供了更多有效率却不那么重要的重载。加入 double 的重载将增加这个范围,但是这里没有一个令人确信的理由增加integer::integer(double) 或者 operator+=(double).然而,还是提供了operator*=(double) 和 operator /= (double)。与这个有很密切联系的是,它让 (double(0.5) + integer))到底应该是什么类型变得不清楚。

   这个对于 operator*= 的额外实现方法是留给编译器去实现的但是它需要比直接相乘更好(复杂度将是O(N2),这个复杂度界限制定是 <O(N2) ).提案N1692 对于乘法提供了很多选择。但是 却没有提供对于除法的引导。 GNU GMP 文档GMP5.0,H2 2005 建议除法复杂度 <O(N2) 是不合理的,这是为什么 operator/=(integer const&) 提议在这里有一个二次的复杂度边界。当然,一个高质量的实现可以用更好的算法。

   &=,|= ^=操作符的操作是让最短的操作数加入前导的0来匹配其他操作数的长度。这点确保了像(integer(1234567891234567890) | 1)这样的表达式不会截断左操作数。这里没有提供operator<< 和有符号的整数 operator<<(long long lhs,size_t rhs)的重载;这将会允许表达式1<<size_t(65),但是需要核心的改变。

      Sqr函数被加了进来因为这个操作时很普遍的但是显然 实现 V*V用通用的乘法算法。这个提案的语法允许这些但是也允许优化的算法。比如,用传统的O(N2)算法,123*123 100*100 + 100*20 + 20*100 + 100*3 + 3* 100 + 20*20 + 20*3 + 3*20 + 3*3 (9 个乘法, 8 个加法)

     像矩阵一样这些数字可能变得相当大意味着临时变量可能有相当明显的开销。因此,类似的技术可以对它们应用。特别的,普通的a*b+c形式可能以从operator*返回一个中间值的形式优化,而加重operator+的负担。这个提案不允许这样,但是因为没有内在的表示法被要求,一个运行时相同的技术可以被使用。

             作为与普通的小字符串相同的优化方案实现可以选择不去使用动态分配内存假如这个值足够的小例如不大于LONGLONG_MAX。这些可以被强制执行,通过integer::integer(long long)的方式。这个提案不是想要强制执行这个决定,虽然它默默地假设这个行为被operator long long()所描述。

     这个类不是特化一个std::allocator 模板参数。这不是一个准确的决定,然而LWG可以考虑增加它。

 

      

  原文      Copyright Michiel Salters / Nederlands Normalisatie Institute.

 

阅读全文....

(N1744)Big Integer Library Proposal for C++0x 粗略翻译稿 双语对照(有什么不妥,请参看原文)

N1744=05­0004

 

Big Integer Library Proposal for C++0x

C++ 0x标准的大整数库提案

 

九天雁翎粗略翻译稿

原文链接:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1744.pdf

 

 

 

 

 

 

 

Introduction

引言

This proposal aims to provide the standardese for N1692.

这个提案目标是给 N1692提案提供一个标准的行话。

It is meant to be self­contained, but implementers may still benefit from the background provided in N1692.

本提案原意是独立成文的但是一些实现可能仍然得益于提案N1692提供的背景。

If included in TR1, this would fit best in chapter 5, Numerical facilities.

假如本提案能加入TR1,它最适合加入第5数值工具。

It is an extension from the second category (New library components (types and functions) that are declared in entirely new headers”).

它是一个属于第二大类(“在完全新的头文件中声明的新的库组件类型和函数)”)的扩展。

However, in that context the type long long cannot be assumed and must be replaced by long .

然而在那个环境里long long类型不能被假设已经包含所以必须用long来替代。

 


Proposed changes:

已经提交的改变

A. Add <integer> to 17.4.1.2/2 Table 11

A.增加<integer> 17.4.1/2 11

 

 

B. Change 26/2 as follows:

B.如下改变 26/2:

The following subclauses describe components for complex number types, numeric ( n at a time) arrays, generalized numeric algorithms, unlimited range integers and facilities included from the ISO C library, as summarized in Table 79:

下面这些条款描述了包含在ISO C 库里面的复数类型数值数组无限长整数和相关函数工具。它们被总结在 79

Table 79Numerics library summary

表 79 数值库总结

Subclauses

条款

Headers

头文件

26.1 Requirements 需求

 

26.2 Complex numbers 复数

<complex >

26.3 Numeric arrays 数值数组

<valarra y>

26.4 Generalized numeric operations

通用数值操作

<numeric >

26.5 Unlimited range integer

无限长整数

 

<integer>

26.56 C library

C的库

<cmath>

<cstdlib >

 

 

C. Add the following paragraph after 26.4 Generalized numeric operations:

C增加如下段落到 26.4 通用数值操作后面

 

 

26.5 Unlimited range integer

26.5 无限长整数

1. The header <integer > defines a single class and numerous functions for representing and manipulating integral numbers whose range is limited by available memory.

头文件<integer>定义了一个和很多函数用来表示和操作长度仅仅受限于可用内存的整数。

2.    Notes:all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory.

要点 所有返回一个临时integer整数的操作和很多成员操作符可能因为没有足够的内存而失败。

Such errors are reported as overflow _e r r o r exceptions(as available memory defines the range of the integer class).

这样的错误会作为一个overflow_error异常被报告。作为以可用内存来定义边界的整数类

 

以下主要是源代码,所以没有翻译,间杂的英文翻译起来工作量太大:

。。。。。。。。。。。。。。。。。。。

请参考原文。

 

 

1.   The class integer represents an integer number.

这个整数类表示一个整数。

[Note:this is not a fundamental type, and therefore not a signed integer type in the sense of 3.9.1 end Note]

[要点 这个不是一个基础类型因此一个带符号整数类在3.9.1最后的要点中是没有意义的]

D. Renumber 26.5 C library to become 26.6:

D重编号 26.5 C 库到26.6:

26.6 C Library

26.6 C语言库                                                                                                                      

1.    Tables 80 and 81 describe headers <cmath> and <cstdlib >

80 81 描述了头文件 <cmath><cstdlib>

Rationale:

基本原理:

The class would fit better after <comple x> 26.2, but this would involve renumbering 26.3 <valarra y> and 26.4 <numeric > .

这个类将更适合在<complex> 26.2,但是这将使26.3<valarray>26.4<numberic>重编号。 However, 26.5 (C library) is different enough that it should be last.

然而26.5C语言库是一个太不同的部分应该一直保持不变。

Therefore, this proposal inserts the paragraph after 26.4 <numeri c> .

因此这个提案插到26.5<numberic>段落后面。

 

Just like std::str i n g introduces a variable­length string to complement char[N], this class introduces an integer class without a fixed size.

就像std::string 引入了一个可变长字符串到char[N]一样这个类引入了一个没有确定大小的integer类。

Like std::str in g , no new literals are created.

就像 std::string,没有新的概念被创造出来。

This class too can use string literals in initializations, e.g.

这个类也可以用string字符串常量来初始化例如

std::integer foo  =  12345 67 89 0 12 3 4 5 6 7 8 9 0 ;

 

Like std::str in g , such initializations can be optimized at compile time.

std::string,这样的初始化可以在编译时优化。

The benefits are larger here,

这个优点在这里更大

as this involves a base conversion (decimal/binary), but it still is a QoI issue.

作为一个调用了基础转换但是它仍然是一个 Qol 问题。(恕我不知道Qol是什么意思)

 

The extra complexity of an unsige d_ i nt e g e r class is considered too much for the savings of a single sign bit.

这个unsiged_integer额外的复杂性在于为节省一个符号位考虑了太多。

 

 

The postfix operato r+ + (i n t ) must create a temporary, which is a rather expensive O(n) operation.

这个后置操作 operator++(int) 必须创建一个临时变量这个操作是一个开销O(n)的操作。 Therefore it is not included, nor is operator - - (int) .

因此它没有被包含operator--int也是这样。

 

Many functions have overloads taking long long int .

许多函数有重载long long int的版本。

These have better complexity bounds, typically by a factor of N. Adding long int , plain int and/or short int overloads would provide only marginally more efficient overloads.

这些函数有更好的复杂边界典型的以N为因子。加入对 long int,plain int 与/或 short int 的重载将只是提供了更多有效率却不那么重要的重载。

Adding double overloads would increase the ranges, but there are no convincing cases known for integer ::i nt e g e r ( d o u b l e )or operator+=(double).

加入 double 的重载将增加这个范围但是这里没有一个令人确信的理由增加integer::integer(double) 或者 operator+=(double). However,operator*=(double)and operator/=(do u b l e )are provided.

然而还是提供了operator*=(double) operator /= (double)

Closely related to this, it is unclear what the type of double 0.5)+integer  )) should be.

与这个有很密切联系的是它让 (double(0.5) + integer))到底应该是什么类型变得不清楚。

The exact implementation of operator * = is left to the implementation, but it is required to be better than straightforward multiplication (which would be O(N2), and the complexity bound specified is < O(N2) ).

这个对于 operator*= 的额外实现方法是留给编译器去实现的但是它需要比直接相乘更好(复杂度将是O(N2),这个复杂度界限制定是 <O(N2) ).

N1692 offers a number of alternatives.N1692 offers no guidance on division.

提案N1692 对于乘法提供了很多选择。但是 却没有提供对于除法的引导。  

The Gnu GMP documentation suggests that <O(N2) is unreasonably expensive (scheduled for GMP5.0,H2 2005),which is why the operator/=(integer const&) proposed here has a quadratic complexity bound.

GNU GMP 文档GMP5.0,H2 2005 建议除法复杂度 <O(N2) 是不合理的,这是为什么 operator/=(integer const&) 提议在这里有一个二次的复杂度边界。

Of course, a high­quality implementation may use the better algorithms.

当然一个高质量的实现可以用更好的算法。

The &= , |= and ^= operators operate as if the shortest of their operands has leading zeroes added to match the length of the other operand.

&=,|= ^=操作符的操作是让最短的操作数加入前导的0来匹配其他操作数的长度。 This ensures that expressions like(integer(1234567891234567890”)|1)don’t truncate their left hand side.There is no overload of operator<< with signature integer operator<< (long long lhs,size_t rhs);This would allow the expression 1<<size_t(65) but would require core changes.

这点确保了像integer(1234567891234567890) | 1这样的表达式不会截断左操作数。这里没有提供operator<< 和有符号的整数 operator<<(long long lhs,size_t rhs)的重载;这将会允许表达式1<<size_t(65),但是需要核心的改变。

     The sqr function is added because the operation is common, but the obvious implementation v*v uses the generic multiplication algorithm.

 Sqr函数被加了进来因为这个操作时很普遍的但是显然 实现 V*V用通用的乘法算法。 The proposed wording allows this, but also allows optimized algorithms. E.g. using the conventional O(N2)  algorithm, 123*123 is 100*100 + 100*20 + 20*100 + 100*3 + 3* 100 + 20*20 + 20*3 + 3*20 + 3*3 (9 multiplies, 8 additions) whereas sqr(123) can also be calculated as 100*100 + 2*100*20+ 2*100*3 + 20*20 + 2*20*3 + 3*3 (6 multiplies, 3 bitshifts, 5 additions).(Of course, this implementation is not allowed for either operator* or sqr because they both should have better complexities.)

这个提案的语法允许这些但是也允许优化的算法。比如,用传统的O(N2)算法,123*123 100*100 + 100*20 + 20*100 + 100*3 + 3* 100 + 20*20 + 20*3 + 3*20 + 3*3 (9 个乘法, 8 个加法)(当然,这个实现不允许operator*或者sqr使用,因为他们都应该有更好的复杂性)

     Like matrices, these numbers can become quite large, which means that temporaries may have significant overhead.

像矩阵一样这些数字可能变得相当大意味着临时变量可能有相当明显的开销。 Therefore, similar techniques could be applied to them.

因此类似的技术可以对它们应用。

In particular, the common form a*b+c could be optimized by returning an intermediate type from operator* and adding overloads for that type to operator+.This proposal does not allow this,but since no internal representation is mandated a run­time equivalent technique can be used.

特别的普通的a*b+c形式可能以从operator*返回一个中间值的形式优化而加重operator+的负担。这个提案不允许这样,但是因为没有内在的表示法被要求,一个运行时相同的技术可以被使用。

 

             Equivalent to the common small string optimalization,implementers could choose not to use dynamically allocated memory if the value held is small enough(e.g. no larger then LONGLONG_MAX).

作为与普通的小字符串相同的优化方案实现可以选择不去使用动态分配内存假如这个值足够的小例如不大于LONGLONG_MAX

 This can be enforced by requiring integer::integer(long long) to succeed.

这些可以被强制执行通过integer::integer(long long)的方式。

 This proposal does not want to enforce that decision, although it silently assumes that behavior in the description of operator long long().

这个提案不是想要强制执行这个决定虽然它默默地假设这个行为被operator long long()所描述。

     This class does not specify an std::allocator template argument.

这个类不是特化一个std::allocator 模板参数。

This is not an explicit decision, and the LWG might consider adding it.

这不是一个准确的决定然而LWG可以考虑增加它。

               

原文 Copyright Michiel Salters / Nederlands Normalisatie Institute.

 

阅读全文....

对提案N1692(A Proposal to add the Infinite Precision Integer to the C++ Standard Library)的看法

因为第一次尝试翻译这种技术文章,感觉还是比较难的,用了几个小时,虽然原文才7页纸。体会了翻译的痛苦,才能原谅那么多翻译出来的书籍的枯燥。毕竟,这不是件容易事,虽然他们是拿钱做事的。从N1692 里面,我感受到了一个给C++ standard的提案该有的严谨,哪怕是格式上都是这样,不过很奇怪为什么作者做个提案竟然只提供了借口,而不提供源代码,奇怪的很。而且接口里面,很多操作符不是本来可以在类内部定义,作者放到了外面,而且外面的函数没有设为友元,不知道是因为作者仅仅为了说明方法而已,故意忽略了,还是什么其他原因。要不就是我才疏学浅搞错了什么东西。而且从其中,我倒是了解到一个新的词,粒度,以前从来没有听说过,在网上查了一下,也没有太明白。仅仅知道一个大概。作者提出的问题,在网上也没有找到。这点很郁闷。

阅读全文....

很久没有来了,我可不是在玩哦

最近一直没有空写博客,问题很严重啊,在电脑城打了一下工,硬着头皮看着TC++PL,看着孙鑫的VC++ 教学视频(感谢孙鑫老师免费提供下载),同时还看着原版的Effective C++ ,还有,还看着Grady Booch的面向对象分析与设计(第2版),并且看了一下殷人昆出版的新版数据结构,不过相对而言,反而没有时间来实际的写太多代码来实践了,最近翻看了很多关于我的问题(4)的BigInt的东西,开发一个类真的不容易啊,特别是当你想真的设计的很好的话。。。。。。。。呵呵,说多了,最近其实很想做点实事,因为孙鑫的VC++ 教学视频快学习完了,想尝试翻译一下TR1,不知道是不是太不自量力了,不过我却真的很想。。。。。先翻译一下N1744=050004
Big Integer Library Proposal for C++0x吧,这是我找BigInt资料的时候发现的,翻译的不好不要怪我,我只是自己翻译着好玩,又不是要赚你们的钱啊。

阅读全文....

增加无限长精确整数(infinite precision integer)给C++标准库的提案 简单翻译稿 N1692

A Proposal to add the Infinite Precision Integer to the

C++ Standard Library N1692 1 July 2004

原作者:M.J. Kronenburg

e-mail: M.Kronenburg@inter.nl.net

 原文链接:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1692.pdf

九天雁翎简单翻译稿:

增加无限长精确整数infinite precision integerC++标准库的提案

1 动机:

对整数的需要不再适应于处理器数据长度的增加。比如,int类型的范围在一个32位电脑上是±2^31 ±10^9.对于超出这个范围的情况,程序员往往创建一个用unsigned int 和符号位组成的C++类,这个类的数据长度仅仅受可用内存的限制。并且重载了数学操作符。这个类的整数范围是±2^8mm是以字节(byte)度量的最大可用内存。以现在的内存大小来说,这个范围实际上是无限的。这个类就是一个无限长精确整数,我提议这个类的名字为integer

目前有很多无限长精确整数的实现存在,以下给出一些总的来说比较好的支持,实现和设计方案:

 

1. Gnu C++ library 中的 Integer

(C++, 限制在10^5 位以内 [7]).

 

2. The Gnu Multiple Precision Arithmetic Library

(C with assembler, 无限[6]).

 

3. 我自己设计的Integer class

(C++ with assembler, 无限)

 

在以后,我提到实现123就是分别指以上几种。

 

2           对标准的影响

作为一个有自己内存管理的独立类,没有对标准产生影响。

 

3           设计结果

有很多设计结果,但是选择通常就是在我在上面列出来的几种中进行。

 

3.1       类结构

这个被提议的C++类将是integer类。实现这个类,使用int的函数和操作符是需要被重载的,并且重载求最大公约数和最小公倍数的函数也是必须的,而且一些类似setbit,clearbit,getbit,highestbit,lowestbit等的位级(bit level)操作也是需要重载的。在实现1里面的Integer类是用包含一个struct的方式表示的。这意味着,每个类函数或者操作符调用的函数都是作用在这个struct上面。实现2是一个在C上的实现。所以要在C++上面使用,需要一个C++的封装。在实现3里,这个Integer类是一个内部没有用struct表示的简单的C++类。这里有一个从string创建对象的构造函数,因此任何数字可以由一个任意长度的string指定。

 

3.2       数据结构

在所有以上我提到的实现中,数据都是一个连在一起的可变长二进制块。一个可以保存-1(小于0),0(零),1(大于0)值的符号被存储在一个分开的地方。一个可行的方法是把数据放在一个标准库容器vector中,但是像许多integer操作在位级上实现一样,对vector容器实现的依赖是不可接受的。因此,integer不会使用任何标准库容器或者函数。

 

3.3  数据粒度(Data Granularity

为了操作integer数据,它的粒度必须被定义,即一次操作多宽的数据块。在32位处理器上,实现1short 16位粒度,因为这意味着所有的移位(shift)和传送(carry)操作可以用32位的int实现,那么就不需要使用汇编。在32位处理器上,其他的实现用32位的粒度,这意味着汇编是不可避免的了。目前我还不清楚,是否64位处理器可以控制64位粒度的integer

 

3.3       性能

所有的算术计算操作性能在使用32位粒度和汇编时都好很多。对于两个大数的乘法,很多算法存在(N 是数据的十进制或二进制位数(number of decimals or bits:

Algorithm            implementation     order                           decimals               reference

Basecase                     1,2,3              N^2                                      1 10^2

Karatsuba                    2,3                N^1.585                              10^2 10^3               [1,4]

3-way Toom-Cook                         N^1.465                               > 10^3                        [1,4]

16-way Toom-Cook                       N^1.239                               > 10^3                        [1]

Sch¨onhage NTT                           N logN log logN          > 10^3                        [2,3,4]

Strassen FFT            -                      N log^2 N                    > 10^3                        [1,3,5]

NTT是数理论上的一种转换,FFT是快速傅利叶变换)。Starassen  FFT算法因为是使用浮点计算法(arithmetic),所以对于非常大的参数它的准确性无法保证[4],因此没有被我提到实现使用,但是他的是最好的。实现1只使用了basecase乘法,因此对于大参数来说它的性能很差。在实现3里面,我发现16-way Toom-Cook算法比Sch¨onhage NTT更快(直到一些我不知道的非常大的参数)

对于除法和残余递归算法(remainder recursive algorithms)对于大参数有着更好的性能,而且在输入输出流(instream and outstream)来说也是一样的。意味着从二进制转换到十进制也是一样有着好的性能,而且反之亦然。

 

3.4       汇编的使用

在实现1里没有使用汇编,因此可以运行在任何平台上。实现2用了汇编,而且它是一个为了在类Unix平台运行的C语言编译器,它使用的汇编也是。实现3用了汇编,而且它是为了在Borland C++ Bulider 它的Turbo汇编编译器使用的。

 

3.5       总结

当的确需要从上述3个存在的实现中选一个的话,以下的情况可能要被考虑。因为实现1仅仅受限于大概10^5位(我不清楚为什么有这样的限制存在),这个实现作为无限制精确整数可能不是那么有用。而且对于很大的整数它的性能不好。实现2可能更多的在类Unix平台被选择,所有它需要的看起来是一个C++的封装。实现3可能更多地在Wintel平台被选择。另一个选项是与商业的代数运算程序开发商合作。

 

4           提案正文

4.1       需求

integer类的需求由包含在提案头文件的界面(interface)提供。这些断言(assertion)和之前之后的情况(pre/post-condition)都是很明显的,对于平均复杂度的需要也提供了,N 是数据的十进制或二进制位数:

 

class integer

{

private:

unsigned int *data, *maxdata;

signed char thesign;

public: // Complexity:

integer(); // 1

integer( int ); // 1

integer( double ); // 1

integer( const char * ); // < N^2 (see 3.4)

integer( const string & ); // < N^2 (see 3.4)

integer( const integer & ); // N

virtual ~integer(); // 1

const unsigned int size() const; // 1

integer &operator=( const integer & ); // N

integer &negate(); // 1

integer &abs(); // 1

integer &operator++(); // 1

integer &operator--(); // 1

const integer operator++( int ); // N

const integer operator--( int ); // N

integer &operator|=( const integer & ); // N

integer &operator&=( const integer & ); // N

integer &operator^=( const integer & ); // N

integer &operator<<=( unsigned int ); // N

integer &operator>>=( unsigned int ); // N

integer &operator+=( const integer & ); // N

integer &operator-=( const integer & ); // N

integer &operator*=( const integer & ); // < N^2 (see 3.4)

integer &operator/=( const integer & ); // < N^2 (see 3.4)

integer &operator%=( const integer & ); // < N^2 (see 3.4)

const integer operator-() const; // N

const integer operator<<( unsigned int ) const; // N

const integer operator>>( unsigned int ) const; // N

};

const bool operator==( const integer &, const integer & ); // N

const bool operator!=( const integer &, const integer & ); // N

const bool operator>( const integer &, const integer & ); // N

const bool operator>=( const integer &, const integer & ); // N

const bool operator<( const integer &, const integer & ); // N

const bool operator<=( const integer &, const integer & ); // N

const integer operator|( const integer &, const integer & ); // N

const integer operator&( const integer &, const integer & ); // N

const integer operator^( const integer &, const integer & ); // N

const integer operator+( const integer &, const integer & ); // N

const integer operator-( const integer &, const integer & ); // N

const integer operator*( const integer &, const integer & ); // < N^2 see 3.4)

const integer operator/( const integer &, const integer & ); // < N^2 see 3.4)

const integer operator%( const integer &, const integer & ); // < N^2 see 3.4)

const integer gcd( const integer &, const integer & ); // ?

const integer lcm( const integer &, const integer & ); // ?

ostream & operator<<( ostream &, const integer & ); // < N^2 (see 3.4)

istream & operator>>( istream &, integer & ); // < N^2 (see 3.4)

const int sign( const integer & ); // 1

const bool even( const integer & ); // 1

const bool odd( const integer & ); // 1

const bool getbit( const integer &, unsigned int ); // 1

void setbit( integer &, unsigned int ); // 1

void clearbit( integer &, unsigned int ); // 1

const unsigned int lowestbit( const integer & ); // 1

const unsigned int highestbit( const integer & ); // 1

const integer abs( const integer & ); // N

const integer sqr( const integer & ); // < N^2 (see 3.4)

const integer pow( const integer &, const integer & ); // ?

const integer factorial( const integer & ); // ?

// floor of the square root, like int sqrt( int )

const integer sqrt( const integer & ); // ?

// random integer >= first and < second argument

const integer random( const integer &, const integer & ); // ?

const int toint( const integer & ); // 1

const double todouble( const integer & ); // 1

 

为了错误控制,可能需要创建一个独立的exception:

class integer_exception : public exception

{ public:

enum type_of_error {

error_unknown, error_overflow,

error_divbyzero, error_memalloc, ...

};

integer_exception( type_of_error = error_unknown, ... );

virtual const char * what () const;

private:

type_of_error error_type;

string error_description;

};

5           没有解决的问题

5.1     需要的gcd,lcm,sqrt,pow,factorial复杂度还不清楚。

5.2     全部的无限长精确整数性能应该与著名的商业数学软件进行比较。

5.3     无限长精确整数上,真实的精度应该可以被定义。

 

6           引用

1. D.E. Knuth, The Art of Computer Programming, Volume 2 (1998).

2. P. Zimmermann, An implementation of Sch¨onhage’s multiplication algorithm (1992).

3. A. Sch¨onhage and V. Strassen, Computing 7 (1971) 281.

4. Free Software Foundation, Gnu MP manual ed. 4.1.2 (2002).

5. http://numbers.computation.free.fr/Constants/Algorithms/fft.html

6. http://www.swox.com/gmp

7. http://www.math.utah.edu/docs/info/libg++ 20.html

 

 

阅读全文....

和实现有关的相同字符串存储方式检验的思考及c-string字符串

/*Copyright (c) 2007,九天雁翎

* All rights reserved.

* 和实现有关的相同字符串存储方式检验的思考

* 完成日期:2007年7月7日*/

#include "stdafx.h"

#include <iostream>

using namespace std;

int main()

{

    char *p1 = "Hello the world!";

    char *p2 = "Hello the world!";

    if(p1 == p2)

    {

//ok,We could know it is the same as Bjarne Stroustrup said in VC++2005

       cout << "The same."<<endl;         

    }

    else

    {

       cout << "Not the same."<<endl;

    }

//But look at this

    cout << &p1 <<'/t' <<&p2 <<endl;

//the adress output is not the same!

//Do you want to output it use p1 and p2?

//Let try;

    cout << p1 <<'/t' << p2 <<endl;

//We can only get the string.

//Let reaffirm it

    if(&p1 == &p2)

    {

       cout<<"The same." <<endl;

    }

    else

    {

       cout<<"Not the same." <<endl;

    }

    return 0;

}

 


&p其实得到的是指针的地址,而不是c-string “Hello word!”的地址,而cout又为char* 重载了一个不同与一般指针的输出方式,所以你要输出”Hello world!”,可以通过static_cast<void*>方式,强制转换到void*指针,这样cout就可以输出想要的结果,结果自然和Bjarne Stroustrup说的一样,微软也没有错。

如下:

 

/*Copyright (c) 2007,九天雁翎

* All rights reserved.

* 和实现有关的相同字符串存储方式检验的思考

* 完成日期:2007年7月7日*/

#include "stdafx.h"

#include "myself.h"

#include <iostream>

using namespace std;

int main()

{

    char *p1 = "Hello the world!";

    char *p2 = "Hello the world!";

    if(p1 == p2)

    {

       cout << "The same."<<endl;         

    }

    else

    {

       cout << "Not the same."<<endl;

    }

//Yes,it is.

    cout << static_cast<void*>(p1) <<'/t' <<static_cast<void*>(p2) <<endl;

    return 0;

}

 

阅读全文....