小白的Coding之旅

原创 STL之空间配置器

为什么需要空间配置器？通过new申请的空间，虽然代码可以正常运行，但是有以下不足之处：空间申请与释放需要用户自己管理，容易造成内存泄漏频繁向系统申请小块内存块，容易造成内存碎片频繁向系统申请小块内存，影响程序运行效率直接使用malloc与new进行申请，每块空间前有额外空间浪费申请空间失败怎么应对代码结构比较混乱，代码复用率不高未考虑线程安全问题SGI-STL空间配置器实现原...

原创 如何理解C++中的引用折叠？

template<class T>void test(T&& t) { cout << "test(T&&)" << endl;}int main(){ int a = 10; test(a); test(10); return 0;}模板函数的参数是右值引用。为什么还可以接收左值呢？以上这种未定的引用...

原创 C++11新特性总结

1.列表初始化1.1 内置类型的列表初始化 // 内置类型变量 int x1 = { 10 }; int x2{ 10 }; int x3 = 1 + 2; int x4 = { 1 + 2 }; int x5{ 1 + 2 }; // 数组 int arr1[5]{ 1,2,3,4,5 }; int arr2[]{ 1,2,3,4,5 }; // 动态数组，在C++98中...

原创 C++模拟实现红黑树，封装map和set

红黑树红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包...

原创 C++模拟实现位图&布隆过滤器以及海量数据处理的方式

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。如何扩展BloomFilter使得它支持删除元素的操作1.使用位图。先将一个文件中的query先映射到位图中，然后用另外一个文件中的query在位图中查找。如果query转化为整形数据对应的比特位是1，说明该条query在另外一个文件中也出现了，即就是交集，0说明该条query在另一个...

原创 C++模拟实现unordered_map和unordered_set

unordered系列unordered_map是存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。在内部unordered_map将相同哈希值的键值对放在相同的桶中。键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。unordered_map容器通过key访问单个元素要比map快，map...

原创 范式Huffman树在文件压缩项目中的应用

范式huffman树范式huffman树是在huffman树的基础之上，进行了一些强制性的约定，即：对于同一层节点中，所有的叶子节点都调整到左边，然后，对于同一层的叶子节点按照符号顺序从小到大调整 ，最后按照左0右1的方式分配编码。只要知道一个符号的编码位长就可以知道它在范式树上的位置。即：码表中只要保存每个符号的编码长度(即节点在树中的高度)即可，其远远要比符号频度小相同位长的编码...

转载 银行家算法(一看就懂)

原创 基于LZ77算法和Huffman编码的文件压缩项目

原理：由给定的n个权值{ w1, w2, w3, … , wn}构造n棵只有根节点的二叉树森林F={T1, T2 , T3, … ,Tn},每棵二叉树Ti只有一个带权值wi的根节点，左右孩子均为空。重复以下步骤，直到F中只剩下一棵树为止在F中选取两棵根节点权值最小的二叉树，作为左右子树构造一棵新的二叉树,新二叉树根节点的权值为其左右子树根节点的权值之和在F中删除这两棵二叉树把新的二叉...

原创 C++模拟实现AVL树

AVL树的概念一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)AVL树的旋转如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：新节点插入较高左子树的左侧—左左：右单旋新节点插入较高...

原创 计算机网络 - 理解网络层，数据链路层

网络层IP协议概念：主机: 配有IP地址, 但是不进行路由控制的设备;路由器: 即配有IP地址, 又能进行路由控制;节点: 主机和路由器的统称；协议头格式4位版本号 :指定P协议的版本，对于PV4来说就是44位头部长度:IP头部的长度是多少个32bit，也就是 length*4的字节数，4bit表示最大的数字是15,因此P头部最大长度是60字节8位服务类型 :3位优先权...

原创 mysql数据库知识总结-02

表的增删改查现有有以下学生表：插入是否更新可能由于主键或者唯一键对应的值已经存在而导致插入失败可以选择性的进行同步更新操作insert into students(id, sn, name) values (100,10010,'唐大师') on duplicate key update sn = 10010, name = '唐大师';如果插入冲突，就会按照updat...

原创 mysql数据库知识总结-01

连接服务器在命令行下输入：mysql -h 127.0.0.1 -P 3306 -u root -p注意：如果没有写 -h 127.0.0.1 默认是连接本地如果没有写 -P 3306 默认是连接3306端口号创建数据库语法：create database [IF NOT EXISTS] db_name [DEFAULT] CHARACTER SET charset_nam...

原创 I/O多路转接之poll（实现poll版本的TCP服务器）

I/O多路转接之pollpoll函数接口#include <poll.h>int poll(struct pollfd *fds, nfds_t nfds, int timeout);// pollfd结构struct pollfd { int fd; /* file descriptor */ short events; /* requested events */ ...

原创 I/O多路转接之epoll（实现epoll版本的TCP服务器）

I/O多路转接之pollpoll函数接口#include <poll.h>int poll(struct pollfd *fds, nfds_t nfds, int timeout);// pollfd结构struct pollfd { int fd; /* file descriptor */ short events; /* requested events */ ...

原创 I/O多路转接之select（实现select版本的TCP服务器）

初识select系统提供select函数来实现多路复用输入/输出模型.select系统调用是用来让我们的程序监视多个文件描述符的状态变化的;程序会停在select这里等待，直到被监视的文件描述符有一个或多个发生了状态改变;select函数原型select的函数原型如下: #include <sys/select.h>int select(int nfds, fd_set...

原创 一个端口号真的只能被一个进程bind吗？

不经意间我看见了这个问题，刚好这学期我就在学谢仁希的计算机网络这门课，书上说一个端口号只能被一个进程绑定的。网上关于这个问题的详细解释也是寥寥无几。直到我看见了有位博主说绑定端口号后fork会导致父子进程绑定了同一个端口，博主也是一句话带过，也没有具体解释，下来我也是问了许多老师，不断的通过代码来验证自己的想法和观点。以下测试均在Linux环境下。首先我们需要一个简单的服务器和客户端程...

原创 C++模拟实现二叉搜索树

BSTree.hpp#pragma once#include<iostream>#include<stack>using namespace std;template<class T>struct BSTreeNode{ BSTreeNode(const T& data = T()) : _pLeft(nullptr) , _p...

原创 计算机网络 - HTTP协议

HTTP协议URL我们俗称的网址其实就是“URL”urlencode和urldecode例如 / ? : 等这样的字符, 已经被url当做特殊意义理解了. 因此这些字符不能随意出现. 某个参数中需要带有这些特殊字符, 就必须先对特殊字符进行转义.转义的规则如下: 将需要转码的字符转为16进制，然后从右到左，取4位(不足4位直接处理)，每2位做一位，前面加上%，编码成%XY格式u...

原创 计算机网络 - 理解TCP/IP，UDP协议

应用层HTTP协议URL我们俗称的网址其实就是“URL”urlencode和urldecode例如 / ? : 等这样的字符, 已经被url当做特殊意义理解了. 因此这些字符不能随意出现. 某个参数中需要带有这些特殊字符, 就必须先对特殊字符进行转义.转义的规则如下: 将需要转码的字符转为16进制，然后从右到左，取4位(不足4位直接处理)，每2位做一位，前面加上%，编码成%XY...

原创 C++实现一个线程安全版本的shared_ptr（以及如何设置删除器）

#include<iostream>#include<mutex>#include<thread>using namespace std;namespace LMJian { //设置删除器 template<class T> class DFDef { public: void operator()(T*& _ptr)...

原创 Linux网络编程套接字知识总结

IP地址与端口号IP地址能够标识网络上的某一台主机。端口号是一个2字节16位的整数。端口号用来标识一个进程, 告诉操作系统, 当前的这个数据要交给哪一个进程来处理。IP地址 + 端口号能够标识网络上的某一台主机的某一个进程。一个端口号只能被一个进程占用。端口号与进程ID的区别两者都可以唯一的表示一个进程。但是，一个进程的ID，当该进程结束时，此进程ID就会被释放，下次运行其他...

原创 TCP协议通讯流程（三次握手与四次挥手）

服务器初始化调用socket，创建文件描述符。调用bind，将当前的文件描述符和ip/port绑定在一起，如果这个端口已经被其他进程占用了，就会bind失败。调用listen，声明当前这个文件描述符作为一个服务器的文件描述符，为后面的accept做好准备。调用accecpt，并阻塞，等待客户端连接过来。建立连接的过程调用socket，创建文件描述符。调用connect，向服务器...

原创 实现一个简单的TCP网络程序（多进程，多线程，线程池版本的服务器）

完整代码请前往我的GitHub仓库—>戳我，戳我tcp_process_server.hpp#pragma once#include"tcp_socket.hpp"#include<signal.h>typedef void (*Handler)(const string& buf,string& ret);class TcpProcessServ...

原创 实现一个简单的TCP网络程序（客户端输入字符大小写互转）

github地址：—点我—封装 TCP sockettcp_socket.hpp#pragma once#include<iostream>#include<sys/types.h>#include<sys/socket.h>#include<unistd.h>#include<arpa/inet.h>#include&...

原创 计算机网络基础知识（浅谈网络传输基本流程）

计算机网络背景网络发展独立模式：计算机之间相互独立网络互联：多台计算机连接在一起，完成数据共享局域网LAN：计算机数量更多了，通过交换机和路由器连接在一起广域网WAN：将远隔千里的计算机都连在一起所谓 “局域网” 和 “广域网” 只是一个相对的概念. 比如, 我们国家的广域网, 也可以看做一个比较大的局域网.什么是协议？“协议”是一种约定。计算机之间的传输媒介是光信号和...

原创 C++菱形继承和菱形虚拟继承关系的虚函数表详解

菱形继承中的虚函数表class A {public: virtual void func1() { cout << "A::func1" << endl; }private: int _a;};class B :public A{public: virtual void func1() { cout << "B::func1" <&lt...

原创 C++多态原理，单继承和多继承关系的虚函数表详解

多态的原理虚函数表在vs编译器中，可以看出来a对象除了有一个_a成员，还多一个__vfptr放在对象的前面，对象中的这个指针叫做虚函数表指针。一个含有虚函数的类中都至少都有一个虚函数表指针，因为虚函数的地址要被放到虚函数表中， 虚函数表也简称虚表。派生类虚表构建规则将基类虚表中的内容拷贝一份放到子类虚表中。如果派生类重写了基类某个虚函数，用派生类自己的虚函数替换原先基类虚函数的入口地...

转载 C++如何处理内联虚函数

当一个函数是内联和虚函数时，会发生代码替换或使用虚表调用吗？ 为了弄清楚内联和虚函数，让我们将它们分开来考虑。通常，一个内联函数是被展开的。class CFoo {private: int val;public: int GetVal() { return val; } int SetVal(int v) { return val=v; }};这里，如果使...

原创 C++单例模式之饿汉模式和懒汉模式

饿汉实现方式和懒汉实现方式懒汉方式最核心的思想是 “延时加载”. 从而能够优化服务器的启动速度.饿汉方式实现单例模式template <typename T> class Singleton { static T data; public: static T* GetInstance() { return &data; } };只要通过 Sin...

原创 Linux线程知识点总结

主要内容了解线程的概念，理解线程与进程的区别与联系。线程控制，线程创建，线程终止，线程等待。线程分离与线程安全概念。线程同步。互斥量，条件变量，posix信号量，以及读写锁。理解基于读写锁的读者写者问题。线程概念在一个程序里的一个执行路线就叫做线程（thread）。更准确的定义是：线程是“一个进程内部的控制序列”一切进程至少都有一个执行线程线程在进程内部运行，本质是在进程...

原创 Linux中实现一个线程池（条件变量&POSIX信号量版本）

阻塞队列#pragma once#include<iostream>#include<semaphore.h>#include<vector>using namespace std;template<class T>class BlockingQueue{ public: BlockingQueue(int maxsi...

原创 C++重载，重写，重定义之间的区别以及多态的概念

重载重载是指在同一个类或同一个命名空间中存在多个函数，它们的函数名相同，而函数参数不同。与返回值无关。返回值类型不同。函数名，参数列表相同不能构成重载。虚函数也是可以重载的。重写（覆盖）重写是指在子类中实现一个虚函数，该虚函数与其父类中的一个虚函数拥有同样的函数名和函数参数，包括返回值都必须相同！！！（协变除外）。析构函数可以是虚函数，即析构函数可以重写。但是，构造函数不能是虚函...

原创 二叉树前序中序后序遍历（非递归）

二叉树前序遍历打印当前节点，将该节点入栈。如果该节点有左子树，访问左子树，重复此步骤，直到没有左子树。访问栈顶元素的右孩子，并出栈。重复1的操作。当栈为空且指针为空时，遍历结束。class Solution {public: vector<int> preorderTraversal(TreeNode* root) { vector<int&...

原创 Linux信号的阻塞与信号的捕捉

#include<stdio.h>#include<unistd.h>#include<stdlib.h>#include<errno.h>#include<signal.h>void sigcb(int sig){ printf("recv a signal: %d\n",sig); //sigaction(sig...

原创 Linux进程信号

主要内容Linux信号的基本概念信号产生的一般方式信号递达和阻塞的概念，原理信号捕捉的一般方式可重入函数的概念竞态条件的情景和处理方式SIGCHLD信号， 重新编写信号处理函数的一般处理机制什么是信号？用户输入命令,在XShell下启动一个前台进程。用户按下Ctrl-C ,这个键盘输入产生一个硬件中断，被OS获取，解释成信号，发送给目标前台进程，前台进程因为收到信号，进而...

原创 Linux进程间通信

主要内容：进程间通信介绍匿名管道pipe命名管道共享内存消息队列和信号量的了解进程间通信介绍进程间通信目的数据传输：一个进程需要将它的数据发送给另一个进程。资源共享：多个进程之间共享同样的资源。通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）。进程控制：有些进程希望完全控制另一个进程的执行（如Debug进程），此...

原创 Linux文件系统知识点总结

理解文件系统我们在使用stat命令查看文件信息时可以看到如下信息：[root@localhost linux]# stat test.c File: "test.c" Size: 654 Blocks: 8 IO Block: 4096 普通文件Device: 802h/2050d Inode: 263715 Links: 1Access: (0644/-rw-r--r--) Uid:...

原创 Linux基础IO知识点总结

C语言中打开文件的方式文件使用方式含义如果指定文件不存在“r”(只读）为了输入数据，打开一个已经存在的文本文件出错“w”(只写）为了输出数据，打开一个文本文件建立一个新的文件“a”(追加）向文本文件尾添加数据出错“rb”(只读）为了输入数据，打开一个二进制文件出错“wb”(只写）为了输出数据，打开一个二进制文件建立一个新文件...

原创 Linux中实现一个shell程序

#include<stdio.h> #include<unistd.h>#include<string.h>#include<fcntl.h>#include<stdlib.h> char command[1024]={0};...