C++标准模板库集合类与映射类总结

  • Post author:
  • Post category:其他



一、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,指出容器中键值对的个数。



转载于:https://www.cnblogs.com/huty/p/8519282.html