Makefile傻瓜教程

Makefile是组织代码编译的一种简单办法。make工具和makefile是比较复杂且强大的，本教程甚至还没有触及到make工具的皮毛，但是作为入门指南，它可以帮助你快速又轻松地为中小型项目创建自己的Makefile。

右值引用

1. 什么是右值引用

右值引用是C++11新加的一种引用类型，是一种仅能绑定到右值上的引用。不同于左值引用仅用一个&表示，右值引用用两个&&表示。

intro to smart pointer and move semantics

(翻译改写自https://www.learncpp.com/cpp-tutorial/15-1-intro-to-smart-pointers-move-semantics/)

1. 裸指针导致的内存泄漏问题

考虑下面这个函数，在这个函数中我们动态申请了一片内存。

1
2
3
4
5
6

void someFunction()
{
    Resource *ptr = new Resource; // Resource is a struct or class
    // do stuff with ptr here
    delete ptr;
}

这段代码看起来非常直白，但是存在一个问题：我们常常会忘了释放内存。即使我们始终记得释放内存，但是还存在一些case导致内存没有正确释放。

0.进程和线程对比

• 进程有自己的虚拟地址空间，线程没有
• 进程包含的内容有：地址空间、全局变量、打开的文件、子进程、定时器、信号和信号处理程序等
• 线程包含的东西有：程序计数器、寄存器、栈和状态(条件码)。每个线程都有自己的栈，但是堆是共享的。
• 多个线程运行在单一进程的上下文中，共享进程虚拟地址空间的所有内容，包括代码，数据，堆，共享库和打开的文件等。

0. 删除vector中的指定元素

今天来探讨C++中的一个基础问题。如何正确地删除vector中符合条件的某元素。比如，有一个vector<int> nums = {1, 2, 2, 2, 2, 3, 5}，要求删除nums中所有值为2的元素。C++初学者可能很快就写出代码:

1
2
3
4
5

for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
    if (*it == 2) {
        nums.erase(it);
    }
}

平常在使用GDB调试程序的时候，我们经常需要查看一个STL容器里面存储的元素的值是多少。但是用GDB的p命令打印容器，得到的却是一堆乱七八糟的东西。比如有一个vector<int> nums = {1,2,3}，当我们使用p nums命令时，我们得到的结果是:

Q: 如何设计一个特殊的栈,支持min()操作,返回栈中的最小元素.

这个问题来源于去年面试遇到的一道题目,面试官给了20分钟时间让设计这样一个栈.当时时间有限,虽然写出来了一个版本,但是那个版本还存在很多的问题,比如不够通用,只能支持int类型数据;同时,效率也不高, 存在大量的数据拷贝.

C++中引入的引用类型，给我们带来了很大的方便。通过向函数传递引用，我们既可以享受像传递指针一样直接修改变量值的优点，又避免了空指针和野指针造成的问题。在日常开发中我们应该尽量使用引用，避免使用指针。但是引用到底是什么，看起来好像引用跟指针有着千丝万缕的联系，同时两者又有很大的差别，那么引用跟指针到底是什么关系呢？教材上通常会说，引用就是变量的别名，但是光看这句话可能还是不太明白引用的本质。其实按照我的理解引用可以看做一种特殊的指针，在这里做一个总结。

0.指针和引用的区别

指针和引用的区别主要有以下几点：

1. 指针可以先定义后绑定到（指向）某个对象，并且可以置为NULL；引用必须在定义的时候绑定到某对象。
2. 指针可以改变指向的对象，引用在不能改变绑定的对象。（有没有觉得1、2两个特点跟const指针很像？）
3. 通过引用可以像被绑定的对象本身一样操作，指针不可以。
4. 对指针进行sizeof操作得到的是指针本身占用的内存大小，32位系统是4字节，64位系统是8个字节； 对引用进行sizeof操作得到的是被绑定到的变量占用的内存大小。
5. 指针可以有二级、三级等多级指针，引用没有。

在论坛上看到一个同学贴的一段代码如下：

1
2
3
4
5
6
7
8
9
10
11

#include<stdio.h>
int main()
{
    int num, cnt, sum = 0;
    cnt = scanf("%d", &num);
    while (cnt != 1) {
        printf("cnt = %d\n", cnt);
        cnt = scanf("%d", &num);
    }
    return 0;
}

设计算法，返回二叉树T的先序序列的最后一个节点，要求非递归，不能使用栈。

先序遍历先遍历根节点，然后遍历左子树，最后遍历右子树。因此如果有右子树的话，最后一个节点肯定在右子树里面，一直往右走就可以，如果没有右子树的话，最后一个节点肯定在左子树，往左走一步就可以，一直迭代下去直到没有子节点为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class TreeNode :
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x
class Solution:
    def getLastNodeOfPreorderTravel(self, root):
        tmp = root
        while(tmp):
            if tmp.right:
                tmp = tmp.right
            elif tmp.left:
                tmp = tmp.left
            else:
                break
        return tmp

那么相应的，我们可以设计出算法返回中序遍历序列的最后一个节点。

中序遍历就是先遍历左子树，然后遍历根节点，最后遍历右子树。因此如果没有右子树，那么根节点就是最后一个节点；如果有右子树，最后一个节点就在右子树中。迭代下去，找到没有子节点的节点返回即可。

1
2
3
4
5
6
7
8

def getLastNodeOfPreorderTravel(self, root):
    tmp = root
    while(tmp):
        if tmp.right:
            tmp = tmp.right
        else:    
            break
    return tmp

最后，你可能会想如何获得后序遍历的最后一个节点呢？后序遍历顺序是先遍历左子树，后遍历右子树，最后遍历根节点，因此最后一个节点必然是根节点。直接返回即可。