C++标准模板库（STL）——(四)

本博客前面介绍标准模板库学习的三个容器属于序列式容器，本次将讲解STL的关联式容器，分别为：set/multiset和 map/multimap；

一 .关联式容器：

关联式容器是非线性的数据结构，是一种红黑树的平衡检索二叉树，平衡检索二叉树是任何节点的左子树和右子树的高度最多相差1的二叉树。

二. set/multiset容器：

1.概念：

set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。
multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。

2 . set/multiset 对象的默认构造：

set<int> setInt; //一个存放int的set容器。

set<float> setFloat;     //一个存放float的set容器。
set<string> setString;     //一个存放string的set容器。
multiset<int> mulsetInt;            //一个存放int的multi set容器。
multi set<float> multisetFloat;     //一个存放float的multi set容器。
multi set<string> multisetString;     //一个存放string的multi set容器。

3 .set的插入和迭代器：

set.insert(elem);     //在容器中插入元素。
set.begin(); //返回容器中第一个数据的迭代器。
set.end(); //返回容器中最后一个数据之后的迭代器。
set.rbegin(); //返回容器中倒数第一个元素的迭代器。
set.rend();   //返回容器中倒数最后一个元素的后面的迭代器。

set<int> setInt;
setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2);
for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it)
{
      int iItem = *it;
      cout << iItem;    //或直接使用cout << *it
}
//这样子便顺序输出 1 2 3 5。

set.rbegin()与set.rend()。

4.set的相关操作参考以下程序：

C++标准模板库（STL）——(四)

5.运行结果：

三 . mup/multimup容器：

1. 概念：

map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。
map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。
#include <map>

2.mup/multimup的对象默认构造：

map/multimap采用模板类实现，对象的默认构造形式：
map<T1,T2> mapTT;
multimap<T1,T2> multimapTT;
如：
map<int, char> mapA;
map<string,float> mapB;
//其中T1,T2还可以用各种指针类型或自定义类型

3.mup/multimup的插入与迭代器：

map.insert(...);    //往容器插入元素，返回pair<iterator,bool>
在map中插入元素的三种方式：
假设 map<int, string> mapStu;
一、通过pair的方式插入对象
mapStu.insert( pair<int,string>(3,"小张") );
二、通过pair的方式插入对象
mapStu.inset(make_pair(-1, “校长-1”));
三、通过value_type的方式插入对象
mapStu.insert( map<int,string>::value_type(1,"小李") );
四、通过数组的方式插入值
mapStu[3] = “小刘";
mapStu[5] = “小王"；

前三种方法，采用的是insert()方法，该方法返回值为pair<iterator,bool>
第四种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value。
string strName = mapStu[2];   //取操作或插入操作
只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。

4.mup的对象的拷贝构造与赋值：

map(const map &mp);              //拷贝构造函数
map& operator=(const map &mp);   //重载等号操作符
map.swap(mp);                 //交换两个集合容器
例如:
         map<int, string> mapA;
         mapA.insert(pair<int,string>(3,"小张"));
         mapA.insert(pair<int,string>(1,"小杨"));
         mapA.insert(pair<int,string>(7,"小赵"));
         mapA.insert(pair<int,string>(5,"小王"));

         map<int ,string> mapB(mapA);           //拷贝构造

         map<int, string> mapC;
         mapC = mapA;                                 //赋值

mapC[3] = "老张";
mapC.swap(mapA); //交换

5.mup的相关操作参考以下程序：

6.运行结果：

C++标准模板库（STL）——(四)

相关推荐