Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 从这开始我们进入《STL源码分析》的学习 STL分为6大组件: 空间配置器、容器、迭代器、算法、仿函数、配接器 空间配置器 STL的空间适配器事STL的基础，我们不能靠操作系统来为我们管理内存，那样的代价太大了，这不划算，作为一个c/c++开发人员，我们要完全控制我们程序的一切。 allocator 这是他的英文名字，我们的allocator定义了四个操作 alloc::allocate() 内存配置 alloc::dellocate() 内存释放 alloc::construct() 构造对象 alloc::destroy() 析构对象 type_traits<T> 一个模版元技术，他是一个类,能够萃取类型的相关信息，模版元详见C++笔记中的Boost源码分析 destroy 对于基本数据类型，我们啥都不用干，对于用户定义的数据类型，我们显示调用析构函数即可，这 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 网页 当我们输入网址以后，会建立http(https算了)连接，我们给服务器请求，服务器给我们回应，我们不断发送request,服务器不断返回response,请求又很多种。 大量的response 我们要把这些数据存起来，数据库啊啥的都行。 简单的爬虫1234import requestsres = requests.get("http://www.baidu.com")res.encoding = 'utf-8'print(res.text) 上面的代码能够得到百度网站 分析html12345678import requests#import bs4from bs4 import BeautifulSoupres = requests.get("http://www.baidu.com")res.encoding = ' ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 学习 spring 是一个轻量级框架 他最重要的地方时AOP和IOC，他的目的是降低耦合度，减少代码量 AOP 面向切面编程， IOC 控制反转，即将对象的创建交给spring,配置文件+注解 耦合问题 比方说我们要在B类中使用A类，就会在B类中A a=new A();然后这样就导致了B依赖A 工厂模式解决耦合 用工厂来控制A类，在B中就能 A a=factory.getA(); 这又导致了B和工厂耦合。 ioc方案 解析xml配置文件中的类，在工厂类中利用反射创建类的对象，这就降低了类的耦合度，我们想要换类的时候，只要将xml中的类名称改掉就可以了。 一站式框架springMVC+ioc+jdbcTemplate

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial hadoop hadoop = common+hdfs+mapreduce+yarn common 工具、rpc通信 hdfs 分布式文件系统，一个文件分成多个128Mb的文件，存储在多个节点，为了保证分区容错性，存有备份，默认为3。主从架构。 namenode用来记录各个文件的block的编号、各个block的位置、抽象目录树 处理读写请求 可以有多个namenode secondarynamenode 用来备份namenode,当namenode宕机的时候，帮助namenode恢复 datanode 用来储存数据 副本机制 如果一个datanode挂了，就再开一个datanode，然后吧挂了的数据通过备份推出来存进去，如果之前那个挂了的又活了，则选择一个节点删掉。副本过多将导致维护成本提高 优点 可构建在廉价机器上 高容错性 : 自动恢复 缺点 不支持数据修改(尽管支持改名 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Boost 与c++ Boost是基于C++标准的现代库，他的源码按照Boost Software License 来发布，允许任何人自由使用、修改和分发。 Boost有哪些功能？ Boost强大到拥有超过90个库，但我们暂时只学习其中一部分 Any boost::any是一个数据类型，他可以存放任意的类型，例如说一个类型为boost::any的变量可以先存放一个int类型的值，然后替换为一个std::string的类型字符串。 Array 好像是一个数组容器，和std::vector应该差别不大。 and more …这个系列的博客来干嘛？ 这个系列的博客用来介绍Boost提供的接口，不对Boost进行源码分析，关于Boost的源码，预计会在Boost源码分析笔记系列的博客中。 Boost.Any Any在C++17被编入STLC++是强类型语言，没有办法向Python那样把一个int ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial remove_cv remove_cv 这个模版类能够帮我们去掉类型的const，他的实现很简单，即使用模版元技术： 1234template <class T> struct remove_cv{ typedef T type; };template <class T> struct remove_cv<T const>{ typedef T type; };template <class T> struct remove_cv<T volatile>{ typedef T type; };template <class T> struct remove_cv<T const volatile>{ typedef T type ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Y快速前缀树 继X快速前缀树以后，Dan Willard又提出了X快速前缀树的改进版本 改进X快速前缀树 我们还是继续考虑n个小于M的整数(n<M)，我们按照大小，从小到大分组,每组的元素的个数在区间$[\frac{lgM}{4},2lgM]$上,对每组构建一颗普通平衡树，这样我们一共会得到$\frac{n}{2lgM}$到$\frac{4n}{lgM}$颗树，我们在这些树中取一个随便的值r，r要在平衡树的最大和最小值之间,这样我们每棵树对应了一个r，把所有的r作为键,其对应的平衡树作为值放到X快速平衡树中，这就是Y快速平衡树。 Y快速前缀树的查找前驱后继 首先在上层X前缀树上查找前驱和后继，最终我们会定位到两个叶子节点，也就对应了两颗普通平衡树，我们在这两颗普通平衡树里面直接找前驱后继然后合并就结束了。总复杂度$lglg(\frac{n}{lgM})+2*lg(lgM)=lg ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial X快速前缀树 我以前就说过，当你的数据结构达到了一定的基础，就可以学习那些更加高级的数据结构了，往往那些更加高级的数据结构由基本数据结构组合而成。 先提出一个问题 现在要你维护一个多重集合，支持3种操作，1询问一个值(这个值不一定在集合中)的前驱和后继，2向集合中插入一个元素，3从集合中删掉一个元素，1操作$10^6$次，2操作$10^5$次，3操作$10^5$,要求你在1S内完成回答。保证集合元素都小于M=$10^6$ 普通平衡树？ 我们考虑到上面三种操作都是普通平衡树常见的操作，很多人可能就直接拿起他自己的平衡树上了。很遗憾，大概率是无法通过的。因为操作次数太多了。 观察，思考 我们的操作需要的是大量的查询，大量、大量，你个普通平衡树怎么操作的过来？ 新的平衡树 现在我们提出一个新的平衡树，这个平衡树非常厉害，他支持$O(lgM)$的时间来删除和插入，支持$O(lglgM)$ ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ternary search tree字典树的缺点 不难想到，对于那些字符集特别大的字典树来说，他们的空间消耗特别大，因为每个节点都要储存大量的指针，而这些指针往往又是空的。 将BST与trie结合起来 考虑这样一种树，每个节点有三个儿子，左右儿子表示自己的左右兄弟，向下的儿子表示真正的儿子。这样的树，将极大的提高了空间利用率。 偷个图来放着 这里插入了as,at,be,by,he…. 三叉搜索树的插入 考虑递归，假设我们插入到了某个节点，若下儿子与当前字符相等，则递归到下儿子并使用下一个字符来递归，如果当前字符小于下儿子，则递归到左儿子，保持当前字符不变，如果当前节点不存在了，则创建新节点，直接向下儿子走。 三叉搜索树的删除 我们还是用数字来记录终结节点的终结字符串有多少个，若找到待删除的节点以后，终止与此的只有一个字符串，则直接删掉，否则让终极节点的计数器减1，注意在回溯的时候，如果三个 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 基数树 基数树是一种更加节省空间的数据结构，他是字典树的升华， 字典树的缺陷 常常字典树会很深，而不胖，这会导致空间的浪费，因为里面的指针很多，往往我们发现，如下列字典树 稍等片刻！正在将字符数据转化为图形 12345graph LRstart((start))--a--> 1((1))1((1))--b-->2((2))2((2))--c-->3((end))2((2))--d-->3((end)) 用基数树改进字典树 我们可以通过压缩字符路径为字符串路径，即将长链压缩为一条边。 1234graph LRstart((start))--ab-->2((2))2((2))--c-->3((end))2((2))--d-->3((end)) 当然你甚至还能这样 123graph LRstart((start))--abc-->3((end))s ...