stompJS详解（strtomap）



本蒟蒻写这篇分享的目的一个是为了写一个归纳总结方便自己以后随时能够复习还有就是给那些对STL还不是很了解的萌新介绍一下什么是STL以及如何使用STL更高效偷懒地解题。

CONTENTS

• 一、STL概念
• 二、STL六大组件
• 三、STL容器

• 3.1 vector
• 3.2 stack
• 3.3 string
• 3.4 queue/priority_queue
• 3.5 deque
• 3.6 map/multimap
• 3.7 set/multiset
• 3.8 unordered_map/unordered_set

• 四、STL算法

STL（，标准模板库），是惠普实验室开发的一系列软件的统称。现主要出现在 C++ 中，STL 从广义上分为：容器（）、算法（）和迭代器（）。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL 提供了六大组件，彼此之间可以组合套用，这六大组件分别是容器、算法、迭代器、仿函数、适配器、空间配置器。其中，在算法竞赛中用到最多的为容器、算法与迭代器。

• 容器（）：STL 容器为各种数据结构，如 、、、、 等，用来存放数据，从实现角度来看，STL 容器是一种 。
• 算法（）：STL 的算法多数定义在 头文件中，其中包括了各种常用的算法，如 、、、 等，从实现角度来看，STL 算法是一种 。
• 迭代器（）：STL 迭代器扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将 、、 等指针相关操作予以重载的 。所有 STL 容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。
• 仿函数（）：行为类似函数，可作为算法的某种策略，从实现角度来看，仿函数是一种重载了 的 或者 。
• 适配器（）：一种用来修饰容器或仿函数或迭代器接口的东西。
• 空间配置器（）：负责空间的配置与管理。从实现角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的 。

相信很多人学习 STL 就是为了在比赛中能够更好地装B运用各种数据结构和算法，提高解题速度。确实，使用 STL 中的容器能够不需要自己手写定义各种数据结构，使用 STL 中的算法能够不需要自己手写实现各种基本算法，因此本部分对于算法巨巨们是最为重要的一部分，那么 STL 容器究竟有哪些呢？在做题中该如何使用呢？

又称变长数组，定义在 头文件中， 容器是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。因此 的运用对于内存的合理利用与运用的灵活性有很大的帮助。

• 的定义方式：

• 的常用内置函数：

又称栈，是一种后进先出（Last In First Out，LIFO）的数据结构，定义在 头文件中， 容器允许新增元素、移除元素、取得栈顶元素，但是除了最顶端以外，没有任何方法可以存取 的其它元素，换言之， 不允许有遍历行为。

• 的定义方式：

• 的常用内置函数：

又称字符串，定义在 头文件中。C 风格的字符串（以空字符结尾的字符数组）太过复杂难于掌握，因此 C++ 标准库定义了一种 类。 和 在数据结构、内存管理等方面都是相同的。但是， 只是单纯的一个“ 元素的容器”，而 不仅是一个“ 元素的容器”，它还扩展了一些针对字符串的操作，例如 可以使用 函数转换为 C 风格的字符串， 中并未对输入输出流操作符进行重载，因此无法直接对 进行 或者 这样的操作，但是 可以，且 并不能直接实现字符串的拼接，但是 可以， 中重载了 运算符。

• 的定义方式：

• 的常用内置函数：

• 的 与 函数的用法：

又称队列，是一种先进先出（First In First Out，FIFO）的数据结构，定义在 头文件中， 容器允许从一端（称为队尾）新增元素（入队），从另一端（称为队头）移除元素（出队）。

又称优先队列，同样定义在 头文件中，与 不同的地方在于我们可以自定义其中数据的优先级，优先级高的排在队列前面，优先出队。 具有 的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它的本质是用堆实现的，因此可分为小根堆与大根堆，小根堆中较小的元素排在前面，大根堆中较大的元素排在前面。（创建 时默认是大根堆！）

• 的定义方式：

• 的常用内置函数：

又称双端队列，定义在 头文件中， 容器是单向开口的连续内存空间， 则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，也可以在头尾两端插入元素，但是在其头部进行插入操作效率很低。 和 最大的差异一是在于 允许使用常数项时间在头部进行元素的插入和删除操作，二是在于 没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。

• 的定义方式：

• 的常用内置函数：

又称映射，定义在 头文件中， 和 的底层实现机制都是红黑树。 的功能是能够将任意类型的元素映射到另一个任意类型的元素上，并且所有的元素都会根据元素的键值自动排序。 所有的元素都是 ，同时拥有键值和实值（即 对）， 被视为键值， 被视为实值， 不允许两个元素有相同的键值。 和 的操作类似，唯一区别是 的键值允许重复。

• 的定义方式：

• 的常用内置函数：

又称集合，定义在 头文件中。 的特性是所有元素都会根据元素的键值自动被排序， 的元素不像 那样可以同时拥有键值和实值， 的元素既是键值又是实值， 不允许两个元素有相同的键值，因此总结来说就是 中的元素是有序且不重复的。 的特性和用法和 完全相同，唯一的区别在于 允许有重复元素， 和 的底层实现都是红黑树。

• 的定义方式：

• 的常用内置函数：

分别定义在 与 头文件中，内部采用的是 表结构，拥有快速检索的功能。与 相比最大的区别在于 中的元素是无序的，增删改查的时间复杂度为 （ 增删改查的时间复杂度为 ），但是不支持 函数。

• 的定义方式：

• 的常用内置函数：

C++ 标准库定义了一组泛型算法，之所以称为泛型指的是它们可以操作在多种容器上，不但可以作用于标准库类型，还可以用在内置数组类型甚至其它类型的序列上。泛型算法定义在 头文件中，标准库还定义了一组泛化的算术算法（Generalized Numeric Algorithm），定义在 头文件中。使用方法如下：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qdvuejs/21858.html