Spring有六大模块，测试、容器、面向切面编程、instrumentation、数据访问与集成、Web与远程调用。 - 测试: Test - 容器: Beans,Core,Context,Expression,ContextSupport - 面向切面编程: AOP,Aspects - instrumentation: instrument,instrumentTomcat - 数据访问与集成: JDBC,Transaction,ORM,OXM,Messaging,JMS - Web与远程调用: Web,WebServlet,WebPortlet,WebSocket 但是Spring远不止这些
Spring有三种配置方式，第一是通过XML配置，第二是通过JAVA配置，第三是隐式的bean返现机制和自动装配。建议优先使用三，而后是二，最后是一 ## 自动化装配bean 有两种方法，组件扫描和自动装配，
STL分为6大组件: 空间配置器、容器、迭代器、算法、仿函数、配接器
STL的空间适配器事STL的基础，我们不能靠操作系统来为我们管理内存，那样的代价太大了，这不划算，作为一个c/c++开发人员，我们要完全控制我们程序的一切。
这是他的英文名字，我们的allocator定义了四个操作
一个模版元技术，他是一个类,能够萃取类型的相关信息，模版元详见C++笔记中的Boost源码分析
对于基本数据类型，我们啥都不用干，对于用户定义的数据类型，我们显示调用析构函数即可，这个使用模版特化即可。
就是new，但是不用申请空间了，因为allocate已经干了
一级配置大空间(>128bytes)就是malloc和free，二级配置小空间，利用内存池。
直接new的，new失败以后调用out of memery的处理方式调用处理例程，让其释放内存，不断尝试,释放的时候直接free
维护16个链表，每个链表维护一种类型的内存，分别为8bytes、16bytes、24bytes、一直到128bytes。更加巧妙的地方是将维护的内存和链表的指针使用联合体组装。这就不浪费空间了。当需要配置内存的时候，向8字节对齐，然后再分配，当释放内存的时候，丢到链表里面就行了 当链表空了的时候，从内存池中取出20个新的内存块填充链表。 内存池是一个大块大内存，当内存池空了以后，申请更多的内存，保证每次都比上一次申请的多就行了，要是让我实现，我才不这样做，我要用计算机网络中的自适应rtt原理来做。
说白了就是个指针，但是他比指针更强大，更灵活。
graph TB
1((input)) --> 3((forward))
2((output)) --> 3((forward))
3((forward)) --> 4((bi))
4((bi)) --> 5((random))首先为了实现的容易，得设计iterator_category为迭代器自己的类型，value_type为迭代器维护的具体数据的类型，diference_type为两个迭代器之间的距离的类型，pointer为原生指针，reference为原生引用。
不讲了，太简单了
服了，居然就是指针，我一直以为他封装了一下，这也太懒了。
算了这都跳过算了，没啥意思，
用分段连续来制造整体连续的假象。 两个迭代器维护首尾，一个二维指针维护一个二维数组，感觉很low，每一行被称为一个缓冲区,但是列的话，他前后都预留了一些指针位置。 当我们随机访问的时候，就可以根据每一行的长度来选择正确的缓冲区了。
这个就厉害一些了，他包含了4个地方，当前指针、当前缓冲区首尾指针，中控器上面当前缓冲区的指针。
代码我感觉也一般般，我写也这样
居然是deque实现的，明明有更好的实现方法，再见，看都不想看
算法都是这样写的
vector实现的，
我还是不适合这个东西
这玩意就是红黑树啦，上一章的序列容器看的我难受死了，希望这个能爽一些
翻了好几页，都是红黑树，并没有让我感到很吃惊的代码
set就是直接红黑树，map就把用pair分别存kv，然后自己定一个仿函数，难怪map找到的都是pair
算了自己写过平衡树的都知道，和非multi没几行代码不一样。
下一章下一章。。。
分为质变算法和非质变算法，一个会改变操作对象，另一个不会。
这个强，accmulate(first,last,init),将[first,last)的值累加到init上
accmulate(first,last,init,binary op),将[first,last)从左到右二元操作(init,*)到init上
666666666，adjacent_difference(first,last,result)差分都来了[first,last)差分到[result,*)
6666666,自己定义的差分adjacent_difference(first,last,result,binary_op); 这个能自定定义减法，
注意可以result设为first
内积，inner_product(first1,last1,first2,init),加到init上然后返回。
参数在加上一个binary_op1和binary_op2,init=binary_op1(init,binary_op2(eme1,eme2))
太强了，佩服的五体投地，明天继续学,看java去
和前面的差分一样,partial_sum 为前缀和，partial_sum(first,last,result)为前缀和输出到result中
当然你也可以定义binary_op操作，加在最后面
快速幂算法了解一下，power(x,n)x的n次方，n为整数，要求满足乘法结合律。
power(x,n,op),这个同理
itoa(first,last,value);
while(first!=last) *first++=value++;
equal(first1,last1,first2)
判断[first1,last1) 和[first2,...)是否相同
同样支持二元仿函数。
fill(first,last,value)
把区间的值设为value
fill(first,n,value)
把first开始的n个元素设为value
iter_swap(a,b)
交换迭代器的内容，这里就有意思了，如何获取迭代器内容的类型呢？还记得之前讲迭代器的时候，在迭代器内部定义的
value_type吗？对！就是那个。
lexicographical_compare(first1,last1,first2,last2)
字典序比大小，需要支持小于号
这俩也支持仿函数
mismatch(first1,last1,first2)
用第一个去匹配第二个，你需要保证第二个不必第一个短，返回匹配尾部
支持仿函数==
就是很普通的交换，
特化了char*和wchar_t*为memmove，特化了T*和const T*，通过萃取，若指向的数据为基本数据类型则调用memmove，
否则再分为随机迭代器和非随机迭代器，随机迭代器使用last-first这个值来控制，非随机迭代器用if(last==frist)来控制。
和上面一样，但是为逆序拷贝
set_union(first1,last1,first2,last2,result)
就是遍历两个有序容器，然后赋值到result中，注意到它在碰到相同元素的时候两个迭代器都自增了，导致若第一个中有3个1，第二个中有5个1，则输出的时候只有5个1
同上
交集，得到3个1
代码越来越平庸了，这个是S1-S2，出现在S1中不出现在S2中
对称差，平庸的代码
找到第一个相等的相邻元素，允许自定义仿函数
对value出现对次数计数
count_if(first,last,op) 对op(*it)为真计数
越看越无聊了
找value出现的位置，这个函数应该挺有用的
find_if(first,last,op) 同上啦
这个函数没用，我为啥不用kmp算法
op(*i)
*i=op()
generate_n 同上
*result=op(*first)
*result=op(*first1,*first2)
保证有序，然后判断2是不是1的子序列，显然On
区间最大值
同上
归并排序的时候应该用得到吧
pred(*)为真在前，为假在后On
把value移到尾部 remove_copu(first,last,result,value),非质变算法
同上
看名字就知道怎么实现的
replace_copy,replace_if,replace_copy_if
秀得我头皮发麻，这个。。。。。。。
1 | while(true) |
随机迭代器的版本还好
1 | while(first<last) iter_swap(first++,--last); |
reverse_copy ，常见的代码
这个代码有点数学，大概率用不到，一般情况下我们写splay都用3次reverse来实现的，复杂度也不过On,他这个代码就一步到位了，使用了gcd，没啥意思，STL果然效率第一
子序列首次出现的位置，
好偏，算了，没啥用的代码
区间交换，swap的增强版
移除重复元素
unique_copy
不多说了，就是二分，
一直想不明白这个函数怎么实现的，今天来看看，既然是下一个排列，显然是需要找到一个刚好比现在这个大大排列，简单分析......6532,如果一个后缀都是递减的，显然这个后缀不能更大了，如果一个后缀都不能变得更大，就必须调整更前的，所以我们要找到这样的非降序....16532,把最后一个放到1的位置，其他的从小到大排列好就行了。也即swap(1,2),reverse(6531)
同理
洗牌算法，从first往last遍历，每次从最后面随机选一个放到当前位置即可。
partial_sort(first,middle,last) 保证[first,middle)有序且均小于[middle,last)直接对后面元素使用堆上浮，这样保证了小的元素均在[first,middle)中，然后使用sort_heap????? &ems; 为啥第一步不用线性时间选择，第二步不用快排？
大一就听说了这个的大名，现在来学习学习
__median(a,b,c) 返回中间那个值
这个大家都会写，就是按照枢轴，把小的放左边，大的放到右边
当只有很少很少的几个元素的时候，插入排序更快。
我们不必在快速排序中进行插入排序，但是可以提前推出，保证序列基本有序，然后再对整体使用插入排序
先快速排序到基本有序，然后插入排序
先排序右边，后左边，且将左边当作下一层，当迭代深度恶化的时候，即超过了lg(n)*2的时候，采取堆排序 枢轴的选择，首、尾、中间的中位数
这个就少了堆排序了，其他的和SGI一样
lower_bound和upper_bound的合体 比直接lower_bound+upper_bound应该快一些，大概这样，二分中值偏小，做缩左断点，偏大则缩右端点，若二分中值等于value，则对左边lower_bound,对右边upper_bound,然后就能直接返回了
将两个相邻的有序序列合并为有序序列，他在分析卡空间的做法，再见。。。不缺空间，
线性时间选择，三点中值，递归变迭代，长度很小以后直接插入排序，666666
借助inplace_merge直接完成了，
STL的算法还是很厉害的。
c++的一大特色，通过重载()来实现像函数一样的功能
1 | template<class Arg,class Result> |
看到上面那玩意没，你得继承它。
1 | template<class Arg1,class Arg2,class Result> |
你要为你的仿函数设置一个identity_element单位元，用于快速幂
本质上，配接器是一种设计模式，改变仿函数的接口，成为仿函数配接器，改变容器接口，称为容器配接器，改变迭代器接口，称为迭代器配接器
queue和stack就是修饰了deque的配接器
迭代器的配接器有3个，insert itertors,reverse iterators,iostream iterators.
哇塞这东西有点深，明天再看。
当我们输入网址以后，会建立http(https算了)连接，我们给服务器请求，服务器给我们回应，我们不断发送request,服务器不断返回response,请求又很多种。
我们要把这些数据存起来，数据库啊啥的都行。
1 | import requests |
上面的代码能够得到百度网站
1 | import requests |
1 | import requests |
他最重要的地方时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
Boost是基于C++标准的现代库，他的源码按照Boost Software License 来发布，允许任何人自由使用、修改和分发。
Boost强大到拥有超过90个库，但我们暂时只学习其中一部分
boost::any是一个数据类型，他可以存放任意的类型，例如说一个类型为boost::any的变量可以先存放一个int类型的值，然后替换为一个std::string的类型字符串。
好像是一个数组容器，和std::vector应该差别不大。
这个系列的博客用来介绍Boost提供的接口，不对Boost进行源码分析，关于Boost的源码，预计会在Boost源码分析笔记系列的博客中。
Any在C++17被编入STL C++是强类型语言，没有办法向Python那样把一个int赋值给一个double这种骚操作，而Boost.Any库为我们模拟了这个过程，使得我们可以实现弱类型语言的东西。
1 |
|
这样的代码是允许编译的，大概是因为boost::any内部储存的是指针。
1 |
|
上诉代码可以编译和运行，但是一定会碰到问题的，当我们把char数组弄过去的时候，就不太行了，原因是char[]不支持拷贝构造，但是我们可以通过把std::string来解决这个问题。 ## 用std::string代替char数组 可以见到我们用string完美地解决了这个问题。 ## 写很容易，如何读呢？ 我们已经学习了boost::any的写操作，但是应该如何读取呢？ 1
2
3
4
5
int main(){
boost::any a = 1;
a = std::string("hello world");
} boost提供了一个模版函数any_cast<T>来对我们的any类进行读取 ## 类型不对会抛出异常 有了any<T>的模版，看起来我们可以对boost进行任意读取，我们试试下这个 1
2
3
4
5
6
int main(){
boost::any a = 1;
std::cout << boost::any_cast<int>(a) << std::endl;
} 抛出了如下异常 1
2
3
4
5
6
7
int main() {
boost::any a = 1;
a = "hello world";
std::cout << boost::any_cast<int>(a) << std::endl;
} 实际上上诉代码是永远无法成功的。因为你把一个char数组传了进去。1
libc++abi.dylib: terminating with uncaught exception of type boost::wrapexcept<boost::bad_any_cast>: boost::bad_any_cast: failed conversion using boost::any_cast
boost的any是有很多成员函数的。比方说empty可以判断是否为空，type可以得到类型信息， 代码运行结果如下，表示首先是字符串，然后是整形。 1
2
3
4
5
6
7
8
9
10
11
12
int main() {
boost::any a = std::string("asdf");
if (!a.empty()) {
std::cout << a.type().name() << std::endl;
a = 1;
std::cout << a.type().name() << std::endl;
}
}1
2NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE
i
当我们把一个any的地址传给any_cast的时候，我们会得到any内部数据的指针， 1
2
3
4
5
6
7
8
9
int main()
{
boost::any a = 1;
int *i = boost::any_cast<int>(&a);
std::cout << *i << std::endl;
}
boost::tuple是一个元组。在c++11被编入STL
第六行无法通过编译，这说明tuple的长度最长只能是10
第9-12行定义了3个元组
第13行演示了如何通过make_tuple构造元组
第14行演示了如何通过get来访问元组里面的元素
第16行演示了get的返回值是引用
第19-20行演示了tuple的等号操作
第23-27行演示了tuple中可以储存引用
第28行通过tie构造了一个全引用元组
1 |
|
输出 1
2
3
4
5
6
7
8
9(1 2 3 4)
a.get<0>() is 1
a is (1 2 3 4 5 6 7 8 9 10)
a is (-1 2 3 4 5 6 7 8 9 10)
b is (hello world)
b==c is 0
b==b is 1
reference is (5 2)
reference2 is (10 11)
boost::variant和any很像，variant和any一样在C++17中被编入STL
variant可以指定一部分数据类型，你可以在这一部分中随便赋值，就像下面写到的一样，另外和any的any_cast不一样的是variant使用get<T>来获得内容。
1 |
|
variant允许我们使用访问者模式来访问其内部的成员，使用函数boost::apply_visitor来实现，访问者模式使用的时候重载仿函数。仿函数记得继承static_visitor即可。 输出 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct visit : public boost::static_visitor<> {
void operator()(double &d) const { std::cout << "double" << std::endl; }
void operator()(char &c) const { std::cout << "char" << std::endl; }
void operator()(std::string &s) const { std::cout << "string" << std::endl; }
};
int main() {
boost::variant<double, char, std::string> v;
v = 3.14;
boost::apply_visitor(visit(), v);
v = 'A';
boost::apply_visitor(visit(), v);
v = "Hello, world!";
boost::apply_visitor(visit(), v);
}1
2
3double
char
string
我终于找到一个暂时没有被编入C++17的库了，听说在C++20中他也没进，哈哈哈。 ## 大小写转化 首先上来的肯定就是大小写转化啦，使用函数to_upper_copy(string)就可以了。 1
2
3
4
5
6
7
8
int main() {
std::string s = "abcdefgABCDEFG";
std::cout << boost::algorithm::to_upper_copy(s) << std::endl;
std::cout << boost::algorithm::to_lower_copy(s) << std::endl;
}
erase_all_copy就是说先copy一份，然后再将子串全部删除，如果不带copy就是说直接操作穿进去的母串。下面的代码都可以去掉_copy,erase_first指的是删除第一次出现的，last指的是删除最后一次出现的，nth指的是删除第n次出现的，n从0开始,erase_head值的是删除前n个字符，erase_tail指的是删除后n个字符。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
std::string s = "000111000111ababab000111000111";
std::cout << s << std::endl;
// boost::algorithm::erase_all(s,"ab");
std::cout << boost::algorithm::erase_all_copy(s, "ab") << std::endl;
std::cout << boost::algorithm::erase_first_copy(s, "111") << std::endl;
std::cout << boost::algorithm::erase_last_copy(s, "111") << std::endl;
std::cout << boost::algorithm::erase_nth_copy(s, "111",0) << std::endl;
std::cout << boost::algorithm::erase_nth_copy(s, "111",100) << std::endl;
std::cout << boost::algorithm::erase_head_copy(s, 4) << std::endl;
std::cout << boost::algorithm::erase_tail_copy(s, 4) << std::endl;
}
find一类的函数，同上,他将返回一个iterator_range的迭代器。这个迭代器可以操作子串。注意子串和母串共享空间。 又是一套代码下来了 1
2
3
4
5
6
7
8
9
10
11
int main() {
std::string s = "000111000111ababab000111000111";
std::cout << s << std::endl;
auto x = boost::algorithm::find_first(s,"000");
x[0] = '2';
std::cout << s << std::endl;
//std::cout << boost::algorithm::find_last(s, "111") << std::endl;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
std::string s = "000111000111ababab000111000111";
std::cout << s << std::endl;
auto x = boost::algorithm::find_first(s,"000");
x = boost::algorithm::find_last(s,"1");
x = boost::algorithm::find_nth(s,"1",3);
x = boost::algorithm::find_tail(s,3);
x = boost::algorithm::find_head(s,3);
std::cout << s << std::endl;
//std::cout << boost::algorithm::find_last(s, "111") << std::endl;
}
replace又是一套如下 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
std::string s = "000111000111ababab000111000111";
std::cout << s << std::endl;
// boost::algorithm::replace_all(s,"ab");
std::cout << boost::algorithm::replace_all_copy(s, "ab","all") << std::endl;
std::cout << boost::algorithm::replace_first_copy(s, "111","first") << std::endl;
std::cout << boost::algorithm::replace_last_copy(s, "111","last") << std::endl;
std::cout << boost::algorithm::replace_nth_copy(s, "111", 0,"nth") << std::endl;
std::cout << boost::algorithm::replace_nth_copy(s, "111", 100,"nth") << std::endl;
std::cout << boost::algorithm::replace_head_copy(s, 2,"Head") << std::endl;
std::cout << boost::algorithm::replace_tail_copy(s, 2,"Tail") << std::endl;
}
trim_left_copy 指的是从左边开始修建，删掉空字符等，trim_right_copy是从右边开始修建，trim_copy是两边一起修剪。 这个代码输出了 1
2
3
4
5
6
7
8
9
10
int main() {
std::string s = "\t ab d d d d d \t";
std::cout << "|" << s << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_left_copy(s) << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_right_copy(s) << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_copy(s) << "|" << std::endl;
}1
2
3
4| ab d d d d d |
|ab d d d d d |
| ab d d d d d|
|ab d d d d d|
我们还可以通过指定谓词来修剪使用trim_left_copy_if 更多的谓词,我们还有is_lower、is_upper、is_space等谓词。 1
2
3
4
5
6
7
8
9
10
int main() {
std::string s = " 01 0 1 000ab d d d d d 11111111";
std::cout << "|" << s << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_left_copy_if(s,boost::algorithm::is_any_of(" 01")) << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_right_copy_if(s,boost::algorithm::is_any_of(" 01")) << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_copy_if(s,boost::algorithm::is_any_of(" 01")) << "|" << std::endl;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
std::string s = " 01 0 1 000ab d d d d d 11111111";
std::cout << "|" << s << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_copy_if(s,boost::algorithm::is_space()) << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_copy_if(s,boost::algorithm::is_digit()) << "|" << std::endl<<std::endl;
s = "aaaBBBaBBaaa";
std::cout << "|" << s << "|" << std::endl;
std::cout << "|" << boost::algorithm::trim_copy_if(s,boost::algorithm::is_lower()) << "|" << std::endl;
}
starts_with(s,t)判断s是否以t开头，类似的有ends_with,contains,lexicographical_compare分别表示s是否以t结尾，s是否包含t，s与t的字典序比较。 ## 字符串分割 这个就简单多了，直接split+谓词函数就行了 1
2
3
4
5
6
7
8
9
10
11
int main() {
std::cout << boost::algorithm::starts_with("abcde", "abc") << std::endl;
std::cout << boost::algorithm::ends_with("abcde", "cde") << std::endl;
std::cout << boost::algorithm::contains("abcde", "cde") << std::endl;
std::cout << boost::algorithm::lexicographical_compare("abcde", "cde") << std::endl;
std::cout << boost::algorithm::lexicographical_compare("abcde", "abcde") << std::endl;
std::cout << boost::algorithm::lexicographical_compare("cde", "abcde") << std::endl;
} 输出 1
2
3
4
5
6
7
8
9
10
int main() {
std::string s = "abc abc abc * abc ( abc )";
std::vector<std::string> v;
boost::algorithm::split(v, s, boost::algorithm::is_any_of(" *()"));
for (auto x : v) std::cout << x << ".";
std::cout << std::endl;
}1
abc.abc.abc...abc...abc...
我们注意看有些函数前面有个i，比如ierase_all, 这个说的是忽略大小写。
C++11的时候，被编入STL 明天接着整。。。
remove_cv 这个模版类能够帮我们去掉类型的const，他的实现很简单，即使用模版元技术：
1 | template <class T> struct remove_cv{ typedef T type; }; |
这个代码应该非常容易理解，remove_cv的模版是一个T,我们对他做模版偏特化，将const 和volatile分离，然后使用::value就可以得到没有const、volatile的类型了，所以这个类也叫remove_cv。
is array的实现非常简单，我们先假设所有的都不是array，即如第四行所示，然后利用偏特化，特判掉所有的array即可，让他们继承true_type,这样我们在使用的时候用::value即可判断。
1 |
|
这也是一个模版元技术，他储存了自己的类型，模版的类型，模版的值的类型，他的实现如下
1 | template <class T, T val> |
这里很明显了，value是值，value_type是value的类型，type是自己的类型。
这里就很有意思了，看看就懂
1 | typedef integral_constant<bool, true> true_type; |
可能有人会问这个有什么用，其实这样的，很多时候我们需要为我们的类添加一个value，表示true或者false，正常的实现方法是写两遍，一遍处理全部，另一遍特化false，这样写的话，代码复用就太low了，这时候，其实我们只需要实现一遍基类，派生的时候一个继承true，另一个继承false就OK了。
这个代码就nb了，我还没看懂，先留个坑,我猜了一下，大概是用来判断一个类型是否是函数指针的。
这个模版元我还真没猜出他的功能，话说怎么可能有人想得到这个bounds指的是数组的bounds呢？这个模版元的功能是传入一个数组，传出他的内容，即将T[]映射为T。注意： remove_bounds就是remove_extent。
1 | template <class T> struct remove_extent{ typedef T type; }; |
还是老样子，数组就特判掉，然后返回其头，否则就返回他的本身。
这个名字就很棒，就是移除引用的意思。同样他也是模版元技术，他先将所有的类型映射为自己，然后通过模版偏特化的方式将那些引用映射为本身。这里有一个c++的特性即下面代码 这个代码看懂的人应该不多了。
1 |
|
这里的&&就是右值引用的意思，所以输出是
1 |
1 | namespace detail{ |
同样的我们使用模版元技术，将引用就消除了。
这个模版元的意思是移除引用、移除const、移除volatile、数组移除范围、函数变成指针。
1 | namespace detail |
实际上做起来的时候是先移除引用，最后移除cv的。
如{ post_link 'Boost-学习笔记2-Boost-Any' Any接口学习 }所示，any能够支持我们的c++向python一样，给一个变量瞎赋值，这也太爽了。
1 | template<typename ValueType> |
这里是接受任意的类型，然后对这个类型使用decay得到他的基本类型，最后让holder来替我们管理。holder保持了一个输入参数的副本，我们发现这个holder类型的值放到了一个叫content的指针中。
holder继承自placeholder，placeholder是一个接口，我们不去管他，holder内部的副本保存在held中。
1 | template<typename ValueType> |
any数据有两种读取方式，一是指针，想要读取出里面的元素，显然元素是operand->content->held, 我们要得到他的指针的话，先构造出指针来： holder<remove_cv<ValueType>::type>*, 因为operand->content是placeholer,这也就是为什么下面的代码的括号在->held之前的原因。最后用boost::addressof取出地址就可以了。
1 | template<typename ValueType> |
第二种方式是读取拷贝，先移除引用，调用上面的指针读取，最后指针取内容就可以返回了。
1 | template<typename ValueType> |
前两个就不说了，直接说第三个，如果content存在，就调用content的type
1 | bool empty() const BOOST_NOEXCEPT |
type是这样实现的
1 | virtual const boost::typeindex::type_info& type() const BOOST_NOEXCEPT |
继X快速前缀树以后，Dan Willard又提出了X快速前缀树的改进版本
我们还是继续考虑n个小于M的整数(n<M)，我们按照大小，从小到大分组,每组的元素的个数在区间\([\frac{lgM}{4},2lgM]\)上,对每组构建一颗普通平衡树，这样我们一共会得到\(\frac{n}{2lgM}\)到\(\frac{4n}{lgM}\)颗树，我们在这些树中取一个随便的值r，r要在平衡树的最大和最小值之间,这样我们每棵树对应了一个r，把所有的r作为键,其对应的平衡树作为值放到X快速平衡树中，这就是Y快速平衡树。
首先在上层X前缀树上查找前驱和后继，最终我们会定位到两个叶子节点，也就对应了两颗普通平衡树，我们在这两颗普通平衡树里面直接找前驱后继然后合并就结束了。总复杂度\(lglg(\frac{n}{lgM})+2*lg(lgM)=lglgM\)
先在X前缀树上查询前驱后继，然后在其对应的平衡树上插入真正要插入的值，总复杂度\(lglg(\frac{n}{lgM})+lglgM=lglgM\)，这里有可能导致插入的值太多，进行分裂，我们来看一下这次分裂前插入了多少元素，我们考虑最坏的情况，不妨设之前也是分裂的，那么他的大小为\(lgM\)，到这次分裂一共插入了lgM+1个元素，导致现在的大小超过了2lgM，于是这lgM次插入的均摊分裂复杂度为\(\frac{lg(\frac{n}{lgM})}{lgM}\lt 1\),于是总复杂度为\(lglgM\)
同样的，我们还是先查询前驱后街，然后在对应的平衡树上删除真正要删除的值，总复杂度为\(lglg(\frac{n}{lgM})+lglgM=lglgM\),这里有可能导致平衡树上剩下的值太少，我们考虑合并，合并后如果依然太大，比方说大于lgM，我们就再次分裂为两个平衡树即可。这里可以证明，均摊复杂度依然是O1，因为从\(\frac{lgM}{2}\)到\(\frac{lgM}{4}\)也要\(\frac{lgM}{4}\)次删除，均摊下来，依然是O1,为了懒惰删除，我们甚至可以不必要求合并后超过lgM猜分裂，到2lgM也行。懒惰总是优秀的。于是总体复杂度为\(lglgM\)
至此，Y快速前缀树的所有操作均为lglgM了.
欠着欠着，以后再补。
我以前就说过，当你的数据结构达到了一定的基础，就可以学习那些更加高级的数据结构了，往往那些更加高级的数据结构由基本数据结构组合而成。
现在要你维护一个多重集合，支持3种操作，1询问一个值(这个值不一定在集合中)的前驱和后继，2向集合中插入一个元素，3从集合中删掉一个元素，1操作\(10^6\)次，2操作\(10^5\)次，3操作\(10^5\),要求你在1S内完成回答。保证集合元素都小于M=\(10^6\)
我们考虑到上面三种操作都是普通平衡树常见的操作，很多人可能就直接拿起他自己的平衡树上了。很遗憾，大概率是无法通过的。因为操作次数太多了。
我们的操作需要的是大量的查询，大量、大量，你个普通平衡树怎么操作的过来？
现在我们提出一个新的平衡树，这个平衡树非常厉害，他支持\(O(lgM)\)的时间来删除和插入，支持\(O(lglgM)\)的时间来查询前驱后继。
字典树+哈希表+维护叶子节点的双向链表+二分 首先，我们先建立一颗普通的01字典树，这个树我们对他稍作修改，考虑到字典树的节点分3类： 叶子节点、根节点、内部节点，我们让叶子节点间构造双向环状链表，其次，对于仅有左儿子的内部节点，让其右儿子指向子树的最小叶子节点，对于仅有右儿子的内部节点，让其左儿子指向子树的最大叶子节点。另一方面，我们对字典树的每一层都建立一个hash表，hash掉他们节点所代表的值是有还是没有，这样我们就构造出了一个X快速前缀树的模型了。 
假设我们要找一个数k，我们在树上寻找树和k的lca[最低公共祖先]，这个过程可以只要在hash表中二分即可知道lca在哪一个节点，可以证明，这个节点要么没有左儿子，要么没有右儿子。如果有的话，他的儿子和k的lcp[最长公共前缀]一定更长，但是这与他自己是lca的事实相悖。另一方面，由于我们的单儿子节点储存了最值信息，如果这个节点没有右儿子，则他的右儿子指向的值是k的前驱，至于后继，在叶子节点的链表上后移一个单位即可。这个过程总复杂度在二分lca上，树的高度为lgn，二分高度，所以总体复杂度为\(O(lglgn)\)
找出lca，若lca没有右儿子，则说明当前节点要插入到右儿子里面。照着做就行了，同时注意向下递归的时候把值也插入到hash表里面，递归到叶子的时候重新连接双向环状链表(前驱和后继)，最后回溯的时候维护单儿子节点的信息，以及树根方面的值就行了。
找到待删除节点，然后删掉，重新维护叶子链表，回溯的时候从hash表里面删掉自己，对于单儿子的节点也要根据子树回溯即可。
不难想到，对于那些字符集特别大的字典树来说，他们的空间消耗特别大，因为每个节点都要储存大量的指针，而这些指针往往又是空的。 # 将BST与trie结合起来 考虑这样一种树，每个节点有三个儿子，左右儿子表示自己的左右兄弟，向下的儿子表示真正的儿子。这样的树，将极大的提高了空间利用率。 # 偷个图来放着 这里插入了as,at,be,by,he.... 
考虑递归，假设我们插入到了某个节点，若下儿子与当前字符相等，则递归到下儿子并使用下一个字符来递归，如果当前字符小于下儿子，则递归到左儿子，保持当前字符不变，如果当前节点不存在了，则创建新节点，直接向下儿子走。
我们还是用数字来记录终结节点的终结字符串有多少个，若找到待删除的节点以后，终止与此的只有一个字符串，则直接删掉，否则让终极节点的计数器减1，注意在回溯的时候，如果三个儿子都没有终结字符了，就删掉自己。
递归递归。
树的平衡是一个很大的问题，这个我也没办法
很多时候，很多数据结构像变戏法一样，我们从本质看带三叉搜索树，我们发现下儿子其实是字典树的边，在考虑左右儿子，其实这个就是bst，哈哈哈发现了没有， 我们考虑删掉所有下儿子，你会发现，剩下的是一个bst森林，就像lct删掉指向父亲没有指向自己的边以后，就是splay森林一样，很神奇。我们将这些bst森林转化为一个一个普通的数组，让这些数组从新充当节点，然后将下儿子连回去， 一切都清晰了，又变成普通字典树了。 所以三叉搜索树的本质是优化后的字典树，每个节点都是一个bst。即trie套bst，外层树为trie，内层树为bst。
我们让这里的bst用avl代替？用rbt代替？用sbt代替？都可以，但是我觉得这样编码太难了吧，若实在是真的差这点效率，可以去这样做，但我认为，把普通字典树的节点用avl-map、rbt-map、sbt-map直接范型编程或设为类中类不香吗。在这玩树套树确实高大上，效率也高，但编码难度也太高了。
先欠着，以后再还。