C++标准模板库集合类与映射类总结
分类：数据结构-算法-编程
一、STL集合类
标准模板库向程序员提供了一些容器类，以便在应用程序中频繁而快速的搜索。std::set和std::multiset用于存储一组经过排序的元素，，其查找元素的复杂度为对数，而unordered集合的插入和查找时间是固定的。
容器set和multiset快速查找键，键是存储在一维容器中的值，multiset可存储重复的键值，而set不行。STL容器是泛型模板类，可用于存储字符串、整型、结构或对象。
为了实现快速搜索，STL set和multiset内部结构类似二叉树，将元素插入到set时对其进行排序。
实例化
实例化的方法跟其他类型的容器类似，而访问的方法也可以声明一个迭代器。对于插入元素排序，如果没有提供排序标准，它将使用默认谓词std::less，确保元素升序排列。要创建二元排序谓词，可在类中另一个operator()，让它接受两个参数，其类型与容量中存储的数据类型相同，并根据排序标准返回true。然后在实例化set或multiset时指定该谓词。
举例如下：
set<int> SetIntegers1;
set<int, SortDescending<int>> SetIntegers2;
第一个是最简单的实例化，省略了除类型外的其他所有模板参数，这导致使用默认排序谓词，即std::less<T>，如果要覆盖这种默认行为，则需要具体化另一个谓词模板，即使用指定的排序标准SortDescending来进行具体化set模板类的第二个模板参数。
插入元素
大多数容器都实现了成员函数insert，用法都类似。令使用count可以返回在multiset中存储指定元素的个数。
查找元素
关联容器大都实现了成员函数find()，根据提供的键值查找值。返回值为指向该元素对应的迭代器。对于multiset来讲，返回第一个与给定键值匹配的元素。如果没有找到，则返回对应的容器的.end()迭代器。
删除元素
erase函数，能够根据键删除值，还可以根据迭代器的范围来删除set或multiset中的值
小结：
针对频繁查找的情形使用set或multiset会合适，将对象存储在set或multiset中时要注意实现运算符<和==，前者提供排序谓词，后者提供find等函数。在需要频繁插入而不是频繁查找的情况下，最好使用list而不是set。
二、STL映射类
STL映射类map和multimap是键值对容器，支持根据键进行查找，与set和multiset类似，内部结构类似二叉树，在插入时排序。
实例化
要实例化将整数用作键、将字符用作map或multimap，必须具体化模板类std::map或multimap，实例化模板类map时，需要指定键和值的类型以及可选的谓词（帮助map类对插入的元素进行排序）。因此，典型的map实例化语法如下：
#include<map>
using namespace std;
map<keyType valueType, Predicate=std::less <keyType> > mapObject;
multimap<keyType valueType, Predicate=std::less <keyType> > mapObject;
第三个模板参数是可选的，如果指定了键和值的类型，而省略了第三个模板参数，将默认使用std::less用作排序标准。
指定排序谓词的方法所有的容器大致相同。
插入元素
insert，因为这种容器包含的元素都是键值对，因此可以使用std::pair来指定要插入的键、值：mapIntToString.insert(pari(-1, "Minus One"));还可以使用类似数组的语法[]进行操作，比如等效的形式为mapIntToString[-1] = "Minus One";[]内为键，=右边为值。
查找元素
find，根据给定的键来查找值，返回迭代器。首先应当检查迭代器是否查找到，再利用迭代器进行访问。如果没有查到，返回的迭代器指向容器末尾。而使用迭代器访问时，first返回的是键，而second返回的是值。
对于multimap，容器中可能包含多个键相同的键值对，因此需要找到与指定键对应的所有值，为此，可使用count来确定多少个值与指定的键对应，在对迭代器进行递增，以访问这些相邻的值。迭代器此时返回的是第一个键值对。
删除元素
erase，类似set和multiset。提供了使用键、迭代器和迭代器范围来删除元素。
小结：
需要存储键值对而且键是唯一的时，使用map，而键可重复时（比如电话簿）可使用multimap。与其他容器一样，都用成员函数size，指出容器中键值对的个数。
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇BP神经网络设计常用的基本方法和实用技术下一篇数据结构（三）:非线性逻辑结构-二叉树
顶0踩0
就会犯错误，就会有无数次让自己跌倒的机会出现，
