STL-ACM入门必备

水深无声 2023-07-13 15:14 10阅读 0赞

### STL-ACM入门必备 ###

*   *  关于STL
     *  STL的实战小积累
     *  Pair模板类
     *  动态数组vector
     *  栈stack
     *  队列queue
     *  链表List
     *  集合set
     *  关联容器map
     *  双向队列deque
     *  优先队列priority\_queue
     *  multiset
     *  multimap
     *  后记

## 关于STL ##

STL包括：容器（containers）、迭代器（iterators）、空间配置器（allocator）、配接器/适配器（adapters）、算法（algorithms）、仿函数（functors）六个组件。

1.  STL容器作为常用数据结构，大致分为两类：  
    1）序列容器，即通过序列化访问的容器，如vector，list，deque；  
    2）关联容器，即通过键值对访问的容器，如set，map。  
    STL容器在实现上，属于类模板（class template）。  
    STL容器主要由头文件,,,,,和组成。
2.  迭代器可以理解为”一套访问容器的接口“，其行为类似于指针，它为不同算法提供的相对统一的对容器中元素的访问方式，使得设计算法时无需过多地关注数据。
3.  空间配置器（allocator）  
    为容器提供空间配置和释放、对象构造和析构的服务。  
    通常我们可以在代码中用"\#include "来包含它。  
    STL空间配置器在实现上，属于类模板（class template）。
4.  配接器（adapter）：将一种容器修饰为功能不同的另一种容器，如以容器vector为基础，在其上实现stack，stack的行为也是一种容器，这就是一种配接器。除此之外，还有迭代器配接器和仿函数配接器。
5.  算法“for\_each”为指定序列中的每一个元素调用指定的函数；算法“stable\_sort”以你所指定的规则对序列进行稳定性排序.STL提供一套常用的算法，其中常用到的功能范围涉及到：比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。  
    STL的算法在实现上，可以认为是一种函数模板（function template）。
6.  STL的仿函数，作为函数使用的对象，用于泛化算法中的操作。

## STL的实战小积累 ##

> 1、map关于排序  
> map默认根据key值按升序排序。  
> 2、map的基本操作函数：  
> begin() 返回指向map头部的迭代器  
> end()返回指向map尾部的迭代器  
> rbegin() 返回一个指向map尾部的逆向迭代器  
> rend() 返回一个指向map头部的逆向迭代器  
> 【end和begin进行正向遍历，rend和rbegin进行逆向遍历】  
> count()返回指定元素（key值）出现的次数，可以用来判断这个key值是否存在  
> insert() 插入元素  
> find() 查找一个元素  
> erase()删除一个元素  
> clear() 清空map  
> empty() 如果map为空则返回true  
> size() 返回map中元素的个数  
> max\_size() 返回可以容纳的最大元素个数  
> key\_comp() 返回比较元素key的函数  
> value\_comp() 返回比较元素value的函数  
> lower\_bound() 返回键值>=给定元素的第一个位置  
> upper\_bound() 返回键值>给定元素的第一个位置  
> swap() 交换两个map  
> 2.sort() 默认排序是按升序排序  
> compare（type a,type b） 自定义比较函数 a,b应该是具体元素，对结构体进行排序的时候，type是自定义的结构体类型

## Pair模板类 ##

很多人学习了很久STL，却连pair是啥都不知道，但又经常性遇到，所以，先谈谈pair：  
pair模版类需要两个参数：

> 首元素的数据类型和尾元素的数据类型。  
> pair模版类对象有两个成员：first和second，分别表示首元素和尾元素。

在中已经定义了pair上的六个比较运算符：<、>、<=、>=、==、!=，其规则是先比较first，first相等时再比较second。当然，也可以通过重载这几个运算符来重新指定自己的比较逻辑。  
除了直接定义一个pair对象外，如果需要即时生成一个pair对象，也可以调用在\*\*\*\*中定义的一个模版函数：make\_pair。make\_pair同样需要两个参数，分别为元素对的首元素和尾元素。

## 动态数组vector ##

动态数组，从末尾能快速插入与删除，直接访问任何元素。  
详细介绍，请点链接：[向量][Link 1]

## 栈stack ##

后进先出。  
详细介绍，请点链接：

## 队列queue ##

先进先出。  
详细介绍，请点链接：

## 链表List ##

双链表，从任何地方快速插入与删除。  
详细介绍，请点链接：

## 集合set ##

快速查找，不允许重复值。  
详细介绍，请点链接：

## 关联容器map ##

一对一映射，基于关键字快速查找，不允许重复值。  
详细介绍，请点链接：