查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 
 
 
 

正确地使用STL查找算法

2018-3-3 21:47:19 阅读25 评论0 32018/03 Mar3

以下内容节选自《C++编程规范:101条规则/准则与最佳时间》,看到第85条感觉C++标准库里的查找算法会经常被误用,这条规则是对这些函数很好的总结,而且这些函数还很常用,所以就在这里总结一下了,顺带加写测试代码,以加深对这些函数的理解。查找函数有find/find_if,count/count_if,lower_bound,upper_bound,equal_range,binary_search。

查找操作,无非是从一个序列里查找,序列分为无序列表和有序列表

查找无序范围,应该使用find/find_if或者count/count_if,这两组函数是线性时间查找,无论元素是否在查找范围内,而两者相比,find/find_if效率会更高一点,因为找到匹配后函数就返回了

查找有序范围,应该使用lower_bound,upper_bound,equal_range,binary_search(这个函数需要谨慎地使用,因为它的效率并不高)。这4个函数的查找时间都是对数的。下面说下这几个函数的区别。

lower_bound返回一个迭代器,如果元素存在,指向第一个匹配的位置;如果不存在,指向匹配应该处于的位置。

upper_bound也返回一个迭代器,如果存在,指向最后一个匹配的下一个元素,此位置是添加下一个元素的位置。如果需要在所查找元素之后插入值,该函数正好满足需求。

equal_range能得到lower_bound,upper_bound两种算法的结果,并且开销小于两倍。

binary_search虽然有个好名字,但几乎毫无用处,该函数只返回一个bool值来表示是否匹配到了。

作者  | 2018-3-3 21:47:19 | 阅读(25) |评论(0) | 阅读全文>>

消除工程中第三方库的警告

2018-1-6 8:37:43 阅读33 评论0 62018/01 Jan6

我们都知道编译器在编译程序阶段都会对程序进行合法性的检查,如果不合法则会报出error信息,导致编译不能通过;同时也会进行合理性检查,如果某些语句不合理,则会报出warning信息,通常warning不影响编译生成汇编代码和可执行文件,但是warning信息通常都是友好的,出现warning,一般是代码中有潜在的问题,下面是常见的warning:

未使用函数参数(Unsed function parameter)定义了从未使用过的变量(Variable defined but never used)变量使用前未经初始化(Variable be used without being initialized)不是所有的分支都能正确return有符号数和无符号数不匹配

通常我们在编译项目的时候,都会把警告等级调到最高,比如在vs2015下

 会选中启用所有警告,同样在Qt Creator下的pro文件中,我们也会加上 /Wall来开启最高等级警告,目的就是为了防止由于失误导致的隐藏性错误。

截至到这一步,所有操作都是正确的,并且是推荐的做法,直到某一天,我们的项目,需要引入第三方库,比如Boost,Eigen等等,写好程序,再次编译程序你会发现信息栏会输出一大堆的warning信息,特别是有符号数和无符号数不匹配,但是我们也不能去修改第三方库啊,指不定会出现什么样的奇怪的错误导致编译错误呢。既想关掉第三方库的警告信息,但是需要在自己的项目中继续启用所有警告,那怎么办?

有一个办法:创建一个头文件,这个头文

作者  | 2018-1-6 8:37:43 | 阅读(33) |评论(0) | 阅读全文>>

常用Git命令

2017-8-27 13:25:05 阅读32 评论0 272017/08 Aug27

本文汇总了常用的几条Git命令。

提交改变内容,并添加注释

git commit -a -m "comment"

拉取某个分支的代码

git pull origin mihooke_branch

上传某个分支的代码

git push origin mihooke_branch

创建分支

git checkout mihooke_branch

删除远程分支

git push origin --delete mihooke_branch

删除本地分支

git branch -D mihooke_branch

查看git 提交日志

git reflog

恢复某个提交版本(XXX是指git reflog列出的某个ID值)

git reset --hard XXX

作者  | 2017-8-27 13:25:05 | 阅读(32) |评论(0) | 阅读全文>>

使得一个函数返回固定元素的数组

2017-6-10 18:31:13 阅读36 评论0 102017/06 June10

在C++11之前,如果我们要实现一个函数返回一个数组,比如,返回一个int数组,通常我们会定义一个int指针,而这个指针一般是指向堆内存(因为函数不能返回局部对象),然后让该函数返回该int指针,类似

int *MyFunc(...)

{

int *ptr = new int[NUM];

return ptr;

}

这样做会有一些小问题:该函数的使用者必须时刻牢记释放内存。

C++11提供了一种返回数组的方法,示例如下

typedef int arr[NUM];

using arr = int[NUM];

arr *func()

{

}

其中using语句就是表示arr是包含NUM个int元素的数组,arr可以直接当做函数的返回值。

还有一种方法就是声明一个返回数组指针的函数,示例如下

int (*func(int i))[NUM];

这样的表示法也是返回一个数组的指针,该数组包含NUM个int元素。

另外,C++11还提供了一种方法:尾置返回类型,这种方式可以随意设定函数的返回类型,示例如下

auto func(int i) -> int(*)[NUM]

在函数的参数之后加个指针运算符,后面是返回类型,比如int(*)[NUM]就是包含NUM个int元素的数组指针。

作者  | 2017-6-10 18:31:13 | 阅读(36) |评论(0) | 阅读全文>>

回调和观察者模式

2017-4-11 21:13:19 阅读49 评论0 112017/04 Apr11

在C和C++中,回调是一个模块中的函数指针,可以调用另一个模块中的函数,并且后者不存在对前者的包含或链接依赖。回调的这种特性,使得低层代码能够执行与其不能有依赖关系的高层代码。比如,上位机程序需要调用算法DLL的函数进行处理工作,算法提供了相应头文件和DLL,我们在上位机程序中就可以使用函数指针来调用算法接口函数,而不用让整个工程包含算法DLL编译库,从而降低两者之间的耦合。

有时候,需要通过回调函数来传递参数,可以用一个“闭包”来解决,下面是一个例子:

class CallBackClass

{

public:

typedef void(*CallBackFunc)(char *str, void *data);

void SetCallBack(CallBackFunc, void *data);

private:

CallBackFunc m_cbf;

void *m_data;

};

使用:

if (m_cbf)

{

(*m_cbf)("mihooke", m_data);

}

不过C++中这种封装使用有一个问题,那就是非static成员函数自带this指针,因为this指针也需要传递,这时候当作回调函数会比较复杂,可以为每个成员函数创建一个static方法,并且使用额外的回调参数来传递this指针。

作者  | 2017-4-11 21:13:19 | 阅读(49) |评论(0) | 阅读全文>>

红黑树介绍

2017-3-1 18:35:39 阅读54 评论0 12017/03 Mar1

红黑树,一种二叉查找树。

二叉查找树,有如下性质:

若任意节点的左子树不为空,则左子树的值均小于它的根节点的值若任意节点的右子树不为空,则右子树的值均大于它的根节点的值任意节点的左、右子树均为二叉查找树没有键值相等的节点空树也是二叉查找树

那么,红黑树就是在二叉查找树的每个结点上增加一个存储位来表示节点的颜色,只能是红色或黑色,通过对任何一个节点着色方式的限制,红黑树确保没有一条路径比其它路径长出两倍。它有如下性质:

每个节点要么是红的,要么是黑的根节点是黑的每个叶子节点也是黑的如果一个节点是红色的,那么它的左右儿子节点是黑的对于任何一个节点,其到叶子节点的每条路径都包含相同数目的黑节点。

这样的特性保证了红黑树相对平衡,从而使得查找、删除、增加操作时间复杂度最坏为O(logn)。

当对红黑树进行插入删除操作时,会破坏树的结构,从而红黑性质也会破坏,通过对树的旋转和重新着色来调整。

STL中set和map容器都是采用红黑树的结构来维护的,具有自动调整树结构的特性。

这就是为什么set和map的插入删除操作效率比其他序列容器要高的原因,插入和删除的时候,只要变动对应指针指向即可,,并不需要做内存拷贝和内存移动;既然内存没有变化,那么相应的iterator也没有变化了,还是保存先前的值,所以在插入和删除操作之后,先前保存的iterator并不会失效

作者  | 2017-3-1 18:35:39 | 阅读(54) |评论(0) | 阅读全文>>

C++的反射

2016-12-29 21:07:35 阅读71 评论0 292016/12 Dec29

C++的反射:可以通过类的名字得到对应类型的对象

C++语言本身是不支持反射的,但实际应用中总是会有将对象序列化的需求,总不可能C++不支持,我们就不用C++了,既然发明C++的大师们没有考虑这个,那我们只有自己动手了,毛主席说过“自己动手,丰衣足食”!

天生限制

C++语言本身不支持反射机制,但C++对象总是要序列化的,序列化就是存储到磁盘上,将对象变成一定格式的二进制编码,然后要用的时候再将保存在磁盘上的二进制编码转化成一个内存中的对象,这个过程中总是需要有一个指示来告诉编译器要生成什么样的对象,最简单的方式当然就是类名了,例如:将一个ClassXXX对象存储到磁盘上,再从磁盘读取的时候让编译器根据“ClassXXX”名称来new一个对象。

但是问题出现了,C++语言本身不支持反射,也就是说不能通过如下方式生成一个对象:

ClassXXX object = new “ClassXXX”;

工厂方法

当然,这样的方法不行,那我们只有另辟蹊径。最简单的就是工厂方法了:

ClassXXX* object = FactoryCreate(“ClassXXX”);

至于FactoryCreate的设计就很简单了,if的集合就可以了:

if(name = “ClassXXX”)

return new ClassXXX;

作者  | 2016-12-29 21:07:35 | 阅读(71) |评论(0) | 阅读全文>>

class Base1

{

int m_i;

public:

Base1(int i) {m_i = i;}

virtual int sum() {return m_i;}//如果sum函数是非virtual函数,那么callfun(d)依旧调用的是Base1::sum,此时发生了类型向上转换;如果是virtual函数,那么根据多态原理,会调用派生类的sum函数

};

class Derived1 : public Base1

{

int m_j;

public:

Derived1(int i, int j) :Base1(i), m_j(j) {}

virtual int sum() {return Base1::sum() + m_j;}

};

void callfun(Base1 &b)//如果函数参数是非引用,会发生切片,那么callfun(d)依旧会调用Base1::sum

{

cout<<b.sum()<<endl;

作者  | 2016-12-29 21:05:09 | 阅读(62) |评论(0) | 阅读全文>>

一个解决方案内添加多个工程进行调试

2016-12-5 21:59:09 阅读42 评论0 52016/12 Dec5

像上节我说的管道程序,因为有server端程序和client程序,如果在编译器中打开多个解决方案会影响调试的速度,很是浪费时间,我收到有网友的提问,便把一个解决方案内添加多个工程文件进行调试的步骤说下。

拿命名管道的程序来说,首先建立server端的工程:

 这里我建立的是名为namedpipe解决方案,并且工程名字和方案名字一样,接下来:

点击【新建项目】

新建步骤和正常创建一样。这时,namedpipe解决方案下就有2个项目了:

编写好代码,编译,在此程序中,我们应该先启动server端程序,在namedpipe项目名称上,右键,选择【调试】->【启动新实例】

server端程序启动。接下来,在client项目名称上,右键,选择【调试】->【启动新实例】,那么2个程序就都启动了,可以直接进行调试了。

作者  | 2016-12-5 21:59:09 | 阅读(42) |评论(0) | 阅读全文>>

巧用set容器

2016-11-20 8:58:04 阅读44 评论0 202016/11 Nov20

问题描述:目录下不确定有1.bmp 2.bmp 3.bmp.......的一个或多个,也不确定有没有,在不知道的情况下使得从1.bmp插入该目录中,比如,如果有2.bmp,再次插入的时候需要是1.bmp;如果有1.bmp,再次插入的时候是2.bmp

用set容器解决,可以遍历把所有的bmp保存在一个set中,然后循环插入set中1.bmp 2.bmp 3.bmp……,用pair保存插入的返回值,如果是true,则表示目录下不存在,如果是false,表示已存在,继续下一次循环:

set<CString> setFile;

pair< set<CString>::iterator, bool > setPair;

for (int i=1; i<nSize+2; i++)

{

CString csBmpName;

csBmpName.Format(_T("%d.bmp"), i);

setPair = setFile.insert(csBmpName);

if (setPair.second)

{

nRet = i;

break;

}

}

作者  | 2016-11-20 8:58:04 | 阅读(44) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 

发现好博客

 
 
列表加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 

天气

 
 
模块内容加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 

标签

 
 
数据加载中...
 
 
 
 
 
 
 

北京市 海淀区 摩羯座

 发消息  写留言

 
E-Mail sadandeduoluozhich@163.com
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注