Category: C/C++


VS2010

VS2010 RTM 了
对 C++ 的支持应该是最近几个版本中改进最大的。

看了下对标准库多了个 <codecvt> 的头文件,终于从 iostream 实现了对 UTF8 UTF16LE UTF16BE 的转码支持,大概前一段我试验的那几个 codecvt_facet 也到时候了吧。不过具体效果如何(性能问题比较难说)还是等拿到再具体判断为好。
右值引用也加入标准库,然后多了个 forward_list 的单链表,几个新的 algorithm 函数,智能指针等

就我感觉类似 <codecvt> 应是 C++ 标准库很需要添加的内容,虽然公司的效率还是比较快,可是等着 C++ 标准委员会整好新标准还不知得等到猴年马月去。每次想到标准库里面的查找函数命名乱得一塌糊涂,就感觉那些个人工作效率真是低的要死。

Advertisements

又一次吃了浮点数的亏 = =

C++:
while(step > 0.02){
    for(;;){
        if(x+step <= 100.0 &&
            (ttlen = ttl(x+step, y)) < minlength){
            minlength = ttlen;
            x += step;
        } else if(xstep >=0.0 &&
            (ttlen = ttl(xstep, y)) < minlength){
            minlength = ttlen;
            x -= step;
        } else if(y+step <= 100.0 &&
            (ttlen = ttl(x, y+step)) < minlength){
            minlength = ttlen;
            y += step;
        } else if(ystep >= 0.0 &&
            (ttlen = ttl(x, ystep)) < minlength){
            minlength = ttlen;
            y -= step;
        } else break;
    }
    step /= 2.0;
}
 
在 x-y 平面上寻找一个对 ttl 函数的极值点。先用 step 为步长寻找,然后步长减半再找,直到满足一定精度为止。
逻辑上过程上都很简单才对,可惜以上代码在 VC2008 运行正确,用 Gcc 却陷入死循环。
 
调试下发现居然出现了这种情况:在 A 点时发现 B 比 A 小,然后在 B点 发现 C 比 B 小,而在 C点 又发现 A 更小……于是就在这几个点上跳不出来了。
其实以前也看过不少强调处理浮点数比较时要特别注意的地方,但每个地方都特别写一下又很麻烦,而且觉得 double 的精度够高应该不用担心,没想到还是出了问题。VC 里大概对浮点数的比较运算做了特殊处理才没出错,感觉在这种很细节的地方 VC 非常强调安全性,但可能有时候也会觉得多此一举或是担心性能上的影响吧。
总之发现问题所在就好解决了,(ttlen = ttl(x, y+step)) < minlength 改为 (ttlen = ttl(x, y+step)) < minlength – 1e-4 即可。
今后再处理浮点数的问题时一定要相当小心咯

File I/O 效率 C vs C++ (一)

继续关注文件读写…这次测试写的效率
其实关于这个问题的讨论似乎总会以类似语言信仰问题而告终,再加 C++ IO 库的复杂性,很多半调子 C++ 程序员总会出现各种误用,反过来却作为攻击 C++ IO 效率低的凭证。
比如经常有人边在输出时大量使用类似
    fout<<…<<endl;
的语句边嚷嚷着写文件速度超慢的,只能说这些人根本不知道自己写的句子都做了什么…
 
所以说在评价任何东西之前先要做到最起码的了解
咱也算是大致研究过 C++ IO stream 各方面的内容,虽然不能说完全掌握仍在学习中,但自认为还是可以写点东西的。
 
总之还是用数据说话。
平台 XPsp3 + VC2008 Express Edition SP1 + STLport / MinGW(GCC4.4.0)
 
实验内容:
共做了三种类型写入的比较,每种类型采用几种不同方法实现:
1. 纯字节流写入
     (1) C fputs()
     (2) C fprintf()
     (3) C++ ofstream<<
     (4) C++ ofstream.rdbuf()->sputn()
2. 宽字符流通过转码写入
     (1) C++ locale + wofstream<<
     (2) C++ codecvt<> facet + ofstream.rdbuf()->sputn()
     (3) WinAPI WideCharToMultiByte() + ofstream<<
3. 格式化写入 (一个 int 一个 double + 一个字符串)
     (1) C fprintf()
     (2) C++ ofstream<<
     (3) C++ ostream.rdbuf()->sputn() sputc() + num_put<> facet
 
前两类比较时写入的内容是完全一致的,也可以横向做下参照。
 
结果:(由于和硬盘寻道时间等也有关系,尽量多次测试取受影响最小的值)
以 C Runtime library 的 fputs 函数所用时间为 1.0 做基准
VC2008EE + VC STL:
text out C fputs()                      1.0
text out C fprintf()                    2.0
text out C++ ofstream <<                1.2
text out C++ ofstream rdbuf()->sputn()  0.8
wText out C++ wofstream deflocale      25.0
wText out C++ locale codecvt            7.5
wText out C++ ofstream + WinAPI         1.5
Format data out C fprintf()             2.0
Format data out C++ ofstream  <<        4.0
Format data out C++ ofs num_put facet   3.0
 
首先用 VC 自带的标准库,可以看到直接用 C++ fstream 的 << 效率与 C 库函数相比还是略低一些,但差距并没有到不可忍受的地步,考虑到 C++ IO stream 的各种特性,这些还是可以接受的。
而直接调用下层 rdbuf()->sputn() 函数却比 fputs() 效率更高,让我对 C++ IO 库的进一步优化仍有希望。
在 Unicode 大行其道的今天,宽字符的读写已成为必需,但使用 locale 配合 wstream 来做的话效率确实无法接受,从上面看居然比调用 WinAPI 的方法慢几十倍。我还是严重怀疑 VC STL 的实现有问题,只是换做直接调用 codecvt<> facet 就能提高好几倍效率。
格式化读写一向是 C++ IO stream 被重点诟病的地方,与 fprintf() 函数整相差一倍,即使直接调用 num_put (去掉了构造 ios_base::sentry 对象产生的流同步、空白跳过等操作),仍然有 50% 的差距。
其实从理论上来说,C++ 的格式化读写应当是比 C 的 fprintf() 函数要快的,因为 fprintf() 总要有一个解析格式字符串的过程,这个只能放在运行时,而 C++ 的格式是通过多个连续函数调用控制的,可以在编译时即进行优化。但实践往往存在各种变数 = =
 
VC2008EE + STLport5.2.1:
text out C fputs()                      1.0
text out C fprintf()                    2.0
text out C++ ofstream <<                0.7
text out C++ ofstream rdbuf()->sputn()  0.6
wText out C++ wofstream deflocale       7.5
wText out C++ locale codecvt            7.0
wText out C++ ofstream + WinAPI         1.0
Format data out C fprintf()             2.0
Format data out C++ ofstream  <<        2.0
Format data out C++ ofs num_put facet   1.7
 
STLport 的 C 库函数完全是照搬 VC 的标准运行库,而只是重新实现了整个 C++ 库,所以 C 函数的效率与上一例是相同的,可直接横向比较。
面对这样的结果,我只能说 STLport 太赞了!!再考虑到其他的种种特性,赶紧扔掉 VC STL 全部换用 STLport 吧
不过转码看来确实是一个平台相关的特性,仍然无法比过 WinAPI 的效率
MinGW GCC4.4.0 + libstdc++:
text out C fputs()                      1.5
text out C fprintf()                    2.7
text out C++ ofstream <<                6.0
text out C++ ofstream rdbuf()->sputn()  2.7
mingw libstdc++ doesnot support other locale…
mingw libstdc++ doesnot support other locale…
wText out C++ ofstream + WinAPI         2.1
Format data out C fprintf()             3.0
Format data out C++ ofstream  <<        6.6
Format data out C++ ofs num_put facet   5.8
 
MinGW 貌似比较慢,是因为 MinGW 默认输出按 UTF-8 编码,对中文来说,字节数是 ANSI 的 1.5 倍。只有调用 API 的那个例子保持了 ANSI 编码。
除以 1.5 的话可以看到 C 库函数的效率与 VC 差不多,但 C++ 的效率比 VC 略低,与 STLport 比就差更远了。毕竟 GCC + libstdc++ 在 Win 平台不是原生支持,只作为跨平台的特性这样也足够了。
没有用 MinGW + STLport 做实验,不知能不能达到 VC 的效率。
 
————————————————————-
以前使用 C++ 的 IO stream 做输入输出时总担心效率问题,现在有了 STLport 做支持就可以放心大胆的用了。
但可以看到 C++ 的流式 IO 非常依赖于库实现,在各平台上的表现大概不如 C 库函数来得稳定。
而且使用除 "C" 之外的 locale 时效率确实还是有问题,转码的话还是直接调用平台 API 省时省力又高效。MinGW 考虑不引入 locale 部分也是有道理的啊…
 
这次全是 O,下次再比较 I 的情况…
 
最后按惯例是程序代码:
C++语言:
001 // test the performance of C I/O & C++ streams & C++ codecvt facet
002 #include<cstdio>
003 #include<iostream>
004 #include<fstream>
005 #include<locale>
006 #include<cstdlib>
007 #include<ctime>
008 #include<windows.h>
009 using namespace std;
010
011 const int testsize = 50000;
012
013 int main(){
014     char cstr[] = "这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
015     wchar_t wstr[] = L"这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
016     char buffer[200];
017     int cstrlen = strlen(cstr);
018     locale defloc("");
019
020     clock_t start;
021     FILE *cfile;
022     ofstream fout;
023     wofstream wfout;
024
025     // pure text ………………………
026     start = clock();
027     cfile = fopen("text_out_C_fputs.txt", "w");
028     for(int i = 0; i < testsize; ++i){
029         fputs(cstr, cfile);
030         fputc(‘\n’, cfile);
031     }
032     fclose(cfile);
033     printf("Text out C fputs: %d\n", clock()start);
034
035     start = clock();
036     cfile = fopen("test_out_C_fprintf.txt", "w");
037     for(int i = 0; i < testsize; ++i){
038         fprintf(cfile, "%s\n", cstr);
039     }
040     fclose(cfile);
041     printf("Text out C fprintf: %d\n", clock()start);
042
043     fout.clear();
044     start = clock();
045     fout.open("text_out_Cpp_ofstream.txt");
046     for(int i = 0; i < testsize; ++i){
047         fout << cstr << ‘\n’;
048     }
049     fout.close();
050     printf("Text out Cpp ofstream: %d\n", clock()start);
051
052     fout.clear();
053     start = clock();
054     fout.open("text_out_Cpp_rdbuf.txt");
055     for(int i = 0; i < testsize; ++i){
056         fout.rdbuf()->sputn(cstr, cstrlen);
057         fout.rdbuf()->sputc(‘\n’);
058     }
059     fout.close();
060     printf("Text out Cpp rdbuf: %d\n", clock()start);
061
062     // wchar_t text ………………………….
063     wfout.clear();
064     start = clock();
065     wfout.open("wtext_out_Cpp_wofs_defloc.txt");
066     wfout.imbue(defloc);
067     for(int i = 0; i < testsize; ++i){
068         wfout << wstr << L’\n’;
069     }
070     wfout.close();
071     printf("wText out Cpp wofs with default locale: %d\n",
072         clock()start);
073
074     fout.clear();
075     start = clock();
076     char *next;
077     const wchar_t *wnext;
078     mbstate_t st;
079     fout.open("wtext_out_Cpp_codecvt_facet.txt");
080     for(int i = 0; i < testsize; ++i){
081         use_facet<codecvt<wchar_t, char, mbstate_t> >(defloc).out(
082             st, wstr, wstr+sizeof(wstr)/21, wnext,
083             buffer, buffer+sizeof(buffer)1, next);
084         fout.rdbuf()->sputn(buffer, nextbuffer);
085         fout.rdbuf()->sputc(‘\n’);
086     }
087     fout.close();
088     printf("wText out Cpp ofs with codecvt facet: %d\n",
089         clock()start);
090
091     fout.clear();
092     start = clock();
093     fout.open("wtext_out_Cpp_ofs_WinAPI.txt");
094     for(int i = 0; i < testsize; ++i){
095         WideCharToMultiByte(CP_ACP, 0, wstr, 1, buffer, 200,
096             NULL, NULL);
097         fout << buffer << ‘\n’;
098     }
099     fout.close();
100     printf("wText out Cpp ofs with WideCharToMultiByte API: %d\n",
101         clock()start);
102
103     // Format out …………………………………….
104     srand((unsigned)time(NULL));
105
106     char datastr[] = "TestDataString实验格式化字符串";
107     start = clock();
108     cfile = fopen("format_data_out_C_fprintf.txt", "w");
109     for(int i = 0; i < testsize; ++i){
110         fprintf(cfile, "%d %lf %s\n", rand(),
111             double(rand())/RAND_MAX, datastr);
112     }
113     fclose(cfile);
114     printf("Format data out C fprintf: %d\n", clock()start);
115
116     fout.clear();
117     start = clock();
118     fout.open("format_data_out_Cpp_ofstream.txt");
119     for(int i = 0; i < testsize; ++i){
120         fout << rand() << ‘ ‘ << double(rand())/RAND_MAX << ‘ ‘
121             << datastr << ‘\n’;
122     }
123     fout.close();
124     printf("Format data out Cpp ofstream: %d\n", clock()start);
125
126     fout.clear();
127     start = clock();
128     fout.open("format_data_out_Cpp_ofs_facet.txt");
129     for(int i = 0; i < testsize; ++i){
130         use_facet<num_put<char> >(locale::classic()).put(
131             ostreambuf_iterator<char>(fout), fout, ‘ ‘, (long)rand());
132         fout.rdbuf()->sputc(‘ ‘);
133         use_facet<num_put<char> >(locale::classic()).put(
134             ostreambuf_iterator<char>(fout), fout, ‘ ‘,
135             double(rand())/RAND_MAX);
136         fout.rdbuf()->sputc(‘ ‘);
137         fout.rdbuf()->sputn(datastr, sizeof(datastr) 1);
138         fout.rdbuf()->sputc(‘\n’);
139     }
140     fout.close();
141     printf("Format data out Cpp ofs with facet: %d\n", clock()start);
142
143     system("pause");
144 }

fstream 文件 IO 点滴

http://dantvt.is-programmer.com/posts/11949.html

很多时候较大数据量的文件 IO 总是成为瓶颈,为了提高效率,有时想要先将文件大块大块的读入再行处理。下面分析两种惯常的处理手法。

1. 将文件一次性读入 string 中。

貌似 std::getline 、 istream::getline 或是 operator<< operator>> 等都不提供一次读到文件结尾的机制,只有 istreambuf_iterator 可以做到:

ifstream in("input.txt");
string instr((istreambuf_iterator<char>(in)), istreambuf_iterator<char>());

string 的构造函数前一个参数要多加一层 () 以免编译器误认为是函数声明 = = …

这样读入 string 会随着内容动态增长,空间不足时会触发额外的 realloc 及 copy 操作,为提高效率有必要预分配足够的空间:

ifstream in("input.txt");
in.seekg(0, ios::end);
streampos len = in.tellg();
in.seekg(0, ios::beg);

string instr;
instr.reserve(len);
instr.assign(istreambuf_iterator<char>(in), istreambuf_iterator<char>());

2. 将文件一次性读入 stringstream 中。

filebuf 和 stringbuf 无法直接通过 rdbuf() 重定向,因此从 filebuf 到 stringbuf 需要一次 copy 操作。最简单的方法是直接复制整个 streambuf :

ifstream in("input.txt");
stringstream ss;
ss<<in.rdbuf();

与 string 的情况相同,这里同样也有一个空间 realloc 及 copy 的问题。但 streambuf 的缓冲区不是那么方便操作的,解决方法是我们给他手动指定一个空间:

ifstream in("input.txt");
in.seekg(0, ios::end);
streampos len = in.tellg();
in.seekg(0, ios::beg);

vector<char> buffer(len);
in.read(&buffer[0], len);

stringstream ss;
ss.rdbuf()->pubsetbuf(&buffer[0], len);

最后再顺便 BS 一下 VC 的 STL = =…

虽然 VC 的编译器效率没的说,但被 STL 拖后腿的话不就白搭了嘛。在文件 IO 方面 (fstream) 比起 MinGW (GCC 4.4.0) 带的要慢好几倍。GCC 的 fstream 格式化读写效率与 C 的比已经不分伯仲,以后应该还会有进一步的提升空间 (编译时格式控制 vs 执行时)

另外上面最后一段程序在 VS2008 (VC9.0) 下应该无法得到预想的结果,跟踪进去看了一下,VC 标准库里的 pubsetbuf 函数体居然是空的!内容如下(中间还有一层函数调用):

virtual _Myt *__CLR_OR_THIS_CALL setbuf(_Elem *, streamsize)
        {       // offer buffer to external agent (do nothing)
        return (this);
        }

看来是等着我们来继承了啊 = = 。而在 MinGW (GCC 4.4.0) 中可以得到预期的结果。

目前已发现 VC 9.0 所带 STL 的几处缺陷,为了保证在任何 C++ 编译器中使用 STL 时能够表现一致,决定将标准库都统一为 STLport 。
MinGW 下则是为了使用 wstream 的宽字符流。
大致记录下编译过程,以后也能做个参考。
编译版本 STLport-5.2.1
 
一、VS2008 (MSVC 9.0) 下
    (1) 将压缩包解到某文件夹,如 D:\STLport (路径中无空格)
    (2) 启动 VS2008 的命令行模式。(注意不是 Run… 中的 cmd)
         cd D:\STLport
    (3) configure msvc9 -x –with-static-rtl –use-boost D:\lib\boost_1_36_0
         msvc9 指明编译器
         -x 参数指明是 cross-compile ,在 lib 文件夹下会生成一个 vc9 文件夹。加不加无所谓。
         –with-static-rtl 指明编译静态库,编译器参数选择 /MT 时会使用此库。
                 若是需要动态库则改为 –with-dynamic-rtl
                 经试验好像没法同时编译动态和静态库。一次一种也无所谓。
                 但是选择编译静态库时也会生成动态库的文件,不过那些是不可用的,文件名中也有 x 字母表示无效文件
         –use-boost 指明 boost 库的路径。仅使用一下 boost 的几个头文件,所以无需事先编译 boost。路径中不要有空格,不然很麻烦
    (4) cd build\lib
         切换到 build\lib 子目录
    (5) nmake /fmsvc.mak install
         开始编译。需要待一会儿。完成后会在 STLport\lib 和 STLport\bin (动态库时) 下生成 LIB 和 DLL 文件。
    (6) 启动 VS2008 设定 include 目录。注意把 STLport\stlport 的位置放在 VC 自带的 STL 库的前面。完毕~
 
—————————-
2009.11.1 补充:
最近根据需要又重新编译了一遍 STLport,发现以前写的这篇文章有几个问题。
先是关于 –use-boost 的选项。STLport 在 5.2.1 版上已经停留好久了,而这期间,boost 的版本从 1.36.0 变动到 1.40.0 ,所以 STLport 中 –use-boost 的选项貌似和新版 boost 已经不能很好的协作了。所以不要再指定这个选项即可,本来这个对 Win32 VC 来说就不是很有必要。
其次关于 –with-static-rtl 和 –with-dynamic-rtl ,以前理解是有误的。
–with-static-rtl 这个指明编译时静态链接到 VC 的 C runtime library (即 libcmt.lib),这样编译出来的库,我们以后在 build 自己的程序时选择 /MT 选项会用到。如果没有其他改动的话,默认也是静态链接到 stlport 库的,如果想要静态链接到 C runtime library 的同时,动态链接到 stlportxx.dll ,那么在自己的项目属性中添加 _STLP_USE_DYNAMIC_LIB 的预定义宏即可。此时会用到带有字母 x 的生成文件(在上面说带 x 的是无效文件,是因为当时不会用,呵呵。)
–with-dynamic-rtl 这个指明编译时动态链接到 VC 的 C runtime library (即 MSVCxxx.lib MSVCP90.dll),这样编译出来的库,我们以后在 build 自己程序时选择 /MD 选项会用到。如果没有其他改动的话,默认也是动态链接到 stlport 库(依赖 stlport.5.2.dll),如果想动态链接到 C runtime library 的同时,静态链接到 stlportxx.lib ,那么在项目属性中添加 _STLP_USE_STATIC_LIB 的预定义宏即可。(此时也会用到带 x 字母的另一些文件。)
 
现在编译的话,直接这么做:
(1) configure msvc9 -x –with-dynamic-rtl
(2) 切换到 build/lib 目录,nmake /fmsvc.mak install clean
(3) configure msvc9 -x –with-static-rtl
(4) 切换到 build/lib 目录,nmake /fmsvc.mak install clean
完毕~ 生成文件在 /lib/vc9 和 /bin/vc9 目录下。
 
STLport 用起来真的很爽,效率比 VC9 自带的 STL 库高不少,特别对于 C++ 的 stream IO 操作优化很好,基本上都可以超过 C 库函数的效率。
—————————————-
 
不过在 VC 中使用 STLport 也发现点小问题,主要是和 VC 的调试器配合不好,因为 STLport 中一些标准容器的结构变得比较复杂,好像没法在单步调试时方便的观察数据变化。
 
二、MinGW (GCC 3.4.5) 下
        (1) start MSYS & cd /lib/STLport-5.2.1
        (2) configure –with-boost=/lib/boost_1_36_0
            # 设置 boost 路径时中间不要有空格,不然后面会很难办
        (3) cd build/lib
        (4) mingw32-make -f gcc.mak all
            # 要用 mingw 带的那个 make,不要用 MSYS 的那个
            # 编译好后把 .a 和 .dll 文件分别复制到 stlport/lib 和 stlport/bin
            # all 选项默认 build 所有动态库,要编译静态库须如下步指定:
        (5) mingw32-make -f gcc.mak release-static dbg-static stldbg-static
            # 编译三种静态库。同样把 .a 文件复制到 stlport/lib
        (6) 设置 MinGW 的 include:
            这个貌似只能在编译时指定参数 -I 和 -L
        (7) 使用时的参数
            –动态链接:
                g++ xxx.cpp -mthreads -I /lib/STLport5.2.1/stlport -L /lib/STLport5.2.1/lib/mingw -lstlport.5.2
            –静态链接:
                在源文件开头添加:#define _STLP_USE_STATIC_LIB
                g++ xxx.cpp -mthreads -I /lib/STLport5.2.1/stlport -L /lib/STLport5.2.1/lib/mingw -lstlport
                    # 与动态链接版相比最后的库名不带版本号
                    # 要链接 debug 版只需把最后的库名改为相应名称即可,如 -lstlportg
 
 
本来一个月前就写好的。。。结果拜某节日所赐那几天 Space live 被封。。。然后居然拖了这么久 = = 还是懒啊~
 
然后再发点牢骚。看中文书一般总说里面错误成堆措辞不准确什么的,说计算机书都去看原版质量多高,结果这本按说也是 STL 标准学习手册的《C++ Stardand Library : A Tutorial and Reference》里也是错误频频,什么样的都有。。。函数名写错、算法写错、时间复杂度写错、函数返回值true false 搞反的,还有很多印刷错误就不一一列举了。当然书的内容还是很好的,只是看的时候得小心点。。。

Win32 + GCC 的一点尝试

前一段试用了 MinGW 5.1.4 (GCC-3.4.5) 感觉还好,但是有两点不满意:
(1) GCC 自带的 libstdc++-v3 不支持宽字符流 (wcin/wcout/wstream…),似乎是与 Win32 平台的 locale 不兼容所致,但仅用 wstring 的话还是可以的。
(2) GCC 版本有点点久远。毕竟 4.x 版都出来几年了。
(3) MSYS 对中文的支持够呛。这个我也认了,反正只用它来编译,文件名都保持鸟文的就没什么问题。
反正免费平台几乎都这样,那帮老外写的系统总是把国际化支持弄得很差,时不时就得担心来个乱码啥的,毕竟人家也不用管那么多,单就那26个字母的话啥时候也不会出问题。
 
当然也有优点
(1) 全套组件免费。不用总为版权问题心存愧疚
     当然 VC 也有免费 Express 版,但好用的工具 Visual Assist、模拟 Vi 编辑器的 ViEmu 等都不是免费的。
(2) 体积小方便携带。一套 MinGW + MSYS 也就 100MB 出头;VC 随便一整就上 GB…
(3) 运行时库默认链接到 MSVCRT.dll,不像 VC 出个新版就整一套新的 MSVCRxx.dll MSVCRPxx.dll 很乱。
     不过我惊异的是 GCC 动态链接出来的文件体积比 VC 静态链接的还大…写小程序的时候对这个还是有点在意的,毕竟完成同样功能的话一个只要几十KB,另一个要几百KB甚至几MB,差别还是有点大。
 
基于以上考虑,决定对 MinGW 系统尝试做点小升级。
对于宽字符流的支持问题,可以换用其他STL库如 STLport。不过不换而直接使用 API 搞定字符转换也麻烦不到哪去。新的 GCC 可以自己编译着试试。
为了编译 GCC 得先编译安装 GMP 和 MPFR 库,比较简单
cd gmp-x.x.x/
mkdir build & cd build
../configure –prefix=/mingw –disable-shared
make
make check (可选)
make install
编译时间还真长,可以看集动画片了。
然后 MPFR 库类似。make 好后只要通过 check 应该就没什么问题了。
 
麻烦的在编译 GCC ,参数真叫一个多,看半天了 documentation 。这个不敢马虎,毕竟设错的话再来一遍要好久…
GCC 的编译正常来要3遍:第1遍用原GCC编译,第2遍用刚生成的 GCC 自己编译自己,第3遍用第2遍生成的继续编译。如果第2遍和第3遍生成的二进制代码一致则编译成功。
可惜试了三次都没完成。几乎都死在 第2遍编译 上了,似乎环境设置哪里还有问题。然后上 MinGW 官网发现已经有发布预编译过的 4.3.0 版了,晕早发现就不去自己编译了,不然后面还有 libstdc++ ,任务量依然很大。
 
然后咱就偷懒只下了 gcc-part-core-4.3.0-mingw32-bin 和 gcc-part-g++-4.3.0-mingw32-bin 两个包,看说明只用覆盖即可。结果编译一个带 iostream 的程序就出问题,一堆头文件说找不到。不得已继续搜,发现去年都已经有人问了,回答是那两个包里文件选择有bug ,得去下最大的包自己把缺的文件挑出来 = =。我X 这问题都出现快一年了你那俩包也不说修复一下。。。然后又下了最大那个包,把 lib/gcc/ming32/4.3.0/include/c++/ext 这个文件夹覆盖一下问题解决。
 
历尽艰险终于用上 GCC 4.3.0 了。。。先别忙着庆祝,稍微编个小程序,结果发现与 3.4.5 版相比生成的文件体积又大了几乎一倍 = =,执行速度嘛就上次那个计算量很大的 ditch 试了一下,确实快了不少 -O3 参数与 VC 编译的相比差距只在 20% 以内,不过这体积嘛 52KB vs. 9KB …
又试了下 wcout 似乎可以用,至少编译顺利通过,locale 好像也能使用,只可惜一运行仍然不正常,说程序运行时不正常关闭 – -。看来还得找 STLport …
总之感觉 MinGW 上 4.3.0 版还是不够成熟,看官方文档似乎打算把 GCC 4.3.1 版作为新的 official release 在半年后发布,希望到那时能解决些问题吧。不过 wchar stream 咱就不奢望了。
 
算了,有空再试  STLport + Boost。以前用 VC 编译过一遍 boost。同时用两套系统还是挺麻烦的,同一套库也得准备两遍 – –

http://dantvt.is-programmer.com/posts/8313 两边同步吧…

很奇怪的,或者说是一个不应成为问题的问题…
std::list 的 size() 方法时间复杂度是多少?第一感觉应该是 O(1) 没错吧,多一个变量用于储存链表长度应该是很轻易的事情。于是有了下面这段代码:

#include<iostream>
#include<list>
#include<ctime>
using namespace std;

int main(){
    time_t start, finish;
    int num = 0;
    list<int> coll;

    start = clock();
    for(int i=0;i<10000;++i){
        coll.push_back(i);
        num += coll.size();
    }
    finish = clock();
    cout<<finish – start<<"   num:"<<num<<endl;

    coll.clear();
    start = clock();
    for(int i=0;i<10000;++i){
        coll.push_back(i);
    }
    finish = clock();
    cout<<finish – start<<endl;
    return 0;
}

对两个循环分别计时比较。前一个循环只比后一个多了一句 num += coll.size(); 为了使编译器确实生成 list::size() 的代码。
在 MinGW 5.1.4 中 (GCC 3.4.5) 编译结果运行如下:

450   num:50005000
10

可以看到,前一个循环居然比后一个多花了几乎 45 倍的时间…当我把循环次数从 10000 加到 100000 时程序半天没出结果…

由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的?果然,在头文件中发现了这一段:

size_type
size() const
{ return std::distance(begin(), end()); }

 

直接调用 <algorithm> 算法库函数 distance() 计算元素个数……怪不得这么慢。然后又用 VS2008 (VC9.0)编译,结果如下:

30   num:50005000
60

奇怪的是前一个循环居然比后一个还快…不过至少知道 VS2008 (VC9.0)里的 size() 应该是 O(1) 的。同样查看了一下代码,如下:

size_type size() const
    {   // return length of sequence
    return (_Mysize);
    }

_Mysize 是一个 size_type 类型的变量。疑问解决。不过又有了新问题:

————— 咱 — 是 — 分 — 隔 — 线 ——————

为什么 GCC 里要把 list::size() 的复杂度搞成 O(N)?

一通搜索后终于看到有这样的讨论:关于 list::splice() 函数。

list 是链表结构,它的优势就在于可以 O(1) 的时间复杂度任意插入删除甚至拼接 list 片段(删除时可能不是,因为要释放内存),list::splice() 是一个很强大的功能,它可在任意位置拼接两个 list,这正是 list 的优势。如果我们在类内部以一个变量储存 list 的长度,那么 splice() 之后新 list 的长度该如何确定?这是一个很严峻的问题,如果要在拼接操作时计算拼接部分的长度,那么将把 O(1) 的时间变成 O(N),这么一来 list 相对 vector 的优势就消失殆尽。

面对这个问题,GCC 和 VC 的 STL 库作者们做了不同的选择。GCC 选择舍弃在 list 内部保存元素数量,而在 size() 时直接从头数到尾,这便出现了开头看到的 O(N) 时间才算出 size();相反,VC 中有了变量 _Mysize ,无论在 insert() erase() splice() 或是 push() pop() 时都需要对其做相应修改。在上面的两个试验中已经看出同样是 10000 个 push_back() 操作,VC 花的时间比较长,不过也仅仅是一个 inc 指令,差别很小就是了。上面几种会改变 list 内容的操作中,大部分对元素数量的影响只是 +1 或 -1,只有 splice() 需要计算拼接部分元素个数,这个差别就大了,咱还是继续用实验证明吧:

#include<iostream>
#include<list>
#include<ctime>
using namespace std;

int main(){
    time_t start,finish;
    list<int> col;
    col.push_back(1);
    col.push_back(10000);

    list<int> col2;
    start = clock();
    for(int i=2;i<10000;++i)
        col2.push_back(i);
    finish = clock();
    cout<<finish – start<<endl;

    int num = 0;
    start = clock();
    for(int i=0;i<10000;++i){
        col.splice(++col.begin(),col2,++col2.begin(),–col2.end());
        num += *(++col.begin());
        col2.splice(++col2.begin(),col,++col.begin(),–col.end());
        num += *(++col2.begin());
    }
    finish = clock();
    cout<<finish – start<<"   num:"<<num<<endl;
    return 0;
}

首先是 MinGW (GCC 3.4.5) 的结果:

10
0   num:60000

可以看到 10000 次 push 是 10,相对的 20000 次 splice() 几乎没花时间 = =

然后是 VS2008 (VC9.0):

20
2714   num:60000

差别非常明显,花了2秒多才完成。当我把循环次数改成 100000 后 GCC 仍是眨眼间的事,VC 却长时间运行无结果……

怎么说呢,GCC 显然是追求效率至上,尽量体现出 list 的优势所在,不过我觉得这么一来倒不如干脆不提供 list 的 size() 方法,有需求的程序员可以自己维护一个变量记录长度,以免误认为 size() 是 O(1) 的而犯下严重错误。相对的 VC 强调功能性和整体效率,可能在实际中需要对链表一段内容做 splice() 操作的机会远远小于求 size() 的操作,所以舍弃前者而保留后者,不过要维护 _Mysize 其他相关函数中也增加了开销。一个见仁见智的问题,我觉得还是 GCC 的选择比较好,list 的优势应该保留,但能在 size() 函数处给个 warning 什么的就好了。

我想还有一个选择是这样:在 list 内部用一个 bool 变量指示当前内部 size 值是有效还是无效。在通常操作时 bool 保持 true,这样在 size() 时直接返回原值即可;在 splice() 后将此 bool 值置为 false 并不计算长度,直到最后又有需要 size() 时发现 bool 是 false 则从头再来一遍 distance() 并再将 bool 置为 true。暂时只想出这么一个算是折中的方法,基本上都能保持两边 O(1) 的效率,但相应其他各关于元素数量的函数内部都要多一个判断当前 size 值是有效还是无效并选择是否改变其值。反正总是不能非常完美

嘛…本来只是发现 size() 的效率问题,没想到却扯出这么一桩事出来…也算长知识了吧

VC 在 Win32 平台还是强啊

小试一下 MinGW,最简单装的 5.1.4 版。看了下附带 GCC 是 3.4.5,只是06年的版本,应该是考虑稳定性的问题。现在 GCC 已经 4.4.0 了吧。
试着编译一个 iostream 输入输出的小程序居然有 400+ KB… strip 后还有 270+…
然后把前面做题目的程序试了下,只用 cstdio 的 fscanf fprintf 倒是体积小了很多只有 20KB+,虽然用了 -O3 但是效率比起 VS2008 编译的还是有挺大差距。拿 VS2008 与前两年的 GCC 比是挺不厚道,不过咱也只是随便试试而已。
果然在 Win 平台下 VC 很无敌…

VC 中的 STL string 实现

今天小实验一下发现 VC9 的 STL string 实现中没有使用 引用计数和写时拷贝
在 VC6.0 时默认还是有这两个特性的,从 VC7.0 开始貌似就取消了,大概是考虑到线程安全问题
如果我不用多线程,这两个特性应该还是可以一定程度上提高效率的吧
不然在返回一个 string 时是否也要考虑用 auto_ptr 了呢…
看来有必要自己实现一个 string ,或者偶尔考虑用一下其他库的…
 
不过从一致性考虑,感觉还是显式使用智能指针实现以上功能比较好,不然其他各种自定类型是不是也有必要封装一个 share_ptr 类似特性呢。

locale的使用总结

locale 是多种 facet 的容器,每种 facet 管理与 locale 相关的一种功能。
facet 除了按名称区别外,更常用的是按 category 来分类。分类情况如下:
 
locale::ctype 类别,包括以下 facet 模板
ctype // 字符分类和转换
codecvt // 字符编码转换
locale::collate 类别,包括以下 facet 模板
collate // 字符串校对
locale::message 类别,包括以下 facet 模板
messages // 从信息目录中获得本地化信息
locale::numeric 类别,包括以下 facet 模板
numpunct // 有关数字和布尔运算表达式中标点符号及格式信息
num_get // 代表数字或布尔值的字符串的解析
num_put   // 代表数字或布尔值的格式化字符串的生成
locale::monetary 类别,包括以下 facet 模板
moneypunct // 货币表达式中的标点符号及格式
money_get   // 代表货币值的字符串的解析
money_put   // 代表货币值的格式化字符串的生成
locale::time 类别,包括以下 facet 模板
time_get // 代表日期和时间的字符串的解析
time_put // 代表日期和时间的格式化字符串的生成
 
使用方法:
locale 对象是不可变的,即在它们的生命周期中,它们的内容不可改变。所包含的 facet 不能进行修改或替换,同时 facet 不能增加或删除。
鉴于以上特性,在使用 locale 时一般都是根据需要生成新的 locale 对象,然后选入IO流中。因此 locale 的构造函数就变得十分多样,方便我们以各种形式构造所需要的locale 对象。
例如,需要 std::wostream 输出中文,我们就需要 locale("chs") 中编码转换相关的功能,但若直接选择 locale("chs"),输出数字时也会进行转换处理,例如将 1234 输出为 "1,234"。为了避免这一转换,就需要保留原 locale("C") 中除了字符相关的其他facet。如下处理即可
locale loc("chs", locale::ctype);
此函数以 global 对应的 locale (一般是 locale("C") ) 初始化 loc 并选择 locale("chs") 的字符相关 facet ,这样我们就可以用 loc 正确输出中文,并保持输出数字时不进行其他处理
其他可参阅 MSDN 中关于 locale 的构造函数说明,解释很详细,用法很简单。
此外,locale 对象还可使用 combine 成员函数 选取其他 locale 中指定 facet 进行组合。总之接口多样,不过也一定程度上增加了对 locale 学习的复杂性。
 
最后,还有更简便的解决方案,即全局 locale 对象。
如果你建立了一个流对象,并且没有规定流使用的 locale 对象,那么流使用全局 locale 对象。如果我们在程序开始处改变全局 locale 对象为我们需要的形式,以后就不需再反复设定每个流的 locale 了。如
locale::global(locale("",locale::ctype));
除了将字符处理部分改为当前系统默认的编码方式外其他不变,这样一般就满足需求了。
再加一条,当流建立后再改变全局locale,则对已建立的流无影响。还有改变 C++ 的全局 locale 对象可能会影响 C 的全局 locale 设定,请不要混用。既然用 locale 对象,就全部采用 C++ 的风格吧