笑天 的个人资料笑天的共享空间日志列表 工具 帮助

日志


9月30日

堆栈(2)

(heap)和堆栈(stack)的区别(在cuC版看到,觉着好,copy过来)
一、预备知识程序的内存分配

一个由c/C++编译的程序占用的内存分为以下几个部分
1
、栈区(stack由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
2
、堆区(heap一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
3
、全局区(静态区)(static,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4
、文字常量区常量字符串就是放在这里的。 程序结束后由系统释放
5
、程序代码区存放函数体的二进制代码。



二、例子程序
这是一个前辈写的,非常详细
//main.cpp
int a = 0;
全局初始化区
char *p1;
全局未初始化区
main()
{
int b;

char s[] = "abc";

char *p2;

char *p3 = "123456"; 123456
在常量区,p3在栈上。
static int c =0
全局(静态)初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
分配得来得1020字节的区域就在堆区。
strcpy(p1, "123456"; 123456
放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。
}
二、堆和栈的理论知识
2.1
申请方式
stack:
由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请,并指明大小,在cmalloc函数
p1 = (char *)malloc(10);
C++中用new运算符

p2 = (char *)malloc(10);
但是注意p1p2本身是在栈中的。

2.2
申请后系统的响应
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,
会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
2.3
申请大小的限制
栈:在Windows,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
2.4
申请效率的比较:
栈由系统自动分配,速度较快。但程序员是无法控制的。
堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.
另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活

2.5
堆和栈中的存储内容
栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。
堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
2.6
存取效率的比较

char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa
是在运行时刻赋值的;
bbbbbbbbbbb是在编译时就确定的;
但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。
比如:
i nclude ;
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码

10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读到edx中,在根据edx读取字符,显然慢了。
?

2.7
小结:
堆和栈的区别可以用如下的比喻来看出:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。

堆和栈的区别主要分:
操作系统方面的堆和栈,如上面说的那些,不多说了。
还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。

堆与栈

五大内存分区
   
C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
   
栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
   
堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。
   
自由存储区,就是那些由malloc等分配的内存块,他和堆是十分相似的,不过它是用free来结束自己的生命的。
   
全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的C语言中,全局变量又分为初始化的和未初始化的,在C++里面没有这个区分了,他们共同占用同一块内存区。
   
常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改

 

一般认为在c中分为这几个存储区:
    1.
 --有编译器自动分配释放
    2.
 -- 一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收

    3.
全局区(静态区) -- 全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束释放。

    4.
另外还有一个专门放
常量的地方。程序结束释放

    在函数体中定义的变量通常是在栈上,用malloc, calloc, realloc等分配内存的函数分配得到的就是在堆上。在所有函数体外定义的是全局量,加了static修饰符后不管在哪里都存放在全局区(静态区),在所有函数体外定义的static变量表示在该文件中有效,不能extern到别的文件用,在函数体内定义的static表示只在该函数体内有效。另外,函数中的"adgfdf"这样的字符串存放在常量区。
比如:

代码:
int a = 0; //
全局初始化区

char *p1; //
全局未初始化区

main()
{
int b; //

char s[] = "abc"; //

char *p2; //

char *p3 = "123456"; //123456\0
在常量区,p3在栈上。

static int c = 0
//全局(静态)初始化区

p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
//
分配得来得1020字节的区域就在堆区。

strcpy(p1, "123456");
//123456\0
放在常量区,编译器可能会将它与p3所指向的"123456"优化成一块。

}


   
还有就是函数调用时会在栈上有一系列的保留现场及传递参数的操作。

   
栈的空间大小有限定,vc的缺省是2M。栈不够用的情况一般是程序中分配了大量数组和递归函数层次太深。有一点必须知道,当一个函数调用完返回后它会释放该函数中所有的栈空间。栈是由编译器自动管理的,不用你操心。

   
堆是动态分配内存的,并且你可以分配使用很大的内存。但是用不好会产生内存泄漏。并且频繁地mallocfree会产生内存碎片(有点类似磁盘碎片),因为c分配动态内存时是寻找匹配的内存的。而用栈则不会产生碎片。

   
在栈上存取数据比通过指针在堆上存取数据快些。

   
一般大家说的堆栈和栈是一样的,就是栈(stack),而说堆时才是堆heap. 栈是先入后出的,一般是由高地址向低地址生长。

在具体的C/C++编程框架中,这两个概念并不是并行的。对底层机器代码的研究可以揭示,栈是机器系统提供的数据结构,而堆则是C/C++函数库提供的。
   
具体地说,现代计算机(串行执行机制),都直接在代码底层支持栈的数据结构。这体现在,有专门的寄存器指向栈所在的地址,有专门的机器指令完成数据入栈出栈的操作。

   
机制的特点是效率高,支持的数据有限,一般是整数,指针,浮点数等系统直接支持的数据类型,并不直接支持其他的数据结构。因为栈的这种特点,对栈的使用在程序中是非常频繁的。对子程序的调用就是直接利用栈完成的。机器的call指令里隐含了把返回地址推入栈,然后跳转至子程序地址的操作,而子程序中的ret指令则隐含从堆栈中弹出返回地址并跳转之的操作。C/C++中的自动变量是直接利用栈的例子,这也就是为什么当函数返回时,该函数的自动变量自动失效的原因。


   
和栈不同,堆的数据结构并不是由系统(无论是机器系统还是操作系统)支持的,而是由函数库提供的。基本的malloc/realloc/free函数维护了一套内部的堆数据结构。当程序使用这些函数去获得新的内存

空间时,这套函数首先试图从内部堆中寻找可用的内存空间,如果没有可以使用的内存空间,则试图利用系统调用来动态增加程序数据段的内存大小,新分配得到的空间首先被组织进内部堆中去,然后再以适当的形式返回给调用者。当程序释放分配的内存空间时,这片内存空间被返回内部堆结构中,可能会被适当的处理(比如和其他空闲空间合并成更大的空闲空间),以更适合下一次内存分配申请。这套复杂的分配机制实际上相当于一个内存分配的缓冲池(Cache),使用这套机制有如下若干原因:

    1.
系统调用可能不支持任意大小的内存分配。有些系统的系统调用只支持固定大小及其倍数的内存请求(按页分配);这样的话对于大量的小内存分类来说会造成浪费。


    2.
系统调用申请内存可能是代价昂贵的。系统调用可能涉及用户态和核心态的转换。


    3.
没有管理的内存分配在大量复杂内存的分配释放操作下很容易造成内存碎片。


堆和栈的对比


从以上知识可知,

·              栈是系统提供的功能,特点是快速高效,缺点是有限制,数据不灵活;而堆是函数库提供的功能,特点是灵活方便,数据适应面广泛,但是效率有一定降低。

·             栈是系统数据结构,对于进程/线程是唯一的;堆是函数库内部数据结构,不一定唯一。不同堆分配的内存无法互相操作。

·             栈空间分静态分配和动态分配两种。静态分配是编译器完成的,比如自动变量(auto)的分配。动态分配由malloca函数完成。栈的动态分配无需释放(是自动的),也就没有释放函数。为可移植的程序起见,栈的动态分配操作是不被鼓励的!堆空间的分配总是动态的,虽然程序结束时所有的数据空间都会被释放回系统,但是精确的申请内存/释放内存匹配是良好程序的基本要素。

c语言中static变量与全局变量区别

static 声明的变量在C语言中有两方面的特征:
  1)、变量会被放在程序的全局存储区中,这样可以在下一次调用的时候还可以保持原来的赋值。这一点是它与堆栈变量和堆变量的区别。
  2)、变量用static告知编译器,自己仅仅在变量的作用范围内可见。这一点是它与全局变量的区别。(和下面这条一样)
c语言中static变量与全局变量区别:
  两方面,一是在函数中,另一是在文件中。如下:
  Static变量是静态局部变量,虽然在被调用后他的值依然不便但是其他函数不能引用它,而全局变量是所有函数都可以调用的。  
  另外;static的全局变量只能在该文件中使用,就算其它文件用extern来声明也不能用,而没用static定义的全局变量在外部文件中可以通过 extern来声明引用它  
下面是具体的例子
static有两种用法:  
  1、在文件中定义;  
  如   a.c  
  static   int   flag;  
  void   func()  
  {  
  //...  
  }  
  在这种情况下,主要的作用是说明flag是a.c的私有变量,不在a.c这个文件的其它函数不能访问flag.  
  2.在函数定义  
  这主要是说明变量是在堆中定义,如  
  void   func()  
  {  
  static   int   flag;  
  //...  
  }  
  这样的话,函数的值可以反复的被func引用(其它函数也可以使用flag)。  
  由于flag是在堆中定义的,所以如果传出它的地址,如:  
  int   *   func()  
  {  
  static   int   flag;  
  //...  
  return   &flag;  
  }  
  main()  
  {  
  int   *pi=func();  
  *pi=1;  
   
  }  
  这样也是可以的,但不推荐。  
  全局变量也没什么好说的,注意如果全局变量和你的局部变量重名的时候,  
  函数使用变量名满足近邻原则。  
  如:  
   
  int   flag;   //   in   some   head   file  
  extern   int   flag;   //in   a.c  
  void   func()  
  {  
  int   flag;   //1  
  flag=1;  
  if(flag)这个flag用的是   //1处定义的flag  
  //...  
  }  
9月18日

c++知识(3)

---------------------------------------------------------------------------

一次把整个文件读入一个 string

我希望你的答案不要是这样:

string input;
while( !ifs.eof() )
{
    string line;
    getline(ifs, line);
    input.append(line).append(1, '\n');
}

当然了,没有错,它能工作,但是下面的办法是不是更加符合 C++ 的精神呢?

string input(
    istreambuf_iterator<char>(instream.rdbuf()),
    istreambuf_iterator<char>()
);

同样,事先分配空间对于性能可能有潜在的好处:

string input;
input.reserve(10000);
input.assign(
    istreambuf_iterator<char>(ifs.rdbuf()),
    istreambuf_iterator<char>()
);

很简单,不是么?但是这些却是我们经常忽略的事实。
补充一下,这样干是有问题的:

    string input;
    input.assign(
        istream_iterator<char>(ifs),
        istream_iterator<char>()
    );

因为它会忽略所有的分隔符,你会得到一个纯“字符”的字符串。最后,如果你只是想把一个文件的内容读到另一个流,那没有比这更快的了:

    fstream fs("temp.txt");
    cout << fs.rdbuf();

因此,如果你要手工 copy 文件,这是最好的(如果不用操作系统的 API):

   ifstream ifs("in.txt");
   ofstream ofs("out.txt");
   ofs << in.rdbuf();

-------------------------------------------------------------------------

open 一个文件的那些选项

ios::in     Open file for reading
ios::out    Open file for writing
ios::ate    Initial position: end of file
ios::app    Every output is appended at the end of file
ios::trunc  If the file already existed it is erased
ios::binary Binary mode

-------------------------------------------------------------------------

还有 ios 的那些 flag

flag effect if set
ios_base::boolalpha input/output bool objects as alphabetic names (true, false).
ios_base::dec input/output integer in decimal base format.
ios_base::fixed output floating point values in fixed-point notation.
ios_base::hex input/output integer in hexadecimal base format.
ios_base::internal the output is filled at an internal point enlarging the output up to the field width.
ios_base::left the output is filled at the end enlarging the output up to the field width.
ios_base::oct input/output integer in octal base format.
ios_base::right the output is filled at the beginning enlarging the output up to the field width.
ios_base::scientific output floating-point values in scientific notation.
ios_base::showbase output integer values preceded by the numeric base.
ios_base::showpoint output floating-point values including always the decimal point.
ios_base::showpos output non-negative numeric preceded by a plus sign (+).
ios_base::skipws skip leading whitespaces on certain input operations.
ios_base::unitbuf flush output after each inserting operation.
ios_base::uppercase output uppercase letters replacing certain lowercase letters.

There are also defined three other constants that can be used as masks:

constant value
ios_base::adjustfield left | right | internal
ios_base::basefield dec | oct | hex
ios_base::floatfield scientific | fixed

--------------------------------------------------------------------------

用我想要的分隔符来解析一个字符串,以及从流中读取数据

这曾经是一个需要不少麻烦的话题,由于其常用而显得尤其麻烦,但是其实 getline 可以做得不错:

    getline(cin, s, ';');   
    while ( s != "quit" )
    {
        cout << s << endl;
        getline(cin, s, ';');
    }

简单吧?不过注意,由于这个时候 getline 只把 ; 作为分隔符,所以你需要用 ;quit; 来结束输入,否则 getline 会把前后的空格和回车都读入 s ,当然,这个问题可以在代码里面解决。

同样,对于简单的字符串解析,我们是不大需要动用什么 Tokenizer 之类的东西了:

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string s("hello,world, this is a sentence; and a word, end.");
    stringstream ss(s);
   
    for ( ; ; )
    {
        string token;
        getline(ss, token, ',');
        if ( ss.fail() ) break;
       
        cout << token << endl;
    }
}

输出:

hello
world
 this is a sentence; and a word
 end.

很漂亮不是么?不过这么干的缺陷在于,只有一个字符可以作为分隔符。

--------------------------------------------------------------------------

把原本输出到屏幕的东西输出到文件,不用到处去把 cout 改成 fs

#include <iostream>
#include <fstream>
using namespace std;
int main()
{    
    ofstream outf("out.txt"); 
    streambuf *strm_buf=cout.rdbuf();    
    cout.rdbuf(outf.rdbuf()); 
    cout<<"write something to file"<<endl; 
    cout.rdbuf(strm_buf);   //recover 
    cout<<"display something on screen"<<endl;
    system("PAUSE");
    return 0;
}
 

输出到屏幕的是:

display something on screen

输出到文件的是:

write something to file

也就是说,只要改变 ostream 的 rdbuf ,就可以重定向了,但是这招对 fstream 和 stringstream 都没用。

--------------------------------------------------------------------------

关于 istream_iterator 和 ostream_iterator

经典的 ostream_iterator 例子,就是用 copy 来输出:

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main()
{  
    vector<int> vect;
    for ( int i = 1; i <= 9; ++i )
        vect.push_back(i);
       
    copy(vect.begin(), vect.end(),
        ostream_iterator<int>(cout, " ")
    );
    cout << endl;
   
    ostream_iterator<double> os_iter(cout, " ~ ");
    *os_iter = 1.0;
    os_iter++;
    *os_iter = 2.0;
    *os_iter = 3.0;
}

输出:

1 2 3 4 5 6 7 8 9
1 ~ 2 ~ 3 ~

很明显,ostream_iterator 的作用就是允许对 stream 做 iterator 的操作,从而让算法可以施加于 stream 之上,这也是 STL 的精华。与前面的“读取文件”相结合,我们得到了显示一个文件最方便的办法:

    copy(istreambuf_iterator<char>(ifs.rdbuf()),
         istreambuf_iterator<char>(),
         ostreambuf_iterator<char>(cout)
    );

同样,如果你用下面的语句,得到的会是没有分隔符的输出:

    copy(istream_iterator<char>(ifs),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

那多半不是你要的结果。如果你硬是想用 istream_iterator 而不是 istreambuf_iterator 呢?还是有办法:

    copy(istream_iterator<char>(ifs >> noskipws),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

但是这样不是推荐方法,它的效率比第一种低不少。
如果一个文件 temp.txt 的内容是下面这样,那么我的这个从文件中把数据读入 vector 的方法应该会让你印象深刻。

12345 234 567
89    10

程序:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main()
{  
    ifstream ifs("temp.txt");
   
    vector<int> vect;
    vect.assign(istream_iterator<int>(ifs),
        istream_iterator<int>()
    );


    copy(vect.begin(), vect.end(), ostream_iterator<int>(cout, " "));
}

输出:

12345 234 567 89 10

很酷不是么?判断文件结束、移动文件指针之类的苦工都有 istream_iterator 代劳了。

-----------------------------------------------------------------------

其它算法配合 iterator

计算文件行数:

    int line_count =
        count(istreambuf_iterator<char>(ifs.rdbuf()),
              istreambuf_iterator<char>(),
              '\n');       

当然确切地说,这是在计算文件中回车符的数量,同理,你也可以计算文件中任何字符的数量,或者某个 token 的数量:

    int token_count =
        count(istream_iterator<string>(ifs),
              istream_iterator<string>(),
              "#include");       

注意上面计算的是 “#include” 作为一个 token 的数量,如果它和其他的字符连起来,是不算数的。

------------------------------------------------------------------------
Manipulator

Manipulator 是什么?简单的说,就是一个接受一个 stream 作为参数,并且返回一个 stream 的函数,比如上面的 unskipws ,它的定义是这样的:

  inline ios_base&
  noskipws(ios_base& __base)
  {
    __base.unsetf(ios_base::skipws);
    return __base;
  }

这里它用了更通用的 ios_base 。知道了这一点,你大概不会对自己写一个 manipulator 有什么恐惧感了,下面这个无聊的 manipulator 会忽略 stream 遇到第一个分号之前所有的输入(包括那个分号):

template <class charT, class traits>
inline std::basic_istream<charT, traits>&
ignoreToSemicolon (std::basic_istream<charT, traits>& s)
{
    s.ignore(std::numeric_limits<int>::max(), s.widen(';'));
    return s;
}

不过注意,它不会忽略以后的分号,因为 ignore 只执行了一次。更通用一点,manipulator 也可以接受参数的,下面这个就是 ignoreToSemicolon 的通用版本,它接受一个参数, stream 会忽略遇到第一个该参数之前的所有输入,写起来稍微麻烦一点:

struct IgnoreTo {
    char ignoreTo;
    IgnoreTo(char c) : ignoreTo(c)
    {}
};
   
std::istream& operator >> (std::istream& s, const IgnoreTo& manip)
{
    s.ignore(std::numeric_limits<int>::max(), s.widen(manip.ignoreTo));
    return s;
}

但是用法差不多:

    copy(istream_iterator<char>(ifs >> noskipws >> IgnoreTo(';')),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

其效果跟 IgnoreToSemicolon 一样。

c++知识 (2)

STL 算法
distance
很多时候我们希望在一个 vector ,或者 list ,或者什么其他东西里面,找到一个值在哪个位置,这个时候 find 帮不上忙,而有人就转而求助手写循环了,而且是原始的手写循环:

for ( int i = 0; i < vect.size(); ++i)
    if ( vect[i] == value ) break;

如果编译器把 i 看作 for scope 的一部分,你还要把 i 的声明拿出去。真的需要这样么?看看这个:

    int dist =
        distance(col.begin(),
            find(col.begin(), col.end(), 5));

其中 col 可以是很多容器,list, vector, deque... 当然这是你确定 5 就在 col 里面的情形,如果你不确定,那就加点判断:

    int dist;
    list<int>::iterator pos = find(col.begin(), col.end(), 5);
    if ( pos != col.end() )
        dist = distance(col.begin(), pos);

我想这还是比手写循环来的好些吧。

--------------------------------------------------------------------------
max, min
这是有直接的算法支持的,当然复杂度是 O(n),用于未排序容器,如果是排序容器...老兄,那还需要什么算法么?

max_element(col.begin(), col.end());
min_element(col.begin(), col.end());

注意返回的是 iterator ,如果你关心的只是值,那么好:

*max_element(col.begin(), col.end());
*min_element(col.begin(), col.end());

max_element 和 min_element 都默认用 less 来排序,它们也都接受一个 binary predicate ,如果你足够无聊,甚至可以把 max_element 当成 min_element 来用,或者反之:

*max_element(col.begin(), col.end(), greater<int>()); // 返回最小值!
*min_element(col.begin(), col.end(), greater<int>()); // 返回最大值

当然它们的本意不是这个,而是让你能在比较特殊的情况下使用它们,例如,你要比较的是每个元素的某个成员,或者成员函数的返回值。例如:

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <boost/bind.hpp>

using namespace boost;
using namespace std;

struct Person
{
    Person(const string& _name, int _age)
        : name(_name), age(_age)
    {}
    int age;
    string name;
};

int main()
{
    list<Person> col;
    list<Person>::iterator pos;

    col.push_back(Person("Tom", 10));
    col.push_back(Person("Jerry", 12));
    col.push_back(Person("Mickey", 9));

    Person eldest =
        *max_element(col.begin(), col.end(),
            bind(&Person::age, _1) < bind(&Person::age, _2));//>=1.33
   
    cout << eldest.name;
}

输出是 Jerry ,这里用了 boost.bind ,原谅我不知道用 bind2nd, mem_fun 怎么写,我也不想知道...

-------------------------------------------------------------------------
copy_if
没错,STL 里面压根没有 copy_if ,这就是为什么我们需要这个:

template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(
    InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{
    while (begin != end)
    {
        if (p(*begin))*destBegin++ = *begin;
        ++begin;
    }
    return destBegin;
}

把它放在自己的工具箱里,是一个明智的选择。

------------------------------------------------------------------------
惯用手法:erase(iter++)
如果你要去除一个 list 中的某些元素,那可千万小心:(下面的代码是错的!!!)

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    for ( std::list<int>::iterator iter = lst.begin();
          iter != lst.end(); ++iter)
        if ( *iter % 2 == 0 )
            lst.erase(iter);
           
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

当 iter 被 erase 掉的时候,它已经失效,而后面却还会做 ++iter ,其行为无可预期!如果你不想动用 remove_if ,那么唯一的选择就是:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    for ( std::list<int>::iterator iter = lst.begin();
          iter != lst.end(); )
        if ( *iter % 2 == 0 )
            lst.erase(iter++);
        else
            ++iter;
          
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

但是上面的代码不能用于 vector, string 和 deque ,因为对于这些容器, erase 不光令 iter 失效,还令 iter 之后的所有 iterator 失效!

-------------------------------------------------------------------------
erase(remove...) 惯用手法
上面的循环如此难写,如此不通用,如此不容易理解,还是用 STL 算法来的好,但是注意,光 remove_if 是没用的,必须使用 erase(remove...) 惯用手法:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>
#include <functional>
#include <boost/bind.hpp>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    lst.erase(remove_if(lst.begin(), lst.end(),
        boost::bind(std::modulus<int>(), _1, 2) == 0),
        lst.end()
    );
          
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

当然,这里借助了 boost.bind ,让我们不用多写一个没用的 functor 。

简单常识——关于stream
从文件中读入一行

简单,这样就行了:

ifstream ifs("input.txt");
char buf[1000];

ifs.getline(buf, sizeof buf);

string input(buf);

当然,这样没有错,但是包含不必要的繁琐和拷贝,况且,如果一行超过1000个字符,就必须用一个循环和更麻烦的缓冲管理。下面这样岂不是更简单?

string input;
input.reserve(1000);
ifstream ifs("input.txt");
getline(ifs, input);

不仅简单,而且安全,因为全局函数 getline 会帮你处理缓冲区用完之类的麻烦,如果你不希望空间分配发生的太频繁,只需要多 reserve 一点空间。

这就是“简单常识”的含义,很多东西已经在那里,只是我一直没去用。

---------------------------------------------------------------------------

一次把整个文件读入一个 string

我希望你的答案不要是这样:

string input;
while( !ifs.eof() )
{
    string line;
    getline(ifs, line);
    input.append(line).append(1, '\n');
}

当然了,没有错,它能工作,但是下面的办法是不是更加符合 C++ 的精神呢?

string input(
    istreambuf_iterator<char>(instream.rdbuf()),
    istreambuf_iterator<char>()
);

同样,事先分配空间对于性能可能有潜在的好处:

string input;
input.reserve(10000);
input.assign(
    istreambuf_iterator<char>(ifs.rdbuf()),
    istreambuf_iterator<char>()
);

很简单,不是么?但是这些却是我们经常忽略的事实。
补充一下,这样干是有问题的:

    string input;
    input.assign(
        istream_iterator<char>(ifs),
        istream_iterator<char>()
    );

因为它会忽略所有的分隔符,你会得到一个纯“字符”的字符串。最后,如果你只是想把一个文件的内容读到另一个流,那没有比这更快的了:

    fstream fs("temp.txt");
    cout << fs.rdbuf();

因此,如果你要手工 copy 文件,这是最好的(如果不用操作系统的 API):

   ifstream ifs("in.txt");
   ofstream ofs("out.txt");
   ofs << in.rdbuf();

c++知识 (1)

 toupper,tolower
地球人都知道 C++ 的 string 没有 toupper ,好在这不是个大问题,因为我们有 STL 算法:

string s("heLLo");
transform(s.begin(), s.end(), s.begin(), ::toupper);
cout << s << endl;
transform(s.begin(), s.end(), s.begin(), ::tolower);
cout << s << endl;

当然,我知道很多人希望的是 s.to_upper() ,但是对于一个这么通用的 basic_string 来说,的确没办法把这些专有的方法放进来。如果你用 boost stringalgo ,那当然不在话下,你也就不需要读这篇文章了。

------------------------------------------------------------------------
trim
我们还知道 string 没有 trim ,不过自力更生也不困难,比 toupper 来的还要简单:

    string s("   hello   ");
    s.erase(0, s.find_first_not_of(" \n"));
    cout << s << endl;
    s.erase(s.find_last_not_of(' ') + 1);
    cout << s << endl;

注意由于 find_first_not_of 和 find_last_not_of 都可以接受字符串,这个时候它们寻找该字符串中所有字符的 absence ,所以你可以一次 trim 掉多种字符。

-----------------------------------------------------------------------
erase
string 本身的 erase 还是不错的,但是只能 erase 连续字符,如果要拿掉一个字符串里面所有的某个字符呢?用 STL 的 erase + remove_if 就可以了,注意光 remove_if 是不行的。

    string s("   hello, world. say bye   ");
    s.erase(remove_if(s.begin(),s.end(),
        bind2nd(equal_to<char>(), ' ')),
    s.end());

上面的这段会拿掉所有的空格,于是得到 hello,world.saybye。

-----------------------------------------------------------------------
replace
string 本身提供了 replace ,不过并不是面向字符串的,譬如我们最常用的把一个 substr 换成另一个 substr 的操作,就要做一点小组合:

    string s("hello, world");
    string sub("ello, ");
    s.replace(s.find(sub), sub.size(), "appy ");
    cout << s << endl;

输出为 happy world。注意原来的那个 substr 和替换的 substr 并不一定要一样长。

-----------------------------------------------------------------------
startwith, endwith
这两个可真常用,不过如果你仔细看看 string 的接口,就会发现其实没必要专门提供这两个方法,已经有的接口可以干得很好:

    string s("hello, world");
    string head("hello");
    string tail("ld");
    bool startwith = s.compare(0, head.size(), head) == 0;
    cout << boolalpha << startwith << endl;
    bool endwith = s.compare(s.size() - tail.size(), tail.size(), tail) == 0;
    cout << boolalpha << endwith << endl;

当然了,没有 s.startwith("hello") 这样方便。

------------------------------------------------------------------------
toint, todouble, tobool...
这也是老生常谈了,无论是 C 的方法还是 C++ 的方法都可以,各有特色:

    string s("123");
    int i = atoi(s.c_str());
    cout << i << endl;
   
    int ii;
    stringstream(s) >> ii;
    cout << ii << endl;
   
    string sd("12.3");
    double d = atof(sd.c_str());
    cout << d << endl;
   
    double dd;
    stringstream(sd) >> dd;
    cout << dd << endl;
   
    string sb("true");
    bool b;
    stringstream(sb) >> boolalpha >> b;
    cout << boolalpha << b << endl;

C 的方法很简洁,而且赋值与转换在一句里面完成,而 C++ 的方法很通用。

------------------------------------------------------------------------
split
这可是件麻烦事,我们最希望的是这样一个接口: s.split(vect, ',') 。用 STL 算法来做有一定难度,我们可以从简单的开始,如果分隔符是空格、tab 和回车之类,那么这样就够了:

    string s("hello world, bye.");
    vector<string> vect;
    vect.assign(

        istream_iterator<string>(stringstream(s)),

        istream_iterator<string>()

    );


不过要注意,如果 s 很大,那么会有效率上的隐忧,因为 stringstream 会 copy 一份 string 给自己用。

------------------------------------------------------------------------
concat
把一个装有 string 的容器里面所有的 string 连接起来,怎么做?希望你不要说是 hand code 循环,这样做不是更好?

    vector<string> vect;
    vect.push_back("hello");
    vect.push_back(", ");
    vect.push_back("world");
   
    cout << accumulate(vect.begin(), vect.end(), string(""));

不过在效率上比较有优化余地。

-------------------------------------------------------------------------

reverse
其实我比较怀疑有什么人需要真的去 reverse 一个 string ,不过做这件事情的确是很容易:

  std::reverse(s.begin(), s.end());

上面是原地反转的方法,如果需要反转到别的 string 里面,一样简单:

  s1.assign(s.rbegin(), s.rend());

效率也相当理想。

-------------------------------------------------------------------------

解析文件扩展名
字数多点的写法:

    std::string filename("hello.exe");

    std::string::size_type pos = filename.rfind('.');
    std::string ext = filename.substr(pos == std::string::npos ? filename.length() : pos + 1);

不过两行,合并成一行呢?也不是不可以:

    std::string ext = filename.substr(filename.rfind('.') == std::string::npos ? filename.length() : filename.rfind('.') + 1);

我知道,rfind 执行了两次。不过第一,你可以希望编译器把它优化掉,其次,扩展名一般都很短,即便多执行一次,区别应该是相当微小。

BCD码

A-65; a-97;0-48(30H)
故转换的时候可以ORL A,#30H, 实现BCD码到ASC码的转换;
 
在数字系统中,各种数据要转换为二进制代码才能进行处理,而人们习惯于使用十进制数,所以在数字系统的输入输出中仍采用十进制数,这样就产生了用四位二进制数表示一位十进制数的方法,这种用于表示十进制数的二进制代码称为二-十进制代码(Binary Coded Decimal),简称为BCD码。它具有二进制数的形式以满足数字系统的要求,又具有十进制的特点(只有十种有效状态)。在某些情况下,计算机也可以对这种形式的数直接进行运算。常见的BCD码表示有以下几种。

8421BCD编码

  这是一种使用最广的BCD码,是一种有权码,其各位的权分别是(从最有效高位开始到最低有效位)8,4,2,1。
  例 写出十进数563.97D对应的8421BCD码。
    563.97D=0101 0110 0011 . 1001 01118421BCD
  例 写出8421BCD码1101001.010118421BCD对应的十进制数。
    1101001.010118421BCD=0110 1001 . 0101 10008421BCD=69.58D
  在使用8421BCD码时一定要注意其有效的编码仅十个,即:0000~1001。四位二进制数的其余六个编码1010,1011,1100,1101,1110,1111不是有效编码。