现役程序员skykens的博客

Function 语意学概述: 这一章好难,有些地方作者语焉不详的,图示和内容有些出入不知道是不是错误. 主要内容是在object中的函数存放位置,虚继承及多重继承下vptr的存取方案,inline 函数的展开以及指向member function 的指针. member的各种调用方式C++的设计准则之一： nonstatic member function 至少必须和一般的nonmember function有相同的效率 对于调用 nostatic member function 而言,例如: 编译器会进行下面几步转化过程: 1.改写函数原型 //non-const Point3d Point3d::magnitude(Point3d *const this) //const Point3d Point3d::magnitude(const Point3d *const this) 2.将每一步对nonstatic data member的存取操作改为经由this指针来存取 3.将member function重新携程一个外部函数。函数名经过名称的特殊处理,使它在程序中独一无二 ...

Data语意学概述 ： 这部分主要内容是在将Class Object中数据成员在内存中的分布,深入的讲解了在多重继承、虚继承等情况下编译器对于Class模型的构建。同时也对成员对象的使用效率方面做了深入的研究分析. Class Object内存布局对于class X{}这样一个对象而言,sizeof(X)后获得的大小为1,它里面包含有一个隐藏的1byte大小，这样可以使得两个object可以在内存中配置独一无二的地址. class A：public X{}; class B: public X{}; class C: public A,public B {}; sizeof运行结果: class A：virtual public X{}; class B: virtual public X{}; class C: public A,public B {}; sizeof运行结果: 对比上述两种继承方式中在内存中的大小分布.首先第一种普通继承方式下仅仅是继承了基类中隐藏的byte. 而第二种虚继承中,A、B、C三者的大小受到三个因素的影响: 1、 语言本身所造成的额外负担(重点) 在编 ...

TCP TCP，控制传输协议，和UDP的差别很大，它充分实现了数据传输时的各种控制功能： 针对发送端发出的数据包的确认应答信号ACK 针对数据包丢失或者出现定时器超时的重传机制 针对数据包到达接收端主机顺序乱掉的顺序控制 针对高效传输数据包的滑动窗口控制 针对避免网络拥堵时候的流量控制 针对刚开始启动的时候避免一下子发送大量数据包而导致网络瘫痪的慢启动算法和拥塞控制。 言归正传：TCP通过序列号、检验和、确认应答信号、重发控制、连接管理、窗口控制、流量控制、拥塞控制实现可靠性。 TCP选项 MSS 选项 ：发送SYN的TCP一段使用本选项通告对端它的最大分解大小。 窗口规模选项 : 就是TCP连接任何一端能够通告对端的窗口大小 时间戳选项: 防止失而复现的分组可能造成的数据损坏 滑动窗口滑动窗口解决的是流量控制的的问题，就是如果接收端和发送端对数据包的处理速度不同，如何让双方达成一致。接收端的缓存传输数据给应用层，但这个过程不一定是即时的，如果发送速度太快，会出现接收端数据overflow，流量控制解决的是这个问题。 https://blog.csdn.net/wdscq1234/a ...

网络相关网络字节序考虑一个16位整数，它由两个字节组成。 内存中存储这两个字节有两种方法：一种是将低序字节存储在起始地址，称为小端字节序,另一种是将高序字节存储在起始地址，称为大端字节序。两种格式都有系统使用。 　　网络上传输的数据都是字节流,对于一个多字节数值,在进行网络传输的时候,先传递哪个字节?也就是说,当接收端收到第一个字节的时候,它将这个字节作为高位字节还是低位字节处理,是一个比较有意义的问题;　　UDP/TCP/IP协议规定:把接收到的第一个字节当作高位字节看待,这就要求发送端发送的第一个字节是高位字节;而在发送端发送数据时,发送的第一个字节是该数值在内存中的起始地址处对应的那个字节,也就是说,该数值在内存中的起始地址处对应的那个字节就是要发送的第一个高位字节(即:高位字节存放在低地址处);由此可见,多字节数值在发送之前,在内存中因该是以大端法存放的;　　所以说,网络字节序是大端字节序;　　在实际中，当在两个存储方式不同的主机上传输时，需要借助字节序转换函数。 在Unix网络编程中，需要用到下列这四个函数进行字节序的转换 include <netinet/in.h ...

鹅厂是cpp的主战场，而以cpp为背景的工程师大都对os，network这块要求特别高，不像是Java这种偏重业务层的语言，之前面试Java的公司侧重还是在数据结构、网络、框架、数据库和分布式。所以OS这块吃的亏比较大。面试分为以下几大块• C/C++• 网络• 操作系统• Linux系统• MongoDB• Redis• mysql• 算法• 设计模式• 分布式架构• 系统设计• 等等，未完待续 C/C++ const 多态 什么类不能被继承（这个题目非常经典，我当时答出了private但是他说不好，我就没想到final我以为那个是java的）网络 网络的字节序 网络知识 tcp三次握手 各种细节 timewait状态 tcp 与 udp 区别 概念 适用范围 TCP四次挥手讲一下过程，最后一次ack如果客户端没收到怎么办，为什么挥手不能只有三次，为什么time_wait。 对于socket编程，accept方法是干什么的，在三次握手中属于第几次，可以猜一下，为什么这么觉得。 tcp怎么保证有序传输的，讲下tcp的快速重传和拥塞机制，知不知道time_wait状态，这个状态出现在什 ...

C++对象模型的演变简单对象模型一个object是一系列的slots,每一个slot指向一个members.Members按其声明顺序,各被指定一个slot 表格驱动对象模型将类的成员和函数抽出来分为两个表,class object中存放这指向两个表的指针 C++对象模型 非静态成员存放在class object 中,函数和静态成员存放在class object 之外 virtual function 由class object中安插的vptr(指向vtbl——虚函数表)支持.每一个class 的构造、拷贝和析构都自动完成对vptr的设置、重置. struct 和 class 的差异在C++ 领域中两者在用法上没有太大区别,但是既然已经迁移到了C++ 领域,使用面向对象的方式思考就最好放弃使用struct 转而使用class 在思想层面更有觉悟一点…23333 但是struct 在C++ 中有一个合理用途,当你要传递”一个复杂的class object”的全部或部分到某个C函数去时,struct声明可以将数据封装起来，并保证用于与C兼容的空间布局.然而这项保证只有在组合的情况下才存 ...

wiki定义 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。 对不同的关键字可能得到同一散列地址，即k1 != k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。 具有相同函数值的关键字对该散列函数来说称做同义词。 综上所述，根据散列函数f(k)和处理冲突的方法将 ...

红黑树定义: 摘自wiki红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。 红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了O(logn)的时间之外，红黑树的持久版本对每次插入或删除需要O(logn)的空间。 红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。 红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删 ...

定义 在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 AVL和二叉搜索树区别当初始化的数组为有序时，二叉搜索树会退化为链表,其时间复杂度为O(n),违背了树这个结构本身设计的初衷. AVL树在每次添加节点的时候都会平衡因子检查当前节点是否平衡(左右子树的高度差是否小于1 ...

二叉搜索树wiki定义二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点。 复杂度 算法 平均 最差 空间 O(n) O(n) 搜索 O(log n) O(n) 插入 O(log n) O(n) 删除 O(log n) O(n) 应用二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透过建构一棵二叉查找树变成一个有序序列，建构树的过 ...

Trie 字典树/前缀树 wiki 定义在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 和并查集的区别并查集主要解决的问题是网络连接问题,集合的包含合并问题.而Trie主要通过空间换取时间,将需要查询的字符串拆解为一个个字符存储在节点中,实现每次查询是否包含字符串只需要付出O(K)(K 为字符串的长度) 的时间复杂度. 两者实际都是一种为了解决特定问题的多路树结构. 笔记内容 代码示例 # include <iostream> # include <map> # include <string> class Node{ private: bool isWord; map<char,Node*> ...