0%

最大堆和最小堆是一种常见的数据结构,其主要用途是实现优先队列。堆的本质是完全二叉树,可以通过数组方式顺序存储;每当堆发生变换时,需要通过节点的上浮和下沉操作,来保证堆的节点之前的严格大小关系。

Read more »

写在前面

拜读Meyers大师的经典书籍《Effective C++》,拨云见日,收获良多,心中很多疑惑迎刃而解。这本书提到的很多C++编程原则对于指导编写高效稳定的C++程序至关重要,值得反复品味,佐以实践。现在脑子记性太差,只好把大师的谆谆教诲搬运过来,时常翻阅。

Read more »

​ 今天看到一个patch fix从std::map中遍历删除元素导致crash问题,突然意识到自己对如何正确地从map等C++容器中删除元素也没有很牢固清醒的认知。重新梳理了下这块的正确做法,记录在此,以备后忘。

Read more »

​ 我们在构造C++对象时,经常会使用两种不同的声明语法;那这两种声明语法对于g++编译器来说到底有什么差异吗,其构造逻辑又会有什么不同吗?一直心存疑惑,做个实验一探究竟。

Read more »

C++11标准新特性

右值引用(Rvalue Reference)是C++11标准引入的特性,它实现了转移语义和精确传递,主要的作用有2个方面:

  1. 消除两个对象交互时不必要的对象拷贝,节省运算存储资源,提高效率;
  2. 能够更简洁明确地定义泛型函数;

左值引用和右值引用

首先区分什么是左值引用和右值引用,简单的定义:

  • 左值引用:就是命名对象,非临时对象,可以在多条代码中使用的对象;我们通常的变量都是左值;
  • 右值引用:就指非命名对象,临时对象,脱离当前代码语句就无法被引用;比如 函数的返回值;

从左值和右值的定义可以得到,左值引用的对象创建后在代码其他地方会被多次使用,其资源的生命周期较长。而右值引用的对象是临时的,通常用来初始化另一个对象;临时对象创建后很快就会被销毁,其创建-销毁造成了一次资源浪费。既然临时对象将永远不会在其他地方被使用,实际上使用临时对象的资源来初始化另一个对象并不需要一次Copy;更高效的做法将临时对象的资源转移(Move)到另一个命名对象,避免资源的Copy和浪费。

Read more »

从用户态到内核态的本质

最近在重温Linux内核相关的内容,当看到用户进程通过系统调用陷入内核态时,对进程由用户态
切换到内核态过程的本质产生了疑惑,原来这和进程的用户栈与内核栈直接相关。

Read more »

简化递归算法

在读《数据结构与算法分析》一书[算法设计技巧]一章时,其中提到了将递归实现简化为非递归实现的方法,
而这种方法正是动态规划的关键思想。

任何数学递归公式都可以翻译成递归算法;但是递归算法的编程实现有可能是非常复杂且低效的。
此时,将递归算法重新写成非递归算法,将子问题的计算结果系统地记录在某种表内。
利用这种方法的一种算法技巧叫做动态规划(Dynamic Programming)。

从这段话提取出如下信息:

  • 简化递归程序的关键是将子问题14的结果记录在表内,从而避免冗余计算;
  • 动态规划算法也是利用了记录子问题的结果这种方法来解决问题;
  • 动态规划算法包括简化递归实现;
Read more »

线性变换和线性变换矩阵

对于从 的线性变换 ,其本质上都是对于 的矩阵变换:.
那么,确定矩阵 的关键则是基于如下观察:线性变换 完全由它对
单位矩阵 的各列所做的变换决定。

Read more »