HM185 标准库分拣台
HM185 标准库分拣台
来源： 第 185 集 STL初识-STL的基本概念
难度： 普及-
时间限制： 1s
空间限制： 64MB
题目描述
软件界一直希望少做重复劳动。面向对象用封装、继承、多态提高复用；泛型编程用模板把类型参数化。多数时候数据结构和算法没有统一标准，不同人会写出功能相同、名字不同的加法。于是出现了 STL（Standard Template Library，标准模板库）：系统提供一套标准的函数模板和类模板，大家直接用。
广义上 STL 分三大块：**容器**、**算法**、**迭代器**。容器和算法通过迭代器无缝衔接——迭代器是二者之间的桥梁（胶合剂）。算法必须经过迭代器才能访问容器里的元素；每个容器都有自己专属的迭代器，使用时可以先把它当成指针（解引用、箭头）。STL 里的技术基本都采用类模板或函数模板。
细分则有六大组件，面试常问全名：
- 容器：放数据。常见的有
vector、list、deque、set、map等。 - 算法：解决问题，头文件名就是
algorithm。常见的有sort、find、copy、for_each。 - 迭代器：容器与算法的粘合剂。
- 仿函数：重载函数调用运算符
()的类，对象用起来像函数，用来给算法换策略。 - 适配器（有的书叫配接器）：修饰、组装接口。
- 空间配置器：负责空间的配置与管理（例如容器在堆区的开辟与释放），使用容器时不必自己管这块。
本课详细展开前四个；后两个只需知道用途。
容器按数据结构可再分成两类：
- 序列式：强调值的排列，每个元素有固定位置。按
1 3 5 4 2放入，取出来仍是1 3 5 4 2。 - 关联式：放入时就会排序，没有严格按插入次序的物理顺序。同一批数放进去，取出来可能是
1 2 3 4 5。
算法也分两类：
- 质变算法：运算期间会改区间内的元素，例如拷贝出另一份、首尾对调、删除。
- 非质变算法：不改区间内的元素，例如查找、计数、遍历、求极值。
迭代器按能力分为五种：**输入**（只读）、**输出**（只写）、**向前**（只能 ++）、**双向**（++ 与 --）、**随机访问**（可以一次跳多格，最强）。常用容器提供的都是双向或随机访问迭代器。
请按下面规则完成分拣。
输入格式
第一行一个整数 \(n\)。
第二行 \(n\) 个整数 \(a_i\)，表示按此顺序放入货架。
第三行一个整数 \(m\)。
接下来 \(m\) 行，每行一个操作名，只可能是：
copy reverse erase replace find count for_each extremum
其中前四个按质变处理，后四个按非质变处理。
再一行一个整数 \(p\)。
接下来 \(p\) 行，每行一个组件英文名，只可能是：
container algorithm iterator functor adapter allocator
再一行一个整数 \(q\)。
接下来 \(q\) 行，每行一个迭代器能力词，只可能是：
readonly writeonly increment both jump
分别对应：只读、只写、只能向前、双向、随机跳跃。
输出格式
第一行：按序列式规则输出 \(n\) 个整数（插入顺序），空格分隔。
第二行：按关联式规则输出这 \(n\) 个数的升序结果，空格分隔。
接下来 \(m\) 行：每个操作输出 质变 或 非质变。
接下来 \(p\) 行：每个组件输出中文名，依次为 容器、算法、迭代器、仿函数、适配器、空间配置器。
接下来 \(q\) 行：每种能力输出 输入、输出、向前、双向 或 随机。
行末无多余空格。
样例
输入 #1
5
1 3 5 4 2
4
copy
find
reverse
count
3
container
functor
allocator
4
readonly
increment
both
jump
输出 #1
1 3 5 4 2
1 2 3 4 5
质变
非质变
质变
非质变
容器
仿函数
空间配置器
输入
向前
双向
随机
输入 #2
3
9 9 1
2
erase
for_each
2
adapter
algorithm
1
writeonly
输出 #2
9 9 1
1 9 9
质变
非质变
适配器
算法
输出
说明
\(1 \le n,m,p,q \le 1000\)，\(|a_i| \le 10^9\)。
- 关联式按**升序排序**模拟「放入时就排序」；相同值全部保留。
adapter与配接器是同一组件，输出统一写成适配器。- 常用容器的迭代器属于双向或随机访问，本题只按输入的能力词分类，不要求判断某个容器属于哪一种。
