1 虹少侠

尚未进行身份认证

醉生梦死.....

等级
博文 21
排名 37w+

Redis源码阅读二,链表和字典

Redis链表redis链表本质上就是一个可以前后移动,并带有头尾指针的双向链表它的结构:typedefstructlistNode{structlistNode*prev;structlistNode*next;void*value;//使用void*实现泛型}listNode;typedef...

2019-06-13 21:13:35

Redis源码阅读一,简单动态字符串

Redis简单动态字符串(SDS)的特点1、在计算长度时的时间复杂度为o(1)。2、在进行拷贝,连接字符串时不必担心空间溢出,因为它会根据长度的需要进行扩容。3、二进制安全,传统的char*是以'\0'作为字符串结尾的标志,也就是字符串本身不能包含'\0'否则会截断。4、惰性空间释放,当字符串的空间被手动缩减时,不会将空间释放,而是记录在free字段中,方便之后可能的append、...

2019-06-12 22:28:53

排序算法总结对比

/*常用排序算法分析*/void swap(int&x,int&y){ if(x!=y){ x=x+y; y=x-y; x=x-y; }}/*冒泡排序时间复杂度为o(n^2)两两比较,交换,每次内层循环在未排序序列中找出最大值放到已排序中对于部分有序的序列来说,效率较高稳定*/void bubble_sor...

2019-04-28 10:45:36

B+树插入删除实现(c++)

B+树性质B+树B+树的实现有多种,有关键字和子树个数相等的,还有向B树一样的子树比关键字数量多一个。这里使用第二种方式。1.树的每个节点最多有M个子树2.根节点至少有两个子树(如果不是叶子节点)3.除根节点之外的所有非叶子节点,至少有M/2个子树(向上取整)4.所有非叶子节点包括keycount,child[0],key[1],child[1],key[2]..key[keyco...

2019-03-20 22:29:36

B树插入删除实现(c++)

B树的性质1、树的每个节点最多有M个子树。2、根节点至少有两个子树(除非它是叶子节点)。3、除根节点之外的所有非叶子节点至少有M/2个子树(向上取整)。4、所有非叶子节点包含keycount,childs[0],keys[1],childs[1],keys[2]........keys[keycount],childs[keycount]。也就是所有非叶子节点的子树在key值...

2019-03-14 13:14:59

Effective c++ 读书总结 21-25

条款二十一:必须返回对象时,别妄想返回其reference1、为什么我们会选择返回引用类型因为返回引用类型可以避免以值返回造成的对象构造和析构带来的效率问题。特别是当一个对象内部资源很大的时候,以值返回往往造成效率降低。2、什么情况下可以使用引用返回当一个函数操作是对对象内部资源生效时,且需要返回生效之后的结果的时候。classtest{private:str...

2019-03-11 13:42:37

Effective c++ 读书总结 16-20

条款十六:成对使用new和delete时要使用相同的形式1、在使用new操作符时,事件上做了两件事,一是申请堆区空间,二是在此空间上执行申请类型的构造函数。使用delete也是两件事,一是调用对象的析构函数,释放里面的资源,二是释放内存。2、数组类型的空间申请和释放string*strs=newstring[10];//new操作符会对每一个string对象都调用一次...

2019-03-10 19:45:16

使用mmap遇到总线错误bus error

先简单描绘一下错误发生的场景:#defineMMAP_BUFF_SIZE4096structMessage{intlen;chardata[1024];};intfd=open("./test",O_RDWR|O_CREAT);lseek(fd,MMAP_BUFF_SIZE,SEEK_SET);Message*m...

2019-03-07 14:21:35

哈夫曼编码

哈夫曼树哈夫曼树就是一棵带权二叉树、它的WPL是最小的、也就是从根节点到每一个节点的路径长度(经过的边数)与权值乘积的总和是最小的、就称为哈夫曼树。哈夫曼编码把各个字符在整个串中出现的频率作为它的权重、通过使用0、1表示来缩短整个串的长度、可用于无损压缩。完成哈夫曼编码首先要先建立哈夫曼树、根据树中节点的路径、计算出对应节点的编码。下面我写了一个类其中就包含了建立哈夫曼树和完成...

2019-01-23 21:22:25

智能指针shared_ptr

说明:在使用c++语言编程时、为了防止忘记对申请的空间进行释放、我们通常使用智能指针来管理对象。智能指针有很多种、它们适用于不同的场合。auto_ptr:只允许唯一的一个auto_ptr对象管理一个资源、在拷贝时会自动将原auto_ptr指向置空。unique_ptr:同一时刻只允许一个unique_ptr对象指向指定资源、不允许拷贝、通过release()释放所有权、move移动所有...

2019-01-23 19:17:33

队列转栈

队列转栈队列转栈就是使用两个队列、相互不断地push、pop完成stack的功能直接看代码:要通过使用队列提供的操作接口来完成栈的功能、不能直接操作指针。#ifndefQUEUE_TO_STACK_H#defineQUEUE_TO_STACK_H#include<cstdio>#include<string>usingnamespacest...

2019-01-22 16:09:03

栈转队列

栈转队列栈转队列就是利用两个栈相互push、pop操作完成队列的功能。直接看代码:#ifndef_STACK_TO_QUEUE_H#define_STACK_TO_QUEUE_H#include<string>#include<iostream>#include<stack>#include<cstdio>#i...

2019-01-22 15:12:01

遇到的错误以及一些配置、做个记录

Vs2012重定义的错误2018-12-5今天我遇到了一个链接期错误“重定义”、以前也遇到过、但是以前是“真的重定义”、有重复的变量或者是重定义的函数、但是这次不一样、听我讲清整个事件的全过程:地点:一个头文件中、暂时命名为“app.h”,更细致一些是在一个命名空间中如下:namespacetest{namespaceAPP{boos...

2018-12-05 19:56:30

Effective c++ 读书总结 11-15

条款十一:在operator=中处理“自我赋值”1、自我赋值的发生1、clssTest;Testt;t=t;//有点傻2、arr[i]=arr[j];//不容易察觉、当i==j时自我赋值3、*p1=*p2;//当p1,p2指向同一个地址时自我赋值2、几种解决方案解决自我赋值时、在operator=中需要同时考虑自...

2018-11-06 09:23:29

开链式哈希表

简单说明hashtable适用于需要频繁插入、删除、查找的场合、在这些场合中hashtable都可以常数平均时间完成、然而之所以hashtable的效率这么高、是因为在以上这些操作时都是通过hashfunction直接定位元素在表中的位置然后直接操作。不可避免的有一些部分性质或全部性质相同的元素被定位到同一个位置上、这时新的问题产生了:解决冲突。实际上解决方法有很多:像线性探测、二次探测、开...

2018-11-04 20:06:46

优先队列实现

简单说明优先队列可以根据key值的大小将元素进行排序、先被pop的通常是优先级最高的。优先队列的内部实现其实是利用了堆的数据结构、binaryheap是一种完全二叉树、以大堆为例、每棵树的根节点的key值一定大于其子孙节点的key值、完全二叉树处了最底层的叶子节点外、其他位置都是填满的。这样我们可以利用数组来存储所有节点。若将数组从下标1开始存储元素、那么下标为i的节点的左孩子节...

2018-10-31 17:02:16

循环队列

在开发时常常需要使用循环队列、看到python中的Queue线程安全的队列、自己也想实现一个。没什么好说的、代码:#pragmaonce#include<Windows.h>template<classT>classCMyCirQueue{private: T* const head; size_t size; size_t...

2018-10-29 10:38:16

STL内存池讲解

简单说下:设计内存池的目的主要是为了解决在一些特殊的场合(比如:网络编程时接受数据包)频繁的创建和销毁、造成的大量的内存碎片和降低效率。在STL的内存池中可以看到、它的实现是利用了一个自由链表数组、Obj**free_lists;数组中每个元素都是一个自由链表的头指针、它指向一个由多个内存块连成的链表。另外、每个链表中所包含的内存块的大小是固定的、STL中是从8开始到128byte结束、块与...

2018-10-26 16:37:57

Effective c++ 读书总结 6 - 10

条款六:若不想使用编译器自动生成的函数、就该明确拒绝当一个类不需要自动生成的函数(构造、拷贝构造、拷贝运算符、析构)时、有以下两种方式解决:1.主动将函数声明为private2.继承一个有限制的base类:derived类自动生成的函数会企图调用base中对应的函数、这时就会编译出错。条款七:为多态基类声明virtual析构函数1.没声明virtual析构函数导致的内存泄漏...

2018-10-16 21:55:30

红黑树插入删除操作

红黑树有以下的性质:性质1.节点是红色或黑色。性质2.根节点是黑色。性质3每个叶节点(NIL节点,空节点)是黑色的。性质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。红黑树是二叉平衡树的一种、STL中的map、set、xxxmap、xxxset都是使用红黑...

2018-10-11 19:23:55
奖章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。