1、STL介绍

STL，是Standard Template Library的缩写，即标准模板库。

STL使用C++的模板语法，通过泛型编程技术，实现了队列、栈、映射等数据结构，支持用户将自定义数据应用到这些数据结构。

STL由惠普公司三个员工开发完成，最初使用C++语言实现，STL出现后得到了广泛使用，现在已经成为C++标准库的组成部分。

2、STL的组成

根据官方描述（
https://www.geeksforgeeks.org/the-c-standard-template-library-stl/），STL由四部分组成：

算法
容器
函数
迭代器

算法：提供对数据的不同操作的方法，例如我们常用的排序、查找；

容器：用于保存对象和数据，常见的有vector、list、queue、stack、set、map；

函数：STL支持函数对象，重载函数调用操作符；

迭代器：用于访问值的序列。

3、STL Map介绍

Map是我们最常用的数据结构之一，我们一般将它翻译成“映射”，用于保存一组键值对（key-value pair）。

Map底层使用红黑树（R-B Tree）存储数据，红黑树是一种接近平衡的二叉树。

《算法导论》这本书指出，红黑树检索的时间复杂度为Log2(N)，这是比较高效的算法，例如：

如果map包含64个记录，查询某个记录最多只需要对比6次；
包含1000个记录的map，查询某个记录最多只需要搜索10次；
包含100万个记录的map，查询某个记录最多只需要搜索20次。

我们利用map，可以很轻松实现检索功能。例如下面的程序用map保存学生的姓名和年龄，并实现了所有记录的遍历功能：

#include <stdio.h>#include <string>#include <map>#include <iterator> int main(){ std::map<std::string, int> students; students.insert(std::pair<std::string, int>('Tom', 23)); students.insert(std::pair<std::string, int>('Jenny', 16)); students.insert(std::pair<std::string, int>('Jack', 19)); students.insert(std::pair<std::string, int>('Lisa', 22)); students.insert(std::pair<std::string, int>('Mary', 18)); students.insert(std::pair<std::string, int>('Sunny', 20)); students.insert(std::pair<std::string, int>('Betty', 19)); students.insert(std::pair<std::string, int>('Smith', 17)); students.insert(std::pair<std::string, int>('Joy', 21)); students.insert(std::pair<std::string, int>('Comma', 18)); students.insert(std::pair<std::string, int>('Ben', 24)); std::map<std::string, int>::iterator iter; for (iter=students.begin(); iter!=students.end(); iter++) { printf('name: %s, age: %d\n', iter->first.c_str(), iter->second); } return 0;}

程序的运行情况如下：

4、STL Map批量删除功能的实现

由于Map使用红黑树，我们不容易知道数据的存放顺序，所以我们在批量删除数据时，需要借助迭代器。

例如，我们继续在上面代码基础上，实现删除年龄大于20岁的学生：

#include <stdio.h>#include <string>#include <map>#include <iterator>  int main(){        std::map<std::string, int> students;        students.insert(std::pair<std::string, int>('Tom', 23));        students.insert(std::pair<std::string, int>('Jenny', 16));        students.insert(std::pair<std::string, int>('Jack', 19));        students.insert(std::pair<std::string, int>('Lisa', 22));        students.insert(std::pair<std::string, int>('Mary', 18));        students.insert(std::pair<std::string, int>('Sunny', 20));        students.insert(std::pair<std::string, int>('Betty', 19));        students.insert(std::pair<std::string, int>('Smith', 17));        students.insert(std::pair<std::string, int>('Joy', 21));        students.insert(std::pair<std::string, int>('Comma', 18));        students.insert(std::pair<std::string, int>('Ben', 24));        std::map<std::string, int>::iterator iter;        printf('Before delete:\n');        for (iter=students.begin(); iter!=students.end(); iter++)        {                printf('name: %s, age: %d\n', iter->first.c_str(), iter->second);        }        for (iter=students.begin(); iter!=students.end(); iter++)        {                if (iter->second > 20)                {                        students.erase(iter);                }        }        printf('After delete:\n');        for (iter=students.begin(); iter!=students.end(); iter++)        {                printf('name: %s, age: %d\n', iter->first.c_str(), iter->second);        }        return 0;}

很可惜，上面的代码不能正常运行，这是运行情况：

为什么不能运行？因为迭代器对象iter执行++操作前，它已经被删除，所以不能正常运行，出现了挂死。

怎么解决呢？我们要在删除迭代器之前，先保存下一个位置的迭代器，确保迭代器的++操作是正常的，这是修改之后的代码：

#include <stdio.h>#include <string>#include <map>#include <iterator> int main(){ std::map<std::string, int> students; students.insert(std::pair<std::string, int>('Tom', 23)); students.insert(std::pair<std::string, int>('Jenny', 16)); students.insert(std::pair<std::string, int>('Jack', 19)); students.insert(std::pair<std::string, int>('Lisa', 22)); students.insert(std::pair<std::string, int>('Mary', 18)); students.insert(std::pair<std::string, int>('Sunny', 20)); students.insert(std::pair<std::string, int>('Betty', 19)); students.insert(std::pair<std::string, int>('Smith', 17)); students.insert(std::pair<std::string, int>('Joy', 21)); students.insert(std::pair<std::string, int>('Comma', 18)); students.insert(std::pair<std::string, int>('Ben', 24)); std::map<std::string, int>::iterator iter; printf('Before delete:\n'); for (iter=students.begin(); iter!=students.end(); iter++) { printf('name: %s, age: %d\n', iter->first.c_str(), iter->second); } std::map<std::string, int>::iterator iterCurrent; iter=students.begin(); while (iter!=students.end()) { iterCurrent = iter++; if (iterCurrent->second > 20) { students.erase(iterCurrent); } } printf('After delete:\n'); for (iter=students.begin(); iter!=students.end(); iter++) { printf('name: %s, age: %d\n', iter->first.c_str(), iter->second); } return 0;}

修改后的程序可以正常运行，这是运行的情况：

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。