Archive for ‘边走编程’ Category

August 10, 2010
[C/C++]volatile

volatile

　　可能很多人都没用过C/C++中的这个关键词，甚至不知道它的存在，本人以前也只是有所耳闻，但似懂非懂。
　　这是一个类型修饰符，位置同const、static等。一个使用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: ,. 1,274 views
Filed under: 之语言特性,边走编程 — dutor @ 8:05 pm Comments (3)
July 6, 2010
qsort

　　对qsort需要注意几点：

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

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

Tags: ,,. 136 views
Filed under: 之语言特性,边走编程 — dutor @ 8:57 pm Comments (2)
July 4, 2010
Unix/Linux环境下创建和使用静/动态库

动态链接库

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

1
2

$ cc -c -fpic plus.c sub.c
$ cc -shared -o libmath.so *.o
Tags: ,. 572 views
Filed under: Unix/Linux,边走编程 — dutor @ 10:23 pm Comments (6)
May 21, 2010
struct/class关键字何时是必须的？

　　在形如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: ,. 95 views
Filed under: 之语言特性,边走编程 — dutor @ 9:16 pm Comments (0)
May 18, 2010
[STL]容器适配器没有clear()

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

Tags: . 57 views
Filed under: 边走编程 — dutor @ 9:44 am Comments (2)
May 6, 2010
单源最短路径Bellman-Ford算法

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: ,. 1,233 views
Filed under: 之算法神奇,边走编程 — dutor @ 8:57 pm Comments (3)
May 4, 2010
[C++]临时对象的可变性

　　有码有真相，各位看官您上眼：

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: . 124 views
Filed under: 之算法神奇,边走编程 — dutor @ 8:04 pm Comments (0)
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: . 233 views
Filed under: 之算法神奇,数理空间,边走编程 — dutor @ 7:39 pm Comments (1)
April 29, 2010
[STL]函数对象/仿函数

　　提到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: ,. 953 views
Filed under: 之语言特性,边走编程 — dutor @ 8:37 pm Comments (1)
April 26, 2010
[C++]exit & abort & 析构 & 异常

进程之死

　　对于一个用C++写的程序，被加载至内存后运行，最终走向死亡。程序的死亡大致有三种：

  • 自然死亡，即无疾而终，通常就是main()中的一个return 0;
  • 自杀，当程序发现自己再活下去已经没有任何意义时，通常会选择自杀。当然，这种自杀也是一种请求式的自杀，即请求OS将自己毙掉。有两种方式：void exit(int status)和void abort(void)。
  • 他杀，同现实不同的是，程序家族中的他杀行径往往是由自己至亲完成的，通常这个至亲就是他的生身父亲（还是母亲？）。C++并没有提供他杀的凶器，这些凶器往往是由OS直接或者间接（通过一些进程库，如pthread）提供的。

　　自然死是最完美的结局，他杀是我们最不愿意看到的，自杀虽是迫不得已，但主动权毕竟还是由程序自己掌控的。下面探究程序一下不同的死亡方式对对象的析构有何影响。

Tags: ,. 564 views
Filed under: 之语言特性,边走编程 — dutor @ 8:20 pm Comments (0)
Page 3 of 1612345678910...Last »