C++ 的 ScopeExitGuard

C++ 提供了 RAII 机制,并提倡使用它来管理各种资源,可是在实际中会发现这一套使用起来并不如想象中的那么方便。在 Linux 下开发会遇到大量 open() / close() 或是 malloc() / free() 类似操作,而且大部分都没有现成好用的 C++ wrapper,如果每组操作都自己去寨一个 class OperationGuard 只用来管理资源释放未免又显得过于繁琐。

其实我需要的只是在退出作用域时自动执行一些清理操作,如果能方便的把要进行的操作封装在一个临时对象的析构函数里就好了。在网上搜索了一下,果然已经有 很多人想到了这个问题,现成的实现有 Boost 的 SCOPE_EXIT,看了一下支持的功能很多,用起来也比想象中复杂了不少。于是还是自己来寨一个好了,也不用很复杂:(以下实现参考了SCOPE(EXIT) IN C++11

template<class F>
class ScopeExitGuard_Impl{
    F _f;
public:
    ScopeExitGuard_Impl(F f) : _f(f) {}
    ~ScopeExitGuard_Impl(){
        _f();
    }
};
template<class F>
ScopeExitGuard_Impl<F> ScopeExitGuard(F f){
    return ScopeExitGuard_Impl<F>(f);
}

#define SCOPE_EXIT_GUARD(code) \
    auto scope_exit_##__LINE__ = ScopeExitGuard([&]{code;})

C++11 的 lambda 真是好用啊。在 SCOPE(EXIT) IN C++11 那篇中,lambda 使用了 [=] 来获取外部变量,这样一来就只能读取,无法改写。我在上面的 lambda 中改为 [&] 方便改写外部变量。

使用起来很简单:

int a = 1;
{
    SCOPE_EXIT_GUARD(a = 2);
    a = 3;
}
cout << a << endl; // print: 2
{
    int *p = (int*)::operator new(100 * sizeof(int));
    // label 1
    SCOPE_EXIT_GUARD(::operator delete(p));
    for (int i = 0; i < 10; ++i){
        p[i] = i;
    }
}

如果在 ::operator new() 语句或 label 1 处抛出异常,::operator delete() 就不会被调用,因此只需把释放资源的 SCOPE_EXIT_GURAD 语句与申请资源的语句放在一起就好。

C/C++ Comments(0) 2014年12月12日 15:18

指针和虚函数表

前两天在水木 C++ 版看到两个题目,分别是关于指针和 class 的虚函数表的。关于指针和数组,之前已经打过很久的交道了,比较简单。不过虚函数表以及 class 成员的内存布局一直是模模糊糊的概念,趁此机会把《C++对象模型》拿出来研究了一把。

题目一

#include<stdio.h>  
int main()  
{  
    int a[5] = {1, 2, 3, 4, 5};  
    int *ptr = (int*)(&a + 1);    
    printf("%d,%d\n", *(a+1), *(ptr-1));  
} 

输出什么?

数组和指针类型的互相转换,只要弄清楚指针所指地址以及所指的类型就容易分析了:

  1. a 的类型是 int[5],表示一个长度为 5 的 int 型数组
  2. 由于 a 的类型是数组,因此对 a 进行算数运算时,其所指地址是以 sizeof(A[0]) 为单位变化的,这里即是 sizeof(int),因此 *(a+1)a[1]
  3. a 取地址,得到的类型是 int (*)[5],这是一个指针,其指向一个含有 5 个 int 的数组。因此 &a+1 会使地址向后移动 5 个 int 的空间,得到 a[5] 的地址。
  4. ptrint* 类型,因此它的算数运算的单位是 sizeof(int)ptr-1 即可得到 a[4] 的地址。
  5. 综上,程序输出 2,5

题目二

#include <iostream>
using namespace std;

class A {
    virtual void g() {
        cout << "A::g" << endl;
    }
private:
    virtual void f() {
        cout << "A::f" << endl;
    }
};

class B : public A {
    void g() {
        cout << "B::g" << endl;
    }
    virtual void h() {
        cout << "B::h" << endl;
    }
};

typedef void(*Fun)(void);

int main() {
    B b;
    Fun pFun;
    for (int i = 0; i < 3; i++) {
        pFun = (Fun)*((int*)* (int*)(&b) + i);
        pFun();
    }
}

输出什么?

看那一串丧心病狂的指针操作!!

class 层次很简单,A 里有两个虚函数 g() 和 f(),B 里重写了 g(),又添了一个 h()。A 里那个 private 是多余,所有函数都是 private 的。 main() 里主要就是对那个函数指针 pFun 赋值,然后调用。看来所有的内容都在那个指针操作里。

  1. (&b) 得到 b 的地址,类型是 B*
  2. *(int*)(&b)b 的地址按 int 型指针来解释,并取出这个 int 值。相当于将 b 的前 4 个字节 (32位环境下) 当成一个 int 型读出。假设读出的值是 vptr (好吧……其实就是 vptr)
  3. *((int*)vptr + i) 将上一个操作取出的值再当成一个地址,并添加 i 个单位偏移。由于是 int* 类型,因此每次偏移一个 sizeof(int) 的空间,即 4 字节。粗略来说就相当于读出 vptr[i] 的值。
  4. 最后再转换为 Fun 的函数指针。

用一个图来看一下:

class A 里有两个虚函数,因此它的虚函数表只有两项,分别是 A::g() 和 A::f()。class B 继承自 A,因此它必须首先照搬 A 的虚函数表(前 2 项),然后再添加自己新加的 B::h(),同时在 B 中又重写了 g(),因此 B 的虚函数表里把 A::g() 的位置替换为 B::g()。

根据前面指针的分析可以看出,三次循环分别调用了 B::g(), A::f() 和 B::h()。不过这个调用比较粗暴,完全无视了函数参数。本身类成员函数是带有一个 this 指针做参数的,不过既然这里也没有使用成员变量,因此也就没什么影响了。

以上程序能够成功运行的条件是 class 的虚函数指针位于对象的头部。我试着在 class A 和 class B 中分别添加一个 int 成员,输出结果依然不变(VS2013 和 gcc4.9.2 下),说明这两个编译器都将虚函数指针放在对象头部,没有再试验其他环境,不知道会不会有不同结果。另外,如果是 64位 环境,应将指针变换那一行的所有 int 换成 int64_t 或 long long,不然指针和 int 所占空间不同,地址运算会出错。

 

C/C++ Comments(0) 2014年12月10日 21:45

MSYS2 + MinGW-w64 + Git + gVim 环境配置

以前用 MSYS 的多,最近重装系统顺带把环境重新配一下,发现 MSYS2 挺顺手的。

一、安装 MSYS2

先装 MSYS2 的好处是之后可以将 $HOME 设为 /home/name/,再装其他 *nix 系工具时配置文件都会放在 MSYS2 的 /home/name 下,方便管理。

1. 到 http://sourceforge.net/projects/msys2/ 下载安装。

  安装位置设为 D:/develop/msys64

  添加环境变量 HOME 为 D:\develop\msys64\home\name,这个变量非常有用,后面配置要多次用到。

2. 运行 msys2_shell.bat

pacman -Sy

更新本地包数据

3. 升级核心包

pacman -S --needed filesystem msys2-runtime bash libreadline libiconv libarchive libgpgme libcurl pacman ncurses libintl

之后需要关闭所有 MSYS2 shell,然后运行 autorebase.bat

4. 升级其他包

pacman -Su

运行环境说明:

可以看到 MSYS2 有三个执行脚本,分别是 msys2_shell.bat、mingw32_shell.bat 和 mingw64_shell.bat,查看内容可以看到其中只有一行区别,即是设定 MSYSTEM 变量。这个变量在 /etc/profile 中会用到:

if [ -n "$MSYSTEM" ]
then
  case "$MSYSTEM" in
    MINGW32)
      PATH="/mingw32/bin:${MSYS2_PATH}:${PATH}"
      PKG_CONFIG_PATH="/mingw32/lib/pkgconfig"
      MANPATH="/mingw32/share/man:${MANPATH}"
      TERMINFO=/mingw32/share/terminfo:${TERMINFO}
    ;;
    MINGW64)
      PATH="/mingw64/bin:${MSYS2_PATH}:${PATH}"
      PKG_CONFIG_PATH="/mingw64/lib/pkgconfig"
      MANPATH="/mingw64/share/man:${MANPATH}"
      TERMINFO=/mingw64/share/terminfo:${TERMINFO}
    ;;
    MSYS)
      PATH="${MSYS2_PATH}:/opt/bin:${PATH}"
      PKG_CONFIG_PATH="/usr/lib/pkgconfig:/lib/pkgconfig"
      TERMINFO=/usr/share/terminfo
    ;;
    *)
      PATH="${MSYS2_PATH}:${PATH}"
    ;;
  esac
else
  PATH="${MSYS2_PATH}:${PATH}"
fi

可见,三个 .bat 的区别就是 PATH 的设置,mingw32_shell.bat 优先使用 msys64/mingw32 下的工具,mingw64_shell.bat 优先使用 msys64/mingw64 下的工具,而 msys2_shell.bat 两个都不使用,只用自身 msys 的工具。这么做的好处是当需要编译 32bit Target 的项目时使用 mingw32_shell.bat,64 bit 使用 mingw64_shell.bat,各套工具互不干扰。

继续阅读

未分类 Comments(20) 2014年9月27日 16:40

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

while(step > 0.02){
    for(;;){
        if(x+step <= 100.0 &&
            (ttlen = ttl(x+step, y)) < minlength){
            minlength = ttlen;
            x += step;
        } else if(x-step >=0.0 &&
            (ttlen = ttl(x-step, y)) < minlength){
            minlength = ttlen;
            x -= step;
        } else if(y+step <= 100.0 &&
            (ttlen = ttl(x, y+step)) < minlength){
            minlength = ttlen;
            y += step;
        } else if(y-step >= 0.0 &&
            (ttlen = ttl(x, y-step)) < 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 即可。
今后再处理浮点数的问题时一定要相当小心咯

C/C++ Comments(0) 2009年11月12日 04:41

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 surpport other locale...
mingw libstdc++ doesnot surpport 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 的情况...
 
最后按惯例是程序代码:
  1. // test the performance of C I/O & C++ streams & C++ codecvt facet
  2. #include<cstdio>
  3. #include<iostream>
  4. #include<fstream>
  5. #include<locale>
  6. #include<cstdlib>
  7. #include<ctime>
  8. #include<windows.h>
  9. using namespace std;
  10.  
  11. const int testsize = 50000;
  12.  
  13. int main(){
  14.     char cstr[] = "这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
  15.     wchar_t wstr[] = L"这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
  16.     char buffer[200];
  17.     int cstrlen = strlen(cstr);
  18.     locale defloc("");
  19.  
  20.     clock_t start;
  21.     FILE *cfile;
  22.     ofstream fout;
  23.     wofstream wfout;
  24.  
  25.     // pure text ...........................
  26.     start = clock();
  27.     cfile = fopen("text_out_C_fputs.txt", "w");
  28.     for(int i = 0; i < testsize; ++i){
  29.         fputs(cstr, cfile);
  30.         fputc('\n', cfile);
  31.     }
  32.     fclose(cfile);
  33.     printf("Text out C fputs: %d\n", clock()-start);
  34.  
  35.     start = clock();
  36.     cfile = fopen("test_out_C_fprintf.txt", "w");
  37.     for(int i = 0; i < testsize; ++i){
  38.         fprintf(cfile, "%s\n", cstr);
  39.     }
  40.     fclose(cfile);
  41.     printf("Text out C fprintf: %d\n", clock()-start);
  42.  
  43.     fout.clear();
  44.     start = clock();
  45.     fout.open("text_out_Cpp_ofstream.txt");
  46.     for(int i = 0; i < testsize; ++i){
  47.         fout << cstr << '\n';
  48.     }
  49.     fout.close();
  50.     printf("Text out Cpp ofstream: %d\n", clock()-start);
  51.  
  52.     fout.clear();
  53.     start = clock();
  54.     fout.open("text_out_Cpp_rdbuf.txt");
  55.     for(int i = 0; i < testsize; ++i){
  56.         fout.rdbuf()->sputn(cstr, cstrlen);
  57.         fout.rdbuf()->sputc('\n');
  58.     }
  59.     fout.close();
  60.     printf("Text out Cpp rdbuf: %d\n", clock()-start);
  61.  
  62.     // wchar_t text ...............................
  63.     wfout.clear();
  64.     start = clock();
  65.     wfout.open("wtext_out_Cpp_wofs_defloc.txt");
  66.     wfout.imbue(defloc);
  67.     for(int i = 0; i < testsize; ++i){
  68.         wfout << wstr << L'\n';
  69.     }
  70.     wfout.close();
  71.     printf("wText out Cpp wofs with default locale: %d\n", clock()-start);
  72.  
  73.     fout.clear();
  74.     start = clock();
  75.     char *next;
  76.     const wchar_t *wnext;
  77.     mbstate_t st;
  78.     fout.open("wtext_out_Cpp_codecvt_facet.txt");
  79.     for(int i = 0; i < testsize; ++i){
  80.         use_facet<codecvt<wchar_t, char, mbstate_t> >(defloc).out(
  81.             st, wstr, wstr+sizeof(wstr)/2-1, wnext,
  82.             buffer, buffer+sizeof(buffer)-1, next);
  83.         fout.rdbuf()->sputn(buffer, next-buffer);
  84.         fout.rdbuf()->sputc('\n');
  85.     }
  86.     fout.close();
  87.     printf("wText out Cpp ofs with codecvt facet: %d\n", clock()-start);
  88.  
  89.     fout.clear();
  90.     start = clock();
  91.     fout.open("wtext_out_Cpp_ofs_WinAPI.txt");
  92.     for(int i = 0; i < testsize; ++i){
  93.         WideCharToMultiByte(CP_ACP, 0, wstr, -1, buffer, 200, NULL, NULL);
  94.         fout << buffer << '\n';
  95.     }
  96.     fout.close();
  97.     printf("wText out Cpp ofs with WideCharToMultiByte API: %d\n",
  98.         clock()-start);
  99.  
  100.     // Format out ...........................................
  101.     srand((unsigned)time(NULL));
  102.  
  103.     char datastr[] = "TestDataString实验格式化字符串";
  104.     start = clock();
  105.     cfile = fopen("format_data_out_C_fprintf.txt", "w");
  106.     for(int i = 0; i < testsize; ++i){
  107.         fprintf(cfile, "%d %lf %s\n",
  108.             rand(), double(rand())/RAND_MAX, datastr);
  109.     }
  110.     fclose(cfile);
  111.     printf("Format data out C fprintf: %d\n", clock()-start);
  112.  
  113.     fout.clear();
  114.     start = clock();
  115.     fout.open("format_data_out_Cpp_ofstream.txt");
  116.     for(int i = 0; i < testsize; ++i){
  117.         fout << rand() << ' ' << double(rand())/RAND_MAX << ' '
  118.             << datastr << '\n';
  119.     }
  120.     fout.close();
  121.     printf("Format data out Cpp ofstream: %d\n", clock()-start);
  122.  
  123.     fout.clear();
  124.     start = clock();
  125.     fout.open("format_data_out_Cpp_ofs_facet.txt");
  126.     for(int i = 0; i < testsize; ++i){
  127.         use_facet<num_put<char> >(locale::classic()).put(
  128.             ostreambuf_iterator<char>(fout), fout, ' ', (long)rand());
  129.         fout.rdbuf()->sputc(' ');
  130.         use_facet<num_put<char> >(locale::classic()).put(
  131.             ostreambuf_iterator<char>(fout), fout, ' ',
  132.             double(rand())/RAND_MAX);
  133.         fout.rdbuf()->sputc(' ');
  134.         fout.rdbuf()->sputn(datastr, sizeof(datastr) - 1);
  135.         fout.rdbuf()->sputc('\n');
  136.     }
  137.     fout.close();
  138.     printf("Format data out Cpp ofs with facet: %d\n", clock()-start);
  139.  
  140.     system("pause");
  141. }

C/C++ Comments(0) 2009年10月31日 16:22

fstream 文件 IO 点滴

很多时候较大数据量的文件 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) 中可以得到预期的结果。

C/C++ Comments(0) 2009年10月06日 18:24

从 std::list 中 size() 的时间复杂度引出的讨论...

很奇怪的,或者说是一个不应成为问题的问题...
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() 的效率问题,没想到却扯出这么一桩事出来...也算长知识了吧

C/C++ Comments(0) 2009年5月10日 05:49

STL 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++ 的风格吧

C/C++ Comments(0) 2009年4月25日 07:41

关于 VC 中的 STL string 实现

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

 

C/C++ Comments(0) 2009年4月25日 07:35

USACO 4.3.2 The Primes

够BT的一道题,改了几遍才过 - -
一开始没想费太多内存觉得稍微预存几种结果应该就差不多了,结果完全低估了数据规模。
只好把所有可能用到的模式全预算出来再循环。结果弄了快300行ORZ...
还有一次犯傻没排序就跑去提交了
 
TASK: prime3
LANG: C++
 
Compiling...
Compile: OK
 
Executing...
   Test 1: TEST OK [0.065 secs, 2984 KB]
   Test 2: TEST OK [0.054 secs, 2988 KB]
   Test 3: TEST OK [0.065 secs, 2984 KB]
   Test 4: TEST OK [0.065 secs, 2988 KB]
   Test 5: TEST OK [0.076 secs, 2984 KB]
   Test 6: TEST OK [0.140 secs, 2984 KB]
   Test 7: TEST OK [0.119 secs, 2988 KB]
   Test 8: TEST OK [0.130 secs, 2988 KB]
   Test 9: TEST OK [0.205 secs, 2988 KB]
   Test 10: TEST OK [0.259 secs, 2988 KB]
 
All tests OK.
Your program ('prime3') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
要速度,貌似只能模拟填表的过程,并且每步选限制尽可能多的行或列来填。
第1行和第1列限制最多,开头第1位已定,且各位都不能出现0,先把他们填了。
然后选辅对角线(左下到右上),因为开头结尾两位都已定。
再填主对角线,第1位和第3位已定。
下面是第二行、第二列、第四行、第四列,这四种情况都是 1、2、4 位已定
然后第三行和第三列都只剩下最后一位空缺了。最后检查一下第五行和第五列即可。
 
从上面过程看出要预先计算的是:
(1) 所有5位质数且各位数字和满足条件的数
(2) 第1位已知且满足(1),各位都不为0的组合
(3) 1、5位已知且满足(1)的组合
(4) 1、3位已知且满足(1)的组合
(5) 1、2、3、4位已知且满足(1)的组合
 
其他好像有提出先填第5行和第5列的,因为这两行除了满足质数与数字和外 各位只能是 1、3、7、9 四选一。不过我觉得这没有用,例如只要第一列填了质数,则第5行第一位自然就只会是 1、3、7、9 之一了,先填第5行对第1列来说也并没有其他额外限制作用。但仅是猜测,也没试验过。
 
预先开个100000的数组,第一遍求所有质数(顺便将不是质数的值存为下标方便遍历),然后筛选数字和满足条件的数,同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来,剩下只用循环便是。排序嘛,就每位挨个判断了,也没几个数。

USACO Comments(0) 2009年4月25日 07:29