发表于   |   分类于   |  

问题

已知链表节点定义如下：

1
2
3
4
5
6
7
class ListNode {
public:
    int val;
    ListNode* next;
public:
    ListNode(int v, ListNode* n = NULL): val(v), next(n) {}
};

如何用 C++ 初始化出指定链表，如：1->2->3？

一般做法

  1. 直接法，这种方法遇到长的链表会导致一行长度过长：

    1
    ListNode* list = new ListNode(1, new ListNode(2, new ListNode(3)));

  2. 分步法，缩短列宽，缺点是初始化长度为n的链表需要n行代码：

    1
    2
    3
    ListNode* list = new ListNode(1);
    ListNode* node2 = list->next = new ListNode(2);
    node2->next = new ListNode(3);

  3. 循环法，最通用的做法：

    1
    2
    3
    4
    5
    6
    7
    int values[] = {1, 2, 3};
    ListNode* list = new ListNode(values[0]);
    ListNode* cur = list;
    for (int i = 1; i < 3; ++i) {
        cur->next = new ListNode(values[i]);
        cur = cur->next;
    }

可以看出，这3种方法都比较啰嗦，如果使用 C++11 的列表初始化，可以简化很多。

列表list 初始化initialization

列表初始化是C++11在旧语法的基础上提出的新语法。其提出是为了解决C++混乱的初始化语法：

1
2
3
4
int i = 1;              // C风格的初始化
int i(1);               // 构造初始化，与上面等价
int arr[] = {1, 2, 3};  // 花括号初始化，用于初始化数组或者结构体
struct { int i; char c; } a = {1, 'c'};

有了列表初始化，上面的初始化可以统一写成：

1
2
3
int i {1};
int arr[] {1, 2, 3};
struct { int i; char c; } a {1, 'a'};

STL 中的容器也支持这种初始化方法：

1
2
std::vector<int> v {1, 2, 3};
std::map<char, int> m {{'a', 1}, {'b', 2}};

这些容器是通过添加一个以std::initializer_list为参数的构造函数实现的。

以std::vector为例，其大致实现代码如下：

1
2
3
4
5
6
7
8
9
template <typename T>
class vector {
    ......
    vector(initializer_list<T> lst) {
        // lst是一个容器，可以通过迭代器遍历出其中的元素，用于初始化vector
        ...
    }
    ......
};

初始化链表

现在，让我们再来看下开头的问题。如何利用列表初始化语法初始化链表呢？

可以直接这样做：

1
ListNode* list {1, new ListNode {2, new ListNode {3}}};

但是这样，跟上面的方法 1 几乎是一样的，初始化语句中有许多冗余的new ListNode。

如何去掉new ListNode呢？

可以使用一个辅助类ListBuilder把new ListNode“包”起来：

1
2
3
4
5
6
7
8
9
10
struct ListBuilder {
    int v;
    ListNode* p;
    ListBuilder(ListNode* p = nullptr): p(p) {}
    ListBuilder(int d, ListBuilder b = ListBuilder())
        : p(new ListNode(d, b.p)) {}
    operator ListNode* () const {
        return p;
    }
};

用法是这样：

1
ListNode* list = ListBuilder {1, {2, {3}}};

当编译器遇到 ListBuilder {1, {2, {3}}} 时，认识到这是一个列表初始化，
会在 ListBuilder的构造函数中寻找匹配函数签名(int, ...)的函数。

ListBuilder(int d, ListBuilder b = ListBuilder()) 被匹配到。

{1, {2, {3}}}中的1被用于初始化参数d,{2, {3}}被用于初始化参数b。

因为b也是ListBuilder，上述过程会递归地进行下去，直到遇到{3}，递归终止。

最后，ListBuilder {1, {2, {3}}}初始化完成，得到一个ListBuilder实例，将它赋值给ListNode* list。

为了实现从ListBuilder到ListNode的转换，需要类型操作符重载：

1
2
3
operator ListNode* () const {
    return p;
}

练习

已知二叉树节点定义如下：

1
2
3
4
5
6
7
8
9
class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
public:
    TreeNode(int x, TreeNode* l = nullptr, TreeNode* r = nullptr)
        : val(x), left(l), right(r) {}
};

如何用 C++ 初始化出二叉树？

发表于   |   分类于   |  

什么是 foreach

foreach 语句一种用于遍历容器的语句，是现代编程语言的标配。使用 foreach 可以方便地对容器进行遍历操作。下面是几种常见语言的 foreach：

  • Python:

    1
    2
    3
    lst = [1, 2, 3]
    for i in lst:
        print(i)

  • C#

    1
    2
    3
    4
    int[] lst = {1, 2, 3};
    foreach (int i in lst) {
        Console.WriteLine(i);
    }

  • Java 8

    1
    2
    3
    4
    int[] lst = {1, 2, 3};
    for (int i : lst) {
        System.out.println(i);
    }

  • PHP

    1
    2
    3
    4
    $lst = array(1, 2, 3);
    foreach ($lst as $i) {
        echo "$i\n";
    }

C++ 中的 foreach

C++ 在 C++11 之前没有 foreach，遍历容器主要有以下两种方法：

  1. 遍历索引, 这种方法继承自 C 语言。

    1
    2
    3
    4
    5
    int arr[] = {1, 2, 3};
    std::vector<int> v(arr, arr + 3);
    for (int i = 0; i < v.size(); ++i) {
        std::cout << v[i] << std::endl;
    }

  2. 使用迭代器(iterator)。

    1
    2
    3
    4
    5
    int arr[] = {1, 2, 3};
    std::vector<int> v(arr, arr + 3);
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << std::endl;
    }

遍历索引的缺点是缺乏通用性，只能用于支持 [] 操作符的容器。

迭代器具有通用性，STL 容器都支持迭代器，缺点则是写起来不方便，迭代器如同裹脚布般又臭又长的类型名容易导致 for 语句长度突破天际。

C++11 为 C++ 增加了 foreach 语句。现在你可以愉快地写出这样的代码：

1
2
3
4
std::vector<int> v {1, 2, 3};   // 使用了 C++11 的列表初始化语法 ;)
for (auto i : v) {              // auto 自动类型推导，与foreach 搭配使用进一步简化语法
    std::cout << i << endl;
}

不幸的是，现在 C++11 尚未普及，有时候你只能使用不支持 C++11 的编译器。遇到这种情况，除了使用上面2种写法，你还有一种选择，那就是动用 C++ 中的黑魔法。

下面有请 C++ 大魔法师Boost为我们演示初级魔法Boost.Foreach：

1
2
3
4
5
6
7
8
9
#include <boost/foreach.hpp>

...

int arr[] = {1, 2, 3};
std::vector<int> v(arr, arr + 3);
BOOST_FOREACH(int i, v) {
    std::cout << i << std::endl;
}

使用BOOST_FOREACH也有缺点，那就是编译需要Boost库，为使用带来了麻烦。

如果你不想/不能用Boost库，那么就只能自己动手造一个轮子了。

如何造 foreach

首先，让我们看下迭代器的写法：

1
2
3
4
for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    int i = *it; // 取出元素值
    ...
}

我们可以定义一个foreach宏，把foreach (i，v)这样的语句变成上面的形式：

1
2
3
#define foreach(i, v) \
    for (??? it = v.begin(); it != v.end(); ++it) { \
        ??? i = *it;

???是相应迭代器和元素的类型，很不幸，在 C++11 之前没有办法可以自动推导类型。

为了解决这个问题，我们只能动用GCC编译器的拓展__typeof__，__typeof__ 用法类似 sizeof，只不过它返回的不是类型大小，而是类型本身。

使用__typeof__后：

1
2
3
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin(); it != v.end(); ++it) { \
        __typeof__(*it) i = *it;

用起来是这样：

1
2
3
4
5
int arr[] = {1, 2, 3};
std::vector<int> v(arr, arr + 3);
foreach (i, v)
    std::cout << i << std::endl;
}

看上去已经实现了foreach的效果，但。。。最后那个不匹配的花括号逼死强迫症啊！

虽然可以把不匹配的花括号定义成一个宏：

1
2
3
4
5
#define endforeach }

foreach (i, v)
    std::cout << i << std::endl;
endforeach

但理想的写法应该是这样的：

1
2
3
foreach (i, v) {
    std::cout << i << std::endl;
}

这样就需要宏里不能出现{。不用{，如何从迭代器里取出元素值呢？

放到for语句里？

1
2
3
4
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin()，__typeof__(*it) i = *it; \
        it != v.end(); \
        i = *++it) \

不行，for语句不能定义两种不同类型的变量。

不过使用for语句取出元素值是正确的思路方向，再使用一条for语句就可以了：

1
2
3
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin(); it != v.end(); ++it) \
        for (__typeof__(*it) i = *it; ???; ???)

接下来，我们得让里面的for只循环一次。可以用一个loop变量实现：

1
2
3
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin(); it != v.end(); ++it) \
        for (__typeof__(*it) i = *it; loop; loop = false)

那么问题来了，loop该定义在哪呢？再用一个for？

1
2
3
4
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin(); it != v.end(); ++it) \
        for (bool loop = true; loop;) \
            for (__typeof__(*it) i = *it; loop; loop = false)

Great！It works！

优化完善

#1 使用 if 代替 for

中间的for循环可以使用if代替：

1
2
3
4
#define foreach(i, v) \
    for (__typeof__(v.begin()) it = v.begin(); it != v.end(); ++it) \
        if (bool loop = true) \
            for (__typeof__(*it) i = *it; loop; loop = false)

#2 调整循环顺序

里面的for循环只循环一遍，放在里面会打断外部for循环的顺序执行。

交换下两者的顺序，再作一点调整：

1
2
3
4
#define foreach(i, v) \
    if (bool loop = true) \
        for (__typeof__(v.begin()) it = v.begin(); loop; loop = false) \
            for (__typeof__(*it) i = *it; it != v.end(); i = *++it)

#3 加上括号,变量名混淆

1
2
3
4
#define foreach(i, v) \
    if (bool __loop = true) \
        for (__typeof__((v).begin()) __it = (v).begin(); __loop; __loop = false) \
            for (__typeof__(*__it) i = *__it; __it != (v).end(); i = *++__it)

加上括号是为了避免类似foreach(i, *p)的语句出错，.的优先级比大多数运算符高。

变量名混淆是为了避免因为重名而导致问题，就像这样：

1
2
3
4
5
6
bool loop = false;
foreach (i : lst) {
    if (i) {
        loop = true; // 这里修改的不是3行前的loop
    }
}

#4 变成 3 行 ;P

1
2
3
#define foreach(i, v) if (bool __loop = true) \
    for (__typeof__((v).begin()) __it = (v).begin(); __loop; __loop = false) \
        for (__typeof__(*__it) i = *__it; __it != (v).end(); i = *++__it)

总结

就这样，我们使用 3 行代码就实现了类似BOOST_FOREACH的功能，是不是很 简单hei mo fa 呢。

发表于   |   分类于   |  

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/bin/python3
from random import choice
from os import system
from readchar import readchar, readkey
from colorama import init
from termcolor import colored

N = 4
SEED = [2] * 9 + [4]
FGS = ['white', 'green', 'yellow', 'blue', 'cyan', 'magenta', 'red']
TERM = (24, 80)
OFFSET = (TERM[0] // 2 - 2, TERM[1] // 2 - 10)

pos          = lambda y, x: '\x1b[%d;%dH' % (y, x)
color        = lambda i: colored('%4d' % i, FGS[len('{:b}'.format(i)) % len(FGS)] if i else 'grey')
formatted    = lambda m: '\n'.join(pos(y, OFFSET[1]) + ' '.join(color(i) for i in l) for l, y in zip(m, range(OFFSET[0], OFFSET[0] + 4)))
combine      = lambda l: ([l[0] * 2] + combine(l[2:]) if l[0] == l[1] else [l[0]] + combine(l[1:])) if len(l) >= 2 else l
expand       = lambda l: [l[i] if i < len(l) else 0 for i in range(N)]
merge_left   = lambda l: expand(combine(list(filter(bool, list(l)))))
merge_right  = lambda l: merge_left(l[::-1])[::-1]
left         = lambda m: list(map(merge_left, m))
right        = lambda m: list(map(merge_right, m))
up           = lambda m: list(map(list, zip(*left(zip(*m)))))
down         = lambda m: list(map(list, zip(*right(zip(*m)))))
add_num_impl = lambda m, p: m[p[0]].__setitem__(p[1], choice(SEED))
add_num      = lambda m: add_num_impl(m, choice([(x, y) for x in range(N) for y in range(N) if not m[x][y]]))
win          = lambda m: 2048 in sum(m, [])
gameover     = lambda m: all(m == t(m) for t in trans.values())
draw         = lambda m: system("clear") or print(formatted(m))

trans = {'a': left, 'd': right, 'w': up, 's': down}
m = [[0] * N for _ in range(N)]
init()
add_num(m)
draw(m)
while True:
    while True:
        move = readkey()
        if move in list(trans.keys()) + ['q']:
            break
    if move == 'q':
        break
    n = trans[move](m)
    if n != m:
        add_num(n)
    m = n
    draw(m)
    if win(m):
        print('\n' + colored('(^_^) You Win!'.center(TERM[1]), 'yellow'))
        break
    elif gameover(m):
        print('\n' + colored('(＞﹏＜) Game Over!'.center(TERM[1]), 'red'))
        break

截图


发表于   |   分类于   |  

Hello world

Hello world 几乎是每个人学习一门语言时写的第一个程序。

C++ 的 Hello world 是这样的：

1
2
3
4
5
6
#include <iostream>
using namespace std;
int main() {
    cout << "Hello world!" << endl;
    return 0;
}

这段代码虽然只有5行(不算上最后一个大括号的话)，但却隐藏着许多C++知识。接下来，让我们一行行的解析这段代码。

第一行

第一行的意思是包含<iostream>这个头文件。 它本身是一段预处理指令。

相关标准描述位于《ISO IEC 14882》（C++11标准文档 ）的 16.2 Source file inclusion [cpp.include]。

<...>是指在系统头文件路径中查找。可用以下命令显示系统头文件路径。

1
2
g++ -E -x c++ - -v < /dev/null
clang++ -E -x c++ - -v < /dev/null

第二行

第二行是引入std命名空间。

相关标准描述位于《ISO IEC 14882》（C++11标准文档 ）的7.3.4 Using directive [namespace.udir]。

在实际工程中，直接using namespace std;应被禁止，因为std命名空间这会污染当前命名空间。

第三行

第三行定义了main函数，main函数是程序的入口。

相关标准描述位于《ISO IEC 14882》的3.6.1 Main function [basic.start.main]。

标准规定，main函数不可预定义，不可重载，允许的函数原型至少包括：

1
2
int main();
int main(int argc, char* argv[]);

第四行

这一行是包含知识点最多的一行。

C++ I/O模型

cout 在<iostream>中只有声明：

1
extern ostream cout;

其类型为ostream，ostream是一个alias： typedef basic_ostream<char> ostream。

basic_ostream的继承结构如下：

运算符重载

cout <<是C++的运算符重载语法。

第四行用到了<ostream>中定义的两个<<运算符重载函数：

1
2
3
4
5
6
template<class traits>
basic_ostream<char,traits>& operator<<(basic_ostream<char,traits>& out,
     const char* s);

basic_ostream<charT,traits>& basic_ostream<charT,traits>::operator<<
    (basic_ostream<charT,traits>&(*pf)(basic_ostream<charT,traits>&));

这两个函数位于std命名空间下。

这一行等价于：

1
operator<<(operator<<(cout, "Hello world"), endl);

ADL(Argument-dependent name lookup)

如果我们去掉第二行using namespace std;，那么这一行就得写成：

1
std::cout << "Hello world" << std::endl;

等价于：

1
operator<<(operator<<(std::cout, "Hello world"), std::endl);

那么问题来了，我们知道这里用到的两个运算符重载函数位于std命名空间，我们没有引入std 命名空间，编译器是如何找到它们的呢？

答案是ADL (Argument-dependent name lookup)。

相关标准描述位于《ISO IEC 14882》的 3.4.2 Argument-dependent name lookup [basic.lookup.argdep]。

ADL, 又称Koenig查找。当一个函数调用中被调用函数名前面没有类、命名空间等作用域限制时，则称之为无限定域的函数调用。
当编译器对其进行无限定域的函数调用名字查找时，如果一般的名字查找失败，会在函数参数的命名空间中继续查找。

I/O manipulator

std::endl是一个 I/O manipulator。

相关标准描述位于《ISO IEC 14882》的 27.7.3.8 Standard basic_ostream manipulators [ostream.manip]

其函数原型为：

1
2
template <class charT, class traits>
std::basic_ostream<charT, traits>& endl(std::basic_ostream<charT, traits>& os);

cout << endl 会调用 basic_ostream<charT, traits> 的运算符重载成员函数：

1
2
3
4
5
typedef basic_ostream<charT, traits> ostream_type;
ostream_type& operator<<(ostream_type& (*pf)(ostream_type&))
{
    return pf(*this);
}

std::endl的定义是这样子的：

1
2
3
template<typename _CharT, typename _Traits>
inline basic_ostream<_CharT, _Traits>& endl(basic_ostream<_CharT, _Traits>& __os)
{ return flush(__os.put(__os.widen('\n'))); }

经过两层函数调用，cout << endl 变成了 flush(cout.put(cout.widen('\n')))。

第五行

第五行的意思是将 0 这个值作为main函数的返回值返回。

相关标准描述位于《ISO IEC 14882》的3.6.1 Main function [basic.start.main]的第5条。

这条语句有两个作用：

  1. 结束main函数。
  2. 使用返回值调用std::exit。

根据标准，当这条语句位于main函数最末尾时可以省略。

发表于   |  

World!