一知半解

指针和引用的区别 引用可以说是别名，指针有自己的存储空间，里面存储的是所指对象的地址 引用必须初始化，指针不必须初始化 引用初始化后不能更改引用的对象，指针初始化后可以更改指向的对象 两者在汇编层面没有区别 使用sizeof运算符看指针是4字节（32位机器）或8字节（64位机器），而用sizeof运算符看引用则取决于被引用对象的大小 指针可以进行自增或自减操作，可以访问原对象相邻存储空间的内容，引用只能固定引用 返回动态内存分配的对象或内存，必须用指针，用引用有可能内存泄露 从面向对象的角度，引用不是对象，指针是对象 数组和指针的联系、区别 指针是单个空间，存储的是所指对象的地址；数组可以有若干单位的空间，存储对象本身；可以有指向数组的指针，也可以有每个单元都是指针的数组 指针间接访问对象，得先解引用，指针可以直接访问 当指针指向数组时，可以用自增自减在数组元素上移动，但若要访问还是需要解引用 当数组作为函数参数传入时，会自动变化为指针，指向数组首位 不能对数组名直接复制，但可以对指针直接复制 用运算符sizeof可以得到数组字节数（数组大小），但只能得到指针类型本身的字节数 内置的 ...

Linux文件系统这篇文章讲文件系统比较通俗形象，由浅入深讲述了inode与block的概念，直接索引与多级索引寻址能力，为什么ext2文件系统最大单文件大小是4T，稀疏文件的概念，还不错：深度剖析 Linux cp 命令的秘密 基础Linux 文件系统会为每个文件分配两个数据结构：索引节点（index node）和目录项（directory entry），它们主要用来记录文件的元信息和目录层次结构。 索引节点(inode)：用来记录文件的元信息，比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识，它们之间一一对应，也同样都会被存储在硬盘中，所以索引节点同样占用磁盘空间。 目录项(dentry)：用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存。 目录与目录项： 目录也是文件，也是用索引节点唯一标识，和普通文件不同的是，普通文件在磁盘里面保存的是文件数据，而目录文件在磁盘里面保存子目 ...

虚拟内存虚拟内存的优势 提供缓存，加速运行 扩大地址空间，通过内存交换 每个进程都有自己的虚拟地址空间，互不影响，也不需要关心物理地址 分段（一般不单独使用） 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。 虚拟地址是通过段表与物理地址进行映射的 缺点： 第一个就是内存碎片的问题。 第二个就是内存交换的效率低的问题。 对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。所以内存交换的效率也很低 分页（推荐）分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换的空间太大的问题。要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是内存分页（Paging）。 每个进程拥有自 ...

二叉树有三种遍历方式：前序、中序、后序，用递归的方法来实现这三种遍历方式非常简单，用非递归的方式来实现就有些细节需要注意了 二叉树的前序遍历非递归实现 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。 即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下： 对于任一结点P： 1)访问结点P，并将结点P入栈; 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P; 3)直到P为NULL并且栈为空，则遍历结束。 123456789101112131415161718192021222324vector<int> preorderTraversal(TreeNode *root){ if (root == nullptr) return vector<int>(); vector<int ...

C++11之前，对代码有点追求的程序员，如果事先知道vector的大小，会预先reserve出确定的空间，代码如下： 123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <vector>#include <string>using namespace std;class Student{ public: Student() = default; Student(string name): name_(name) { cout << "ctor called" << endl; } Student(const Student& student): name_(student.name_) { cout << "copy ctor called" << endl;
...

c++11线程std::thread thread 的构造函数的第一个参数是函数(对象)，后面跟的是这个函数所需的参数。 thread 要求在析构之前要么 join(阻塞直到线程退出)，要么 detach(放弃对线程的管理)，否则程序会异常退出。 只有joinable(已经join的、已经detach的或者空的线程对象都不满足joinable)的thread才可以对其调用 join 成员函数，否则会引发异常 c++11还提供了获取线程id，或者系统cpu个数，获取thread native_handle，使得线程休眠等功能 下面的代码执行如下流程： 传递参数，起两个线程 两个线程分别休眠100毫秒 使用互斥量(mutex)锁定cout，然后输出一行信息 主线程等待这两个线程退出后程序结束 用lambda匿名函数 123456789101112131415161718192021222324252627282930313233#include <chrono>#include <iostream>#include <mutex>#include ...

Trie树在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串，属于多模式串匹配算法 根节点不包含字符，除根节点意外每个节点只包含一个字符。 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符串不相同。 限制： 字符串的字符集不能太大，否则空间消耗大 字符串的前缀要尽量重合，否则空间消耗大 使用场景：Trie树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。比如搜索引擎的搜索关键词提示 1、自动补全（单词自动补全）2、拼写检查（检查单词是否拼写正确）3、IP路由（最长前缀匹配）4、九宫格打字预测（根据前缀预测单词） 12345678910111213141516171819202122232425262728293031323334class Trie {public: Trie() {} void insert(string word) { auto ro ...

索引B树与B+树https://mp.weixin.qq.com/s/y3vDkEQfR5Pv1-rcWRZ7nQ 不想看文章的可以看视频，说的很浅显易懂：深入剖析Mysql优化底层核心技术 一个B+树需要说明是m阶的，其特点如下 每个节点的子节点的个数不能超过m，也不能小于m/2; 根节点的子节点个数可以不超过m/2，这是一个例外; m叉树只存储索引，并不真正存储数据，这个有点类似跳表; 通过链表将叶子节点串联在一起，这样可以方便按区间查找，为了升序和降序，一般是双向链表 B+树作为数据库索引，主要是为了减少磁盘IO次数，根据著名的局部性原理，每次可预读很多附近的记录 B树也就是B-树（不是减号，是连接符），B树与B+树的差别如下 B+树的中间节点关键字只是起到索引的作用，并不存储数据本身 B+树的数据都存储在叶子节点上，B树的数据存储在每个节点上，可能会增加B树的层数，从而增大搜索时间，所以对于同样数量的记录，B+树更加“矮胖”，磁盘IO更少 B+树支持区间访问，底层叶子节点会按大小顺序建立双向链表 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中 ...

不考虑windows的C++，首先看看Linux的虚拟地址空间概念 Linux虚拟地址空间Linux 使用虚拟地址空间，大大增加了进程的寻址空间，由高地址到低地址分别为： 内核虚拟空间（内核态）：用户代码不可见的内存区域，由内核管理(页表就存放在内核虚拟空间)。 栈：用于维护函数调用的上下文空间，堆的末端由break指针标识，当堆管理器需要更多内存时，可通过系统调用brk()和sbrk()来移动break指针以扩张堆，一般由系统自动调用。 内存映射区域（mmap）：内核将硬盘文件的内容直接映射到内存，一般是mmap系统调用所分配的，当malloc超过128KB时，不在堆上分配内存，而在内存映射区分配内存，既可以用于装载动态库，也可以用于匿名内存映射，没有指定文件，所以可以用来存放数据 堆：就是平时所说的动态内存， malloc/new 大部分都来源于此。其中堆顶的位置可通过函数brk和sbrk进行动态调整。 BSS段（.bss）：未初始化的全局变量或者静态局部变量 数据段（.data）：已初始化的全局变量或静态局部变量 代码段（.text）：保存代码（CPU执行的机器码） ...

智能指针总体介绍智能指针是一个类似指针的类，提供了内存管理的功能，当指针不再被使用时，它指向的内存会自动被释放，这就比原生指针要好，原生指针有可能会因为忘记释放所申请的空间，而造成内存泄漏，而用智能指针就没这个顾虑。C++11支持shared_ptr, weak_ptr, unique_ptr，auto_ptr（被弃用）。这些智能指针位于<memory>中 auto_ptr采取所有权模式，可以被拷贝（构造or赋值）时，原auto_ptr指为nullptr，即auto_ptr被其他auto_ptr剥夺（转移），所以很容易引起内存泄露（粗心的程序员可能仍然会解引用原auto_ptr） unique_ptr是独占式拥有，解决了auto_ptr被剥夺的问题，unique_ptr禁止了拷贝（构造or赋值），保证同一时间内只有一个智能指针可以指向该对象，如果真的需要转移，可以使用借助move实现移动构造，原unique_ptr置为nullptr（但粗心的程序员可能仍然会解引用原来的unique_ptr） shared_ptr是共享，允许拷贝（构造or赋值），允许多个智能指针可以指向相 ...