C++中的数据结构

一.STL标准库

结构:STL中有六大组件，分别是：容器，算法，迭代器，仿函数，配接器，配置器；以下分别介绍这六大组件中的最主要的三个。

1.容器

容器来配置存储空间，算法通过迭代器来获取空间内容，仿函数来协助算法完成不同的策略
向量vector是连续存储的容器，一种动态的数组，有三个指针，分别指向首端，已使用的尾部，整体的尾部，当增加数据导致分配的内存不够时，重新申请开辟一块更大的内存，将数据拷贝过去。vector适用于顺序性的遍历。
列表list是不连续的链式的双向链表存储空间，所以顺序读取较慢，但插入，删除较快，排序较快
队列queue专门用于在先进先出的上下文中操作，元素从容队列尾端压入，从队列头部取出。队列有连续的顺序存储，也有不连续的链式存储。通常做线程池一类的生产者消费者模式
映射Map是关联容器，按照特定的顺序存储由键值和映射值组合而成的元素,映射通常被实现为键值对访问的红黑树,支持下标操作
栈stack是专门用于后进先出的上下文中操作，在这种上下文中，元素只从容器的一端插入和提取。通常用户顺序浏览界面并按序返回的情况

2.算法

查找搜索类算法：find，find_first_of，search，count
改变序列类算法：copy，transform，replace，remove，fill
关系类算法：equal，includes，mismatch
堆算法：make_heap，pop_heap，push_heap，sort_heap

3.迭代器

迭代器Iterator模式⼜称 Cursor（游标）模式，⽤于提供⼀种⽅法顺序访问⼀个聚合对象中各个元素, ⽽⼜不需暴露该对象的内部表示。或者说：Iterator模式是运⽤于聚合对象的⼀种模式，通过运⽤该模式，使得我们可以在不知道对象内部表示的情况下，按照⼀定顺序（由iterator提供的⽅法）访问聚合对象中的各个元素。由于Iterator模式的以上特性：与聚合对象耦合，在⼀定程度上限制了它的只能在STL中运⽤，⼀般仅⽤于底层聚合支持类，如STL的list、vector、stack 等容器类及ostream_iterator等扩展iterator。

二.存储结构

数据存储我们常见的有二叉树，B树，红黑树，链表等，其中最为常用的是二叉树和双链表。

1.二叉树遍历

二叉树的遍历顺序前中后是针对根节点来说的，前序就是根在前，中序就是根在中，后序就是根在最后，如针对子图来分别进行遍历

前序遍历：遍历顺序是根左右，上图遍历顺序是：ABDFECGH
中序遍历：遍历顺序是左根右，上图遍历顺序是：DFBEACHG
后续遍历：遍历顺序是左右根，上图遍历顺序是：FDEBHGCA

2.红黑树

节点是红色或黑色
根节点是黑色
每个为空的叶子节点是黑色的
每个红色节点的两个子节点都是黑色
从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点
时间复杂度为O(lgn)
本质上是自平衡二叉树

3.B+树

关键字集合分布在叶子结点中，非叶节点只是叶子结点中关键字的索引
B+树中的关键字必须出现在叶节点中，也可能在非叶结点中重复出现
B+树非叶子节点不存储数据，每个叶子节点指向相邻的叶子节点

4.Hash哈希表

时间复杂度O(1)
存储键值对这种对应的数据
通过开放地址法、链地址法解决哈希表的冲突和溢出问题
非线性结构

5.list链表

线性结构
由节点组成，每个节点包含数据和指向下一个节点的指针
优点：插入和删除操作非常高效，只需调整指针即可
缺点：访问任意元素的效率较低，需要遍历整个链表

6.双链表

1.双链表结构

2.正序输出

3.倒序输出

4.双链表头插法

三.数据序列化

常用的数据序列化有：Json格式，XML格式，protobuf格式。
Json:一般的web项目中，目前最流行的主要就是json。因为浏览器对于json数据支持非常好，有很多内建的函数支持
xml: 在webservice中应用最为广泛，但是相比于json，它的数据更加冗余，因为需要成对的闭合标签。json使用了键值对的方式，不仅压缩了一定的数据空间，同时也具有可读性
protobuf:是后起之秀，是谷歌开源的一种数据格式，适合高性能，对响应速度有要求的数据传输场景。因为profobuf是二进制数据格式，需要编码和解码。数据本身不具有可读性。因此只能反序列化之后得到真正可读的数据。