Category name:C++

boost 初体验

03/21/2014 / 5 Comments

最近要把程序改成多线程,准备用boost,结果发现和当时搞OGRE一样,网上各种坑爹教程,连官网的教程也略坑,伤不起。于是想写篇文章,讲讲如何使用开源库进行开发,也梳理一下其他的一些不明觉厉的东西。
在做一些使用到开源库的开发的时候,经常会出现这样三种类型的错误:
1).某个函数下面有一个红色的波浪线,提示错误是找不到函数,某个#include下面有一条红色的波浪线,提示找不到该文件。
2).link error xxxx,无法解析的外部符号xxx函数。
3).计算机丢失xxx.dll

一般在visual studio下按下ctrl+F5会有以下三个动作发生:编译(compile)、链接(link)、运行(execute)三个步骤。编译一般是检查语法错误,并生成obj文件,这个时候一般要include相关的头文件。link的时候就是把上个步骤生成的各个obj文件链接到一起生成exe文件,这一步要确保要link到相关的lib文件。运行程序时就是检查各种dll是否存在,然后执行程序。
总结一下就是1需要头文件,2需要lib文件,3需要dll文件。这三个文件又分别对应着编译、链接、执行三个步骤。

先说一下dll(dynamic linkable library)文件吧,首先dll是什么,dll翻译过来就是动态链接库,通俗的来讲就是有需要的时候才会用到的东西,比如一个文本编辑器的保存文件模块,就可以做成一个dll。为什么需要dll文件,有时候一个系统过于庞大,比如说一下3d游戏,或者是dota2,如果要一次性把所有的程序模块都加载到内存,估计很多电脑都会变成小霸王,所以把模块做成dll,需要用到哪些就加载哪些,这也许就是为什么玩dota1的时候每次有卡尔的时候,开始的时候就会卡一下,因为要加载技能的dll。第二个使用dll的原因就是软件更新的问题了,比如dota2这种东西,如果你每次更新都要重新下载的话,那岂不是太坑爹了,所以就做成dll,需要更新哪些模块,直接下载对应模块的dll就行了。

头文件声明声明函数的接口,dll包含函数的可执行代码。还有一个lib,翻译过来叫做静态链接库的东西,lib包含有dll里面函数的地址等信息。其实说通俗点就是一个中间人的作用,当程序在运行到头文件中声明的一个代码的时候,他不知道要运行哪一个dll里面的哪一个函数,但是lib知道。简单的用一个小小的例子来梳理一下三者的关系,假如我们要去岗顶买电脑,一般会有三个角色,自己,组装电脑的,各种硬件供应商。头文件就是我们自己,我们告诉装电脑的我们需要什么样的cpu,多大的内存,还有硬盘、显卡、声卡、机箱、电源等信息,然后他们打电话给各种cpu、硬盘、显卡等供应商去问报价。或者是去东莞按摩,顾客就是头文件,各种客户经理就是lib文件,各种技师就是dll。当然也有的一些没有dll的,只有lib的,这种情况是可执行代码比较少的时候,就可以直接放到lib里面。这边再次强调一下,lib文件是会链接到exe文件里面的,但是dll不会,所以如果函数多的话,并且你把他放到lib里面的话,那么exe文件就会很大,会引起的后果请看上一段。就好像你生意小的时候,可以自己去服务,但是生意红火的时候,你还坚持自己去服务的话,就会崩盘。

所以如果在visual studio使用一些开源的库开发,我们需要的也只有两种东西:头文件、lib文件。
看完上面的东西之后,我们再通过opencv环境配置来复习一下头文件、lib文件、dll文件以及编译、链接、运行这些东西。
1)include directory 这个就是指定头文件的目录 D:\opencv\build\include D:\opencv\build\include\opencv D:\opencv\build\include\opencv2,其实可以只用添加D:\opencv\build\include\opencv2这个目录的,因为opencv目录下包含的都是c的接口,opencv2包含的都是cpp的接口,但是江湖上的骚年都添加了这三个目录,所以还是加吧,免得到时候测试别人的代码的时候又要改。
2)library directory 这个就是指定头文件所对应的的lib文件的目录 D:\opencv\build\x86\vc12\lib
3)linker 应该包含程序中所用到的lib文件名称 opencv_core248d.lib opencv_highgui248d.lib

可能有的人就要问了,为什么这样做了以后在我按下F5调试代码的时候会出现缺少xxx.dll这种错误呢,很简单,因为这个操作已经包含程序的运行了,所以是需要dll文件的,一般的话程序只会扫描exe目录下(还有环境变量Path对应的目录)有没有包含所需要的dll(貌似还会扫描包含程序入口的目录,没试验过),现在就有两种解决方法,一种就是将linker中所有lib对应的dll(可以在opencv\build\x86\vc12\bin找到)移到exe文件的目录下,第二种就是将包含dll文件的目录地址添加到环境变量Path中(右键点击计算机-属性-高级系统设置-环境变量-添加用户变量Path)。

boost开发其实很蛋疼的,因为和大多数蛋疼的开源库(不希是否还记得那年的CEGUI),这种库是没有lib和dll的,需要自己去生成。

boost下载地址,下载完成后解压,然后就可以在目录下找到一个bootstrap.bat的文件,双击一下他就开始干活了,好像是会生成一个bjam.exe的东西,这个程序就可以用来生成使用boost所需要的一些lib。但是我不是用这种方法做的,直接用命令行cd到boost的目录下,然后输入bootstrap回车,然后等他出现提示的时候就输入./b2(忘记了是不是这个,反正提示里面有一个,按照那个输就没错了)回车,然后就开始生成lib了。这些lib会存放在一个叫做stage–>lib的文件夹下面,稍微说一下命名规范,libboost_thread-vc120-mt-gd-1_55可以分为libboost(前缀)、thread(库名称)、vc120(开发工具名称 vc代表visual studio 120代表12.0也就是2013)、gd(debug版本的lib,如果没有的话就代表是release版本的)、1_55(boost版本号).

还是同样的三部曲
1)include directory D:\boost_1_55_0
2)library directory D:\boost_1_55_0\stage\lib
3)linker libboost_thread-vc120-mt-gd-1_55.lib(debug版本) libboost_thread-vc120-mt-1_55.lib(release版本) 不过好像有的地方写着这一步是不需要的,因为boost会进行auto-link,试了一下好像还真可以。

由于boost的函数没有opencv那样复杂,所以就直接在lib完成了代码的时候,没有单独的搞一些dll。
下面是一个多线程的小demo,两个窗口同时显示摄像头图像。

运行的时候会发现,线程之间的切换真是快到无情啊。

关于thread,什么时候要用到thread,我的理解就是当你需要使用到很多个while的时候。或者是你的while里面有一段代码是很耗时的,然后你想把他放在后台慢慢跑,其他部分的代码还是继续跑,这个时候你就可以把这段代码拿出来单独做一个while,总之就是很多个while的并行。

感想:对不起语文老师,表达能力捉急:(
其实boost库还是很强大的,还有很多教程可以研究,还是看一下源码。

[LeetCode] Reverse Words in a String

03/10/2014 / 1 Comment

在进入正题之前先扯点别的,微软campus interview就被问的这题,当时写的不够好,主要面试官要求是char *参数,然后我std::string用多了之后根本搞不清,连strlen都忘了,然后竟然以为sizeof字符串/sizeof char 之后再减一能得到结果…实际上如果字符串是用char数组的话就可以,是char *的话sizeof一下得出的是指针的长度肯定不行,并且注意下面的代码

得出的结果, b为5,而c为3. 原因是char[]是会被编译器解析为char *的,所以参数类型 []和*并没有区别,都是当做*来看待,可以试试重载某一个函数,将其中的*换成[],或者[]换成*, 编译器会告诉你俩函数是同一个函数,func xxx already has a body.
再扯几个别的:(感觉其实都是特基础的东西,当时没学好啊!)
为什么写成5[a]也能访问到a[5]呢?忘记在什么地方看到了,后来自己试了一下果然可以,原因是x[y]会被解析成*(x+y),而[y]x自然就是*(y+x)所以就不会有区别了
可能有人觉得x[y]应该是*(&x[0]+y)才对,但实际上,数组本身作为右值的时候,被解析为数组第一个元素的指针,但左值则还是指整个数组的存储空间。可以看以下例子:

Ok下面完整的题(我面试的时候面试官也只给了模糊的条件,得确认string是什么string, 要不要删多余空格等等)
Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

这里我写成了俩函数,java里的string有个trim()所以我就想着也写一个,实际上,在trim的时候,对于空格的位置已经是查找过的了,所以在第二次reverse的时候完全可以借用位置信息,当然这又是空间换时间的问题了。
由于LeetCode上给的输入参数是std::string,所以我也就偷个懒直接调用std::reverse了,有时间再写个偏纯C的,不过纯C挺蛋疼!

OpenCV:Meet Lena

03/06/2014 / 2 Comments

opencv第一讲,为大家带来OpenCV配置,图片读取、显示、存储,以及摄像头的调用。为了各路大神都能参考,我尽量使用鲁棒性较高的说法。

Step1: 配置OpenCV

OpenCV是Open Source Computer Vision Library的简称,SDK可从其官方网站下载,OpenCV SDK最新版本下载地址

windows的环境配置:下载完成后,我将其解压到D盘,右键点击计算机-属性-高级系统设置-环境变量-添加用户变量Path,值D:\opencv\build\x86\vc12\bin (如果已有Path变量的话,就直接在现有值的后面加个; 然后加上D:\opencv\build\x86\vc12\bin)这个值根据不同情况调整,如果是64位的就x64,如果是vs2010就是vc10,vs2012就是vc11,搞定这些之后就可以开始配置vs里面的开发环境了。

vs20xx环境配置:新建一个win32 控制台程序(win32 console application)或者 win32项目(win32 project)—控制台应用程序&空项目—完成。右键项目名称—属性—vc++目录—在包含目录(include directory)中加上D:\opencv\build\include D:\opencv\build\include\opencv D:\opencv\build\include\opencv2三项,在库目录(library directory)中加上D:\opencv\build\x86\vc12\lib。 然后选择链接器(linker)—输入(input)-加上opencv_core248d.lib opencv_highgui248d.lib。

include directory

library directory

linker-input

Step2: 测试OpenCV

测试:新建一个cpp文件,加入以下代码。然后下载lena.jpg,放到cpp所在目录下,ctrl+F5。

Step3: 

接下来讲一下怎么利用摄像头自拍

下期预告:opencv实现滤镜

[LeetCode Summary] Remove Duplicates

02/19/2014 / No Comments

先看最简单的Remove Element:
Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
这里需要理解的是给的是数组,所以新长度以后的元素都不用管了,例如给[1,2,3,4,5]要remove 3,那么结果只要是[1,2,4,5,x],并且返回新长度4就行,x是什么并不重要

下面是Remove Duplicates From Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

然后变形成可以允许duplicate出现2次,把超过2次的删掉,这个也非常简单,这回用multiset
Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

下面看看链表,由于题目都是单链表,所以删除某一个元素需要指向该元素前一个元素的指针,这样的话头节点就比较蛋疼了,解决方法是自己定义一个头节点,使其next等于原来的头节点,这样的话原来的头节点就跟普通节点一样的操作了。
Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3

最后这题是要求一旦有duplicates,就删掉所有的instance,我的办法是用两个set,然后对链表扫两遍,好像有点耗时间又有点耗空间,待改进
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

[LeetCode] Best Time to Buy and Sell Stock I, II and III

02/18/2014 / 3 Comments

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit.

I: If you were only permitted to complete at most one transaction
这个非常简单,扫一遍记录下当前最小价格,以及当前能获得的最大利润就行。
这里有个小小的代码风格问题,有人喜欢把minPrice设为数组第一个数,然后从数组第二个数开始迭代,我就喜欢设成INT_MAX, 可以看到我这样就不用判断数组是否为空,但是需要从数组第一个数开始迭代。

II: You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
这个需要想通的一点就是,假设股票每天都在涨价,那么每天买入/隔天卖出的总收益,是和第一天买入最后一天卖出的收益等价的。假设股票跌价了的话(第i+1天的价格比第i天的高),那就不买,就不计入总收益了。(一开始比较糊涂,一直在想跌价的时候要等到跌到最低再买入等问题,后来发现这其实根本就不是买股票的问题,股票哪有预先就知道接下来30天的价格的!所以所有的股票策略都不适用啊)

III: You may complete at most two transactions, but you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
第三题必须要读清题,题目说是最多可以完成两笔交易,就是说买入2次卖出2次,并且买第2次之前必须卖掉第一次买的(我一开始还想复杂了,忽略了这个条件)。 既然买入第二次之前必须卖掉第一次买的,那么实际上问题就变成了我需要找到一个i,使得0到i天内那笔交易的最大收益与i到n-1天内那笔交易的最大收益之和最大。这样的话每个单独区间的最大收益在问题I中就已经解决了。接下来就需要考虑效率问题,这里有个神奇的地方是参考别人来的(Link)。 我第一遍的代码特别蛋疼,是O(n^2)的,而这个神奇的方法是O(n)。 这里需要扫三遍:
第一遍从前往后扫,得出在第i天之前进行的那笔交易一共能赚多少
第二遍从后往前扫,注意第i天到第n天最多能赚多少,反过来就是从第n天倒回去到第i天最多能亏多少
第三遍扫之前存下的俩数组,得出最大利润

[LeetCode Summary] Tree Traversal

02/10/2014 / 1 Comment

写一下树的各种遍历以及用遍历结果建树之类的总结
首先前提是树的数据结构就是像下面这样的,后面所有的解法都不考虑在数据结构上做改变(加指向父节点的指针之类的)

递归的方法是最intuitive和readable的,例如中序遍历就是访问一个节点之前要先访问其左子树,然后访问该节点,然后再访问右子树。
前序和后续也是类似,只要交换访问语句的顺序就可以。递归方法时间复杂度都是O(n),空间复杂度则是递归深度,即树的高度O(h)

非递归方法的话,比较容易想到的是用栈+迭代
非递归前序遍历:
方法1是从Programming Interview Exposed看到的,其思路是:
1 先把根节点进栈
2 当栈不为空时,取顶部节点出栈
2.1 访问该节点
2.2 如果右孩子存在,将右孩子压入栈
2.3 如果左孩子存在,将左孩子压入栈

方法1我一开始没想通它是怎么模拟的递归,因为当我想把他套用到中序的非递归遍历的时候,发现是行不通的。之后分析了一下,由于前序遍历根节点遍历完之后,就不再需要使用了,而上面的方法1正是抓住了这个特点,根节点访问完就出栈
而下面这种方法2也是用栈来完成非递归前序遍历,但方法2稍加修改就可以适用于中序遍历(实际上这个方法就是我写中序遍历的时候想到的)
并且这个方法的思路看起来才最接近递归的过程
1 先访问当前节点,再将当前节点压入栈
2 若当前节点有左孩子,对其左孩子重复第一步,直到左孩子为空
3 从栈中取出前一个访问的节点,将其右孩子设为当前节点

未完待续

[LeetCode] Sort List

01/30/2014 / 4 Comments

这个在LeetCode上有两题,一题要求用insertion sort,一提要求用O(nlogn)的方法
做insertion sort的时候脑子进水想成了selection sort,虽然写的没bug,但输入稍微大点的时候OJ说Time Limit Exceeded. 但按理selection sort和 insertion sort都是n^2的,咋会超时呢,先贴代码上来吧,想不通
最蛋疼的就是single linked list, 拿删除来说,你要删除当前节点是没办法做到的,你只能删除当前节点的next节点。所以每次都要去检查cur->next这个节点,若需要删除再把cur->next->next赋值给cur->next。
3/10 更新:忘记来更新这个了,插入排序前几周写好了,具体的话必须把list分成排序和未排序的两段,最开始的时候没有注意将第一段的末尾元素next置空导致cyclic蛋疼的好久

[LeetCode] Spiral Matrix II

01/28/2014 / 4 Comments

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

这种题感觉刚学C++的时候就做过,而且很心烦。我的办法还是先画个图
matrix

因为我的想法是代码肯定是在给当前格子赋值的时候,再去对i或j做增减来到达下一个格子(改变方向),所以图中显示的是对当前格子赋值的时候,目前的行走方向是怎样的。

根据这个图,我第一个想法是设一个direction来判断下一步怎么走。然后的问题是如何判断何时应该改变direction,于是我又观察了一下,最开始一个direction走了n-1步,之后分别是n-2,n-2,n-3,n-3,n-4,n-4这样子,也就是说只有当当前direction为向左和向右的时候,下一个direction走的步数会变少。于是我设了一个step来记录当前走了多少步和一个maxStep记录最大布数。这样就是我第一个解法。

这个做法太烦了,后来又想到个简单点的,这次的图里表示的是赋值完后应该进行什么操作,例如黄色区域都是i++。放到坐标系里画几条线的话,不同区域的i,j就符合一定的条件
matrix

[LeetCode] Median of Two Sorted Arrays

01/26/2014 / No Comments

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

这题的做法肯定只能先合并两个sorted array然后再找中位数才能保证线性的时间复杂度

[LeetCode] Maximum/Minimum Depth of Binary Tree

01/25/2014 / No Comments

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

先做的maximum,maximum实际上就是树的深度或者层数level, 想的比较直接,节点为空depth为0,否则返回左右子树depth中较大的那个+1

然后是minimum depth了,题是这样的
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

一拿到感觉是一样的,节点为空返回0,否则返回左右子树中depth较小的那个+1

然后问题来了,像这样一棵树,当有一边的子树为空的时候,由于空节点返回0,那函数就认为下面这棵树的minimum depth 为1,而实际应该是4

                                        0

                                 /

                            1

                        /

                   2

                        \

                            3

所以在发现有一边的子树为空的时候,就应该去找另一边的最小长度,因为这一边是没有叶子节点的。