Browsed by
标签: C++

Lua简明教程

Lua简明教程

The Programming Language Lua这几天系统地学习了一下Lua这个脚本语言,Lua脚本是一个很轻量级的脚本,也是号称性能最高的脚本,用在很多需要性能的地方,比如:游戏脚本,nginx,wireshark的脚本,当你把他的源码下下来编译后,你会发现解释器居然不到200k,这是多么地变态啊(/bin/sh都要1M,MacOS平台),而且能和C语言非常好的互动。我很好奇得浏览了一下Lua解释器的源码,这可能是我看过最干净的C的源码了。

我不想写一篇大而全的语言手册,一方面是因为已经有了(见本文后面的链接),重要的原因是,因为大篇幅的文章会挫败人的学习热情,我始终觉得好的文章读起来就像拉大便一样,能一口气很流畅地搞完,才会让人爽(这也是我为什么不想写书的原因)。所以,这必然又是一篇“入厕文章”,还是那句话,我希望本文能够让大家利用上下班,上厕所大便的时间学习一个技术。呵呵。

相信你现在已经在厕所里脱掉裤子露出屁股已经准备好大便了,那就让我们畅快地排泄吧……

运行

首先,我们需要知道,Lua是类C的,所以,他是大小写字符敏感的。

下面是Lua的Hello World。注意:Lua脚本的语句的分号是可选的,这个和GO语言很类似

print("Hello World")

你可以像python一样,在命令行上运行lua命令后进入lua的shell中执行语句。

chenhao-air:lua chenhao$ lua
Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
> print("Hello, World")
Hello, World
> 

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (88 人打了分,平均分: 4.56 )
Loading...
C++11的Lambda使用一例:华容道求解

C++11的Lambda使用一例:华容道求解

(感谢网友 @bnu_chenshuo 投稿)

华容道是一个有益的智力游戏,游戏规则不再赘述。用计算机求解华容道也是一道不错的编程练习题,为了寻求最少步数,求解程序一般用广度优先搜索算法。华容道的一种常见开局如图 1 所示。

广度优先搜索算法求解华容道的基本步骤:

  1. 准备两个“全局变量”,队列 Q 和和集合 S,S 代表“已知局面”。初时 Q 和 S 皆为空。
  2. 将初始局面加入队列 Q 的末尾,并将初始局面设为已知。
  3. 当队列不为空时,从 Q 的队首取出当前局面 curr。如果队列为空则结束搜索,表明无解。
  4. 如果 curr 是最终局面(曹操位于门口,图 2),则结束搜索,否则继续到第 5 步。
  5. 考虑 curr 中每个可以移动的棋子,试着上下左右移动一步,得到新局面 next,如果新局面未知(next ∉ S),则把它加入队列 Q,并设为已知。这一步可能产生多个新局面。
  6. 回到第2步。

其中“局面已知”并不要求每个棋子的位置相同,而是指棋子的投影的形状相同(代码中用 mask 表示),例如交换图 1 中的张飞和赵云并不产生新局面,这一规定可以大大缩小搜索空间。

以上步骤很容易转换为 C++ 代码,这篇文章重点关注的是第 5 步的实现。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (19 人打了分,平均分: 2.95 )
Loading...
C++面试中string类的一种正确写法

C++面试中string类的一种正确写法

(感谢网友 @bnu_chenshuo 投稿)

C++ 的一个常见面试题是让你实现一个 String 类,限于时间,不可能要求具备 std::string 的功能,但至少要求能正确管理资源。具体来说:

  1. 能像 int 类型那样定义变量,并且支持赋值、复制。
  2. 能用作函数的参数类型及返回类型。
  3. 能用作标准库容器的元素类型,即 vector/list/deque 的 value_type。(用作 std::map 的 key_type 是更进一步的要求,本文从略)。

换言之,你的 String 能让以下代码编译运行通过,并且没有内存方面的错误。

void foo(String x)
{
}

void bar(const String& x)
{
}

String baz()
{
  String ret("world");
  return ret;
}

int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;

  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();

  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (34 人打了分,平均分: 3.76 )
Loading...
C++模板”>>”编译问题与词法消歧设计

C++模板”>>”编译问题与词法消歧设计

(感谢 @文艺复兴记(todd) 投递此文)

在编译理论中,通常将编译过程抽象为5个主要阶段:词法分析(Lexical Analysis),语法分析(Parsing),语义分析(Semantic Analysis),优化(Optimization),代码生成(Code Generation)。这5个阶段类似Unix管道模型,上一个阶段的输出作为下一个阶段的输入。其中,词法分析是根据输入源代码文本流,分割出词,识别类别,产生词法元素(Token)流,如:

int a = 10;

​经过词法分析会得到[(Type, “int”), (Identifier, “a”), (AssignOperator, “=”), (IntLiteral, 10)],在后续的语法分析阶段,就会根据这些词法元素匹配相应的语法规则。在我学习编译原理时,教科书中对于词法分析的介绍主要是基于正则表达式的,言下之意就是普通语言的词法规则是可以通过正则表达式描述的。比如,C语言的变量名规则是“包含字母、数字或下划线,并且以字母或下划线开头”,这就可以用正则表达式[a-zA-Z_][a-zA-Z0-9_]*表达。但是,在实践中我发现不管是主流语言,还是自己设计的DSL都大量存在不能简单通过正则表达式进行词法分析的例子。来看C++98的模版例子:

map<int, vector<int>>

上面这段代码会被C++98编译器中报语法错误,原因在于它把“>>”识别成了位右移运算符而不是两个模版右括号,在C++98中必须在两个括号中间加空格,写成

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (25 人打了分,平均分: 3.84 )
Loading...
数据即代码:元驱动编程

数据即代码:元驱动编程

(感谢 @文艺复兴记(todd) 投递此文)

几个小伙伴在考虑下面这个各个语言都会遇到的问题:

问题:设计一个命令行参数解析API

一个好的命令行参数解析库一般涉及到这几个常见的方面:

1) 支持方便地生成帮助信息

2) 支持子命令,比如:git包含了push, pull, commit等多种子命令

3) 支持单字符选项、多字符选项、标志选项、参数选项等多种选项和位置参数

4) 支持选项默认值,比如:–port选项若未指定认为5037

5) 支持使用模式,比如:tar命令的-c和-x是互斥选项,属于不同的使用模式

经过一番考察,小伙伴们发现了这个几个有代表性的API设计:

1. getopt():

getopt()是libc的标准函数,很多语言中都能找到它的移植版本。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (58 人打了分,平均分: 4.03 )
Loading...
类型的本质和函数式实现

类型的本质和函数式实现

(感谢 @文艺复兴记(todd) 投递此文)

在上一篇文章《二叉树迭代器算法》中,我介绍了一种基于栈的二叉树迭代器实现。程序设计语言和Haskell大牛@九瓜 在看过之后评论到:

这里用了 stack 来做,有点偷懒,所以错失了一个抽象思考机会。如果我们能够理解二叉树到线性表的转换过程,完全可以把 Iterator 当作抽象的线性表来看,只要定义了关于 Iterator 的 empty, singleton, 还有 append 操作,实现二叉树的 Iterator 就变得非常直观。

“错失了一个抽象思考机会”是什么意思呢?我理解九瓜的意思是基于栈的实现虽然是正确的,但它缺乏对于迭代器类型本质的理解,不具有通用性。如果能对迭代器进行合适地抽象就可以像二叉树递归遍历一样自然地得出二叉树迭代器,甚至其他更复杂的数据结构,只要我们能写出它的遍历算法,迭代器算法都可以自然推出。

类型的本质

九瓜提到了通过empty, singleton和append操作对Iterator进行抽象,我本来打算直接根据这个思路介绍函数式的二叉树迭代器实现,但是考虑到其实首要的问题在于理解类型的本质,而并不是所有人都具备这个基础,不如先普及一下类型基础再进入具体实现。那么下面我们就先来认识一下类型到底是什么?我们先以来看看表示元素对的Pair类型,可能有人一提到Pair类型马上就会在脑海中浮现出下面的结构:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (23 人打了分,平均分: 3.61 )
Loading...
C语言全局变量那些事儿

C语言全局变量那些事儿

(感谢网友 @我的上铺叫路遥 投稿)

作为一名程序员,如果说沉迷一门编程语言算作一种乐趣的话,那么与此同时反过来去黑一门编程语言就是这种乐趣的升华。今天我们就来黑一把C语言,好好展示一下这门经典语言令人抓狂的一面。

我们知道,全局变量是C语言语法和语义中一个很重要的知识点,首先它的存在意义需要从三个不同角度去理解:对于程序员来说,它是一个记录内容的变量(variable);对于编译/链接器来说,它是一个需要解析的符号(symbol);对于计算机来说,它可能是具有地址的一块内存(memory)。其次是语法/语义:从作用域上看,带static关键字的全局变量范围只能限定在文件里,否则会外联到整个模块和项目中;从生存期来看,它是静态的,贯穿整个程序或模块运行期间(注意,正是跨单元访问和持续生存周期这两个特点使得全局变量往往成为一段受攻击代码的突破口,了解这一点十分重要);从空间分配上看,定义且初始化的全局变量在编译时在数据段(.data)分配空间,定义但未初始化的全局变量暂存(tentative definition)在.bss段,编译时自动清零,而仅仅是声明的全局变量只能算个符号,寄存在编译器的符号表内,不会分配空间,直到链接或者运行时再重定向到相应的地址上。

我们将向您展现一下,非static限定全局变量在编译/链接以及程序运行时会发生哪些有趣的事情,顺便可以对C编译器/链接器的解析原理管中窥豹。以下示例对ANSI C和GNU C标准都有效,笔者的编译环境是Ubuntu下的GCC-4.4.3。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 3.86 )
Loading...
二叉树迭代器算法

二叉树迭代器算法

(感谢 @文艺复兴记(todd) 投递此文)

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 3.13 )
Loading...
Alan Cox:单向链表中prev指针的妙用

Alan Cox:单向链表中prev指针的妙用

Alan Cox
Alan Cox

(感谢网友 @我的上铺叫路遥 投稿)

之前发过一篇二级指针操作单向链表的例子,显示了C语言指针的灵活性,这次再探讨一个指针操作链表的例子,而且是一种完全不同的用法。

这个例子是linux-1.2.13网络协议栈里的,关于链表遍历&数据拷贝的一处实现。源文件是/net/inet/dev.c,你可以从kernel.org官网上下载。

从最早的0.96c版本开始,linux网络部分一直采取TCP/IP协议族实现,这是最为广泛应用的网络协议,整个架构就是经典的OSI七层模型的描述,其中dev.c是属于链路层实现。从功能上看,其位于网络设备驱动程序和网络层协议实现模块之间,作为二者之间的数据包传输通道,一种接口模块而存在——对驱动层的接口函数netif_rx, 以及对网络层的接口函数net_bh。前者提供给驱动模块的中断例程调用,用于链路数据帧的封装;后者作为驱动中断例程底半部(buttom half),用于对数据帧的解析处理并向上层传送。

为了便于理解,这里补充一下网络通信原理和linux驱动中断机制的背景知识。从最底层的物理层说起,当主机和路由器相互之间进行通信的时候,在物理介质上(同轴、光纤等)以电平信号进行传输。主机或路由器的硬件接口(网卡)负责收发这些信号,当信号发送到接口,再由内置的调制解调器(modem)将数字信号转换成二进制码,这样才能驻留在主机的硬件缓存中。这时接口(网卡)设备驱动程序将通过硬中断来获取硬件缓存中的数据,驱动程序是操作系统中负责直接同硬件设备打交道的模块,硬中断的触发是初始化时通过设置控制寄存器实现的,用于通知驱动程序硬件缓存中有新的数据到来。linux卡设备驱动就是在中断处理例程(ISR)中将硬件缓存数据拷贝到内核缓存中,打包成数据链路帧进行解析处理,再向上分发到各种协议层。由于ISR上下文是原子性的、中断屏蔽的,整个步骤又较为繁琐,因此全部放在ISR中处理会影响到其它中断响应实时性,于是linux有实现一种bottom half的软中断处理机制,将整个ISR一分为二,前半部上下文屏蔽所有中断,专门处理紧急的、实时性强的事务,如拷贝硬件缓存并打包封装,后半部上下文没有屏蔽中断(但代码不可重入),用于处理比较耗时且非紧急事务,包括数据帧的解析处理和分发。下面要讲的net_bh就属于后半部。

我们主要关心的是将链路帧分发到协议层那一段逻辑,下面摘自net_bh函数中的一段代码:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (36 人打了分,平均分: 4.11 )
Loading...
“C++的数组不支持多态”?

“C++的数组不支持多态”?

先是在微博上看到了个微博和云风的评论,然后我回了“楼主对C的内存管理不了解”。

后来引发了很多人的讨论,大量的人又借机来黑C++,比如:

//@Baidu-ThursdayWang:这不就c++弱爆了的地方吗,需要记忆太多东西

//@编程浪子张发财:这个跟C关系真不大。不过我得验证一下,感觉真的不应该是这样的。如果基类的析构这种情况不能 调用,就太弱了。

//@程序元:现在看来,当初由于毅力不够而没有深入纠缠c++语言特性的各种犄角旮旯的坑爹细枝末节,实是幸事。为现在还沉浸于这些诡异特性并乐此不疲的同志们感到忧伤。

然后,也出现了一些乱七八糟的理解:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.25 )
Loading...