Archive for ‘边走编程’ Category

August 17, 2010

  const在C,尤其是C++,是个老生常谈的问题,但这里不谈const具体有哪些特性,如何使用,而是说说const在C和C++中的区别。编译器,C使用gcc,C++使用g++,其它编译器(cl等)请自行验证。
  在我的印象中,const就是常量constant)。但这并不是真的。在C中,const仅仅表示其所修饰对象不可修改。常量和所谓“不可修改”有什么区别呢?C中,const int N = 10; 这样的语句声明了一个整型数据,声明之后你不能再为其赋值,此即为不可修改。但在C中,N却不是常量,而诸如372, 3.72, ‘A’之类才是常量,在C中定义常量通常使用#define。而在C++中,const int N = 10; 就会定义N为常量。
  怎么证明呢?你可能知道,定义静态数组,必须使用整型常量指定其大小,那咱们就用这个特性来验证上面描述的观点。

1
2
3
4
5
6
7
int
main(int argc, char **argv)
{
    const int N = 10;
    int a[N] = { 1, 2, 3 };
    return 0;
}
Tags: . 44 views
August 10, 2010

volatile

  可能很多人都没用过C/C++中的这个关键词,甚至不知道它的存在,本人以前也只是有所耳闻,但似懂非懂。
  这是一个类型修饰符,位置同conststatic等。一个使用volatile修饰的变量,比如volatile int i; 每次对该变量的直接引用,都会访问内存,而不是从寄存器中读取(如果其已经在寄存器中)。这样一来,volatile似乎没什么用处,反倒会使数据的读取相对变慢很多。但是,如果没有volatile,编译器可能会优化你的程序,使得数据从寄存器中读取,从而加快程序的运行,但如果这个变量是同其它进程/线程共享的,就可能造成数据的不一致。多线程情况下,你可以使用互斥机制来保证对共享数据访问的原子性。但是,在单片机等嵌入式环境中,硬件经常不会有这种互斥机制的支持,这时某些共享的数据(比如端口)就可能会产生不一致的情况。而使用volatile就会使编译器不对代码进行优化,每次对该变量的访问都会从内存中读取。
  下面通过观察使用volatile前后编译产生的汇编代码的不同,来加深对volatile关键词的理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[ ... ]
main:
[ ... ]
	call	foo # 调用函数foo,返回值保存至寄存器eax
	movl	%eax, 44(%esp) # 为i赋值
	movl	44(%esp), %edx # 读取i值
	movl	44(%esp), %ecx # 读取i值
	movl	44(%esp), %eax # 读取i值
	movl	%ecx, 16(%esp) # 参数k入栈,使用i值
	movl	%edx, 12(%esp) # 参数j入栈,使用i值
	movl	%eax, 8(%esp) # 参数i入栈
	movl	$.LC0, 4(%esp) # 格式字符串地址入栈
	call	__printf_chk
	movl	$0, %eax
	leave
	ret
[ ... ]
Tags: ,. 73 views
July 6, 2010

  对qsort需要注意几点:

  • qsort中第一个参数是待排序数组的开始地址,既然是数组,各元素就是同类型、同大小的对象,且数组是“一维数组”(即地址是连续的);
  • qsort用以区分对象的依据是第二和第三个参数,分别表示对象个数和每个对象的大小(字节);
  • qsort并不知道每个对象的类型和结构,排序准则由用户在第四个参数(比较函数)中指出,qsort按该比较函数准则的“升序”对数组进行排序;
  • 标准C不支持运算符重载,各对象的交换(因为这是qsort)靠的是逐字节的拷贝(memcpy?)。

  在上面的两片代码中,待排序的对象一个是字符型指针,一个是char (*)[10]型数组。然后,就没有然后了。

Tags: ,,. 52 views
July 4, 2010

动态链接库

  动态库和静态库相似,也是各个目标文件的集合。但相比静态链接的程序,动态链接可执行程序要小得多:这类程序运行时需要外部共享 函数库的支持,因此好像并不完整。除了程序体小之外,动态链接允许程序包指定必须的库,而不必将库装入程序包内。动态链接技术还允许多个运行中的程序共享一个库,这样就不会出现同一代码的多份拷贝共占内存的情况了。由于这些原因,当前多数程序采用动态链接技术。
  在Linux中的扩展名通常为.so。但在链接时,并不会被链接到可执行文件中,而是在执行时(需要时)由操作系统的动态加载模块动态地加载到内存,并链接到可执行文件地址空间的相应位置。
  动态链接库的创建也分为编译和”归档”两个阶段,但不同的是在这两个阶段需要使用一些不同的命令选项。首先,需要将源文件编译成一种成为位置无关码(PIC: Position Independent Code)的目标文件,这种代码可以被加入到内存的任何位置却不需要加载器对其进行重定位,关于这种格式可以参考《链接器与加载器》和《程序员的自我修养–链接装载与库》中较为详尽的描述。接下来需要将这些位置无关码“归档”为.so文件。整个过程只需一个工具即可,即gcc。还是上面的源文件,执行以下命令:

1
2
$ cc -c -fpic plus.c sub.c
$ cc -shared -o libmath.so *.o
Tags: ,. 127 views
May 21, 2010

  在形如struct structName varName;的语句中,struct是必须的吗?这是一个显而易见的语法问题,但却容易被忽略,尤其容易被C+C++的同志们忽略。
  在标准C中,struct关键字是必须的:

1
2
3
4
5
6
7
8
9
10
struct structName {
    int n;
};
//~ typedef struct structName structName;
int
main()
{
    struct structName n;
    return 0;
}

若没有前置的struct关键字,上面的代码就不能通过编译。我的gcc会提示”structName” undeclared, parse error before ‘n’的错误。为了方便,通常会使用typedef struct structName structName;语句来为struct structName定义类型别名。
  但是,在C++中,一般情况下,struct/class关键字就不是必须的。但是,在有些情况下struct/class关键字又是必须的,因为这时的名字structName有歧义性。这是因为,C/C++语言允许用户自定义类型和函数同名。

Tags: ,. 38 views
May 18, 2010

  听XiaFei同学讲课,得知queque<T>没有clear()成员函数,甚觉诧异,察知确凿。非但queue,其它容器适配器,如stack, priority_queque之流,亦无此clear,于此谨记。

Tags: . 25 views
May 6, 2010

Bellman-Ford算法简述

  Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。Bellman-Ford算法的流程如下:
  给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,

  1. 数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为\color{red} \infty, Distant[s]为0;
  2. 以下操作循环执行至多n-1次,n为顶点数:
    • 对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;
    • 若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;
  3. 为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

  可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

Tags: ,. 375 views
May 4, 2010

  有码有真相,各位看官您上眼:

1
2
3
4
5
6
int main()
{
	bar(++foo(372)); //~ 此行报错
	bar(++foo(wrap_int(372))); //~ 无错
	return 0;
}

  第一个bar调用中foo返回int型临时对象,想要把这个int临时对象++后传给bar,未遂。第二个bar调用中,foo返回一个包装过的int, 即wrap_int,对这个临时对象进行++(重载),得逞。结论:C++中,基本类型(内置类型)的临时对象不可以作为左值(l-value),即不可以修改;用户自定义类型的临时对象可以作为左值。

Tags: . 40 views
April 30, 2010

  现有一个数列S = \{1,2,3,\ldots,n\},另有一个栈Stack和一个队列Queue,Stack与Queue初始为空。现对S中元素依次进行如下操作:

  1. 若Stack为空,则从S中取出一个元素入栈;
  2. 若Stack非空,则有两种选择:将栈顶元素弹出并入队,或者从S中取出一个元素入栈;
  3. 若S元素已经取完则操作结束,否则执行操作1或2。

  问最终队列Queue有多少种排列情况?聪明且见识广博的你或许一下子就可以说出答案:\120dpi \color{red}\frac{C_{2n}^{n}}{n+1}\quad\textbf{or}\quad\frac{\binom{2n}{n}}{n+1}
  现在对这个结果进行证明。
  设1表示入栈操作,0表示出栈操作。那么上面对n个元素的入栈和出栈操作就构成了长度为2n的由0和1组成的序列,其中1和0的个数均为n个,在没有任何限制的情况下,一共有C_{2n}^n个这样的序列。但是,这里的01序列是建立在一些列的入栈出栈操作的基础上的,因此就会受到入栈、出栈操作的限制。这里,唯一的限制就是栈为空时,无法进行出栈操作。反映到这个01序列中就是,任意位置之前,0的个数都能比1的个数多。因为有了01序列的总数C_{2n}^n,所以为了找出满足条件的序列的个数,只需要找出不符合条件的序列的个数。

Tags: . 66 views
April 29, 2010

  提到C++ STL,首先被人想到的是它的三大组件:Containers, Iterators, Algorithms,即容器,迭代器和算法。容器为用户提供了常用的数据结构,算法大多是独立于容器的常用的基本算法,迭代器是由容器提供的一种接口,算法通过迭代器来操控容器。接下来要介绍的是另外的一种组件,函数对象(Function Object,JJHou译作Functor仿函数)。

什么是函数对象

  顾名思义,函数对象首先是一个对象,即某个类的实例。其次,函数对象的行为和函数一致,即是说可以像调用函数一样来使用函数对象,如参数传递、返回值等。这种行为是通过重载类的()操作符来实现的,举例说明之,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Print
{
public:
    void operator()(int n)
    {
        std::cout<<n<<std::endl;
        return ;
    }
};
int
main(int argc, char **argv)
{
    Print print;
    print(372);
    print.operator()(372); //~ 显式调用
    return 0;
}
Tags: ,. 193 views
Page 1 of 1412345678910...Last »