编程日志5.19

STL（Standard Template Library)

优点：

1.提高编程效率

2.增强代码的可维护性和可读性

3.促进代码的复用

六大组件：

容器：存放数据结构，顺序表（vector)、串(string)、双端队列(deque)、链表(list)、集合(set)、哈希表（unordered_map)

算法：常用算法的封装，排序(sort)、查找(find)、遍历(traversal)

迭代器：遍历和访问容器中的元素，容器和算法的桥梁

仿函数：算法策略

适配器：用于修改或适配现有的容器或迭代器的行为，如stack和queue就是通过适配器基于底层的容器实现的

分配器：用于管理内存分配

STL容器分类

1、序列容器：按特定顺序存储

vector 顺序表：支持动态扩容也叫柔性数组，内部数据结构是连续存储的，可以随机访问，在尾部插入和删除效率高，中间插入删除效率低。

lis 双向循环列表：元素通过指针链接，在任何位置插入和删除元素，效率都较高，但随机访问效率。

deque 指针数组：数组的每个元素是一个指向一块连续内存的指针，结合了vector和list的特点，支持在两端高效的插入和删除元素，也可以随机访问。

2、关联容器：按照键的特定顺序存储和访问 set map 红黑树（本质上是平衡二叉树），增删改查时间复杂度O(log(n)),效率高。

3、容器适配器：对基本容器进行封装和适配

stack：后进先出线性表（queue、vector）

queue：先进先出线性表（queue、list）

STL常见算法：

遍历算法、最值算法、排序算法、查找算法、反转算法

冷门算法：稳定婚姻、树链剖分、后缀自动机、跳舞链、模拟退火、随机算法（不通用 无）

STL迭代器（->指针）：

用于遍历容器中元素的工具

主要作用：

1、遍历容器元素  2、与算法结合使用

迭代器的类型：

输入迭代器：只能用于读取元素，只能向前移动一次。

输出迭代器：只能用于写入元素，只能向前移动一次。

前向迭代器：可以向前读取和写入元素。

双向迭代器：可以向前和向后移动，进行读取和写入操作。

随机访问迭代器：随机访问，像指针一样进行算术运算。

算法：

          vector<int> vec;

           vector<int>::iterator it;

            it++;

            int x=*it;

优点：

使得STL的容器和算法能够灵活地协同工作，提高了代码的通用性和可扩展性。