网站推广目标关键词,珠海策划网站建设平台,网站申请备案,免费网络电话软件关联容器
关联容器#xff08;associative container#xff09;是对容器概念的另一个改进。关联容器将值与键关联在一起#xff0c;并使用键来查找值。例如#xff0c;值可以表示雇员信息#xff08;如姓名、地址、办公室号码、家庭电话和工作电话、健康计划等#xff…关联容器
关联容器associative container是对容器概念的另一个改进。关联容器将值与键关联在一起并使用键来查找值。例如值可以表示雇员信息如姓名、地址、办公室号码、家庭电话和工作电话、健康计划等的结构而键可以是唯一的员工编号。为获取雇员信息程序将使用键查找雇员结构。前面说过对于容器 X表达式 X::value_type 通常指出了存储在容器中的值类型。对于关联容器来说表达式 X::key_type 指出了键的类型。
关联容器的优点在于它提供了对元素的快速访问。与序列相似关联容器也允许插入新元素但不能指定元素的插入位置。原因是关联容器通常有用于确定数据放置位置的算法以便能够快速检索信息。
关联容器通常是使用某种树实现的。树是一种数据结构其根节点链接到一个或两个节点而这些节点又链接到一个或两个节点从而形成分支结构。像链表一样节点使得添加或删除数据项比较简单但相对于链表树的查找速度更快。
STL提供了4种关联容器set、multiset、map 和 multimap。前两种是在头文件 set以前分别为 set.h 和 multiset.h种定义的而后两种是在头文件 map以前分别为 map.h 和 multimap.h中定义的。
最简单的关联容器是 set其值类型与键相同键是唯一的这意味着集合中不会有多个相同的键。确实对于 set 来说值就是键。multiset 类似于 set只是可能有多个值的键相同。例如如果键和值的类型为 int则 multiset 对象包含的内容可以是 1、2、2、2、3、5、7、7。
在 map 中值与键的类型不同键是唯一的每个键只对应一个值。multimap 与 map 相似只是一个键可以与多个值相关联。
有关这些类型的信息很多无法在本章全部列出但附录G列出了方法这里只介绍一个使用 set 的简单例子和一个使用 multimap 的简单例子。 set 示例 STL set 模拟了多个概念它是关联集合可反转可排序且键是唯一的所以不能存储多个相同的值。与 vector 和 list 相似set 也使用模板参数来指定要存储的值类型 setstring A; // a set of string objects第二个模板参数是可选的可用于指示用来对键进行排序的比较函数或对象。默认情况下将使用模板 less 稍后将讨论。老式 C 实现k额能没有提供默认值因此必须显示指定模板参数 setstring, lessstring A; // older implementation请看下面的代码 const int N 6;
string s1[N] {buffoon, thinkers, for, heavy, can, for };
setstring A(s1, s1 N); // initialize set A using a range from array
ostream_iteratorstring, char out(cout, );
copy(A.begin(), A.end(), out);与其他容器相似set 也有一个将迭代器区间作为参数的构造函数。这提供了一种将集合初始化为数组内容的简单方法。请记住区间的最后一个元素是超尾s1N 指向数组 s1 尾部后面的一个位置。上述代码片段的输出表明键是唯一的字符串for在数组中出现了2次但在集合中值出现了1次且集合被排序 buffoon can for heavy thinkers数学为集合定义了一些标准操作例如并集包含两个集合合并后的内容。如果两个集合包含相同的值则这个值在并集中只出现一次这是因为键是唯一的。交集包含两个集合都有的元素。两个集合的差是第一个集合减去两个集合都有的元素。 STL 提供了支持这些操作的算法。它们是通用的函数而不是方法因此并非只能用于 set 对象。然而所有 set 对象都自动满足使用这些算法的先决条件即容器是经过排序的。 set_union() 函数接受 5 个迭代器参数。前两个迭代器定义了第一个集合的区间接下来的两个定义了第二个集合区间最后一个迭代器是输出迭代器指出将结果集合复制到什么位置。例如要显示集合 A 和 B 的丙级可以这样做 set_union(A.begin(), A.end() B.begin()B.end()ostream_iteratorstring, char out(cout, ));假设要将结果放到集合 C 中而不是显示它则最后一个参数应是一个指向C的迭代器。显而易见的选择是 C.begin()但它不管用原因有两个。首先关联集合将键看作常量所以C.begin() 返回的迭代器是常量迭代器不能用作输出迭代器。不直接使用 C.begin() 的第二个原因是与 copy() 相似set_union() 将覆盖容器中已有的数据并要求容器有足够的空间容纳新信息。C 是空的不能满足这种要求。但前面讨论的模板 insert_iterator 可以解决这两个问题。前面说过它可以将复制转换为插入。另外它还模拟了输出迭代器概念可以用它将信息写入容器。因此可以创建一个匿名 insert_iterator将信息复制给 C。前面说过其构造函数将容器名称和迭代器作为参数 set_uniong(A.begin(), A.end(), B.begin(), B.end(), insert_iteratorsetstring (C. C.begin() );函数 set_intersection() 和 set_difference() 分别查找交集和获得两个集合的差它们的接口与 set_union() 相同。两个有用的方法是 lower_bound() 和 upper_bound()。方法 lower_bound() 将键作为参数并返回一个迭代器该迭代器指向集合中第一个不小于键参数的成员。同样方法 upper_bound() 将键作为参数并返回一个迭代器该迭代器指向集合中第一个大于键参数的成员。例如如果有一个字符串集合则可以用这些方法获得一个这样的区间即包含集合中从 “b” 到 “f” 的所有字符串。 因为排序决定了插入的位置所以这种类包含只指定要插入的信息而不指定位置的插入方法。例如如果 A 和 B 是字符串集合则可以这样做 string s(tennis);
A.insert(s); // insert a value
B.insert(A.begin(), A.end() ); // insert a range下面的程序演示了集合的这些用途 // setops.cpp -- some set operations
#include iostream
#include string
#include set
#include algorithm
#include iteratorint main(){using namespace std;const int N 6;string s1[N] {buffoon, thinkers, for, heavy, char, for};string s2[N] {metal, any, food, elegant, deliver, for};setstring A(s1, s1N);setstring B(s2, s2N);ostream_iteratorstring, char out(cout, );cout Set A: ;copy(A.begin(), A.end(), out);cout endl;cout Set B: ;copy(B.begin(), B.end(), out);cout endl;cout Union of A and B:\n;set_union(A.begin(), A.end(), B.begin(), B.end(), out);cout endl;cout Intersection of A and B:\n;set_intersection(A.begin(), A.end(), B.begin(), B.end(), out);cout endl;cout Difference of A and B:\n;set_difference(A.begin(), A.end(), B.begin(), B.end(), out);cout endl;setstring C;cout Set C:\n;set_union(A.begin(),A.end(),B.begin(),B.end(),insert_iteratorsetstring (C,C.begin()));copy(C.begin(),C.end(),out);cout endl;string s3(grungy);C.insert(s3);cout Set C after insertion:\n;copy(C.begin(), C.end(), out);cout endl;cout Showin a range:\n;copy(C.lower_bound(ghost),C.upper_bound(spook),out);cout endl;return 0;
}下面是程序的输出 Set A: buffoon char for heavy thinkers
Set B: any deliver elegant food for metal
Union of A and B:
any buffoon char deliver elegant food for heavy metal thinkers
Intersection of A and B:
for
Difference of A and B:
buffoon char heavy thinkers
Set C:
any buffoon char deliver elegant food for heavy metal thinkers
Set C after insertion:
any buffoon char deliver elegant food for grungy heavy metal thinkers
Showin a range:
grungy heavy metal和本章大多数示例一样该程序在处理名称空间 std 时采取了偷懒的方式 using namespace std;这样做旨在简化表达方式。这些示例使用了名称空间中非常多的元素如果使用 using 声明或作用域运算符代码将变得混乱 std::setstd::string B(s2, s2N)
std::ostream_iteratorstd::string, char out(std::cout, );
std::cout Set A: ;
std::copy(A.begin(), A.end(), out);multimap 示例 与 set 相似multimap 也是可反转的、经过排序的关联容器但键和值的类型不同且同一个键可能与多个值相关联。 基本的 multimap 声明使用模板参数指定键的类型和存储的值类型。例如下面的声明创建一个 multimap 对象其中键类型为 int存储的值类型为 string multimapint, string codes;第3个模板参数是可选的指出用于对键进行排序的比较函数或对象。在默认情况下将使用模板less 稍后将讨论该模板将键类型作为参数。老式 C 实现可能要求显示指定该模板参数。 为将信息结合在一起实际的值类型将键类型和数据类型结合为一对。为此STL 使用模板类pairclass T, class U 将这两种值存储到一个对象中。如果 keytype 是键类型而 datatype 是存储的数据类型则值类型为 pairconst keytype, datatype。例如前面声明的 codes 对象的值类型为 pairconst int, string。 例如假设要用区号作为键来存储城市名这恰好与 codes 声明一致它将键类型声明为 int数据类型声明为 string则一种方法是创建一个 pair再将它插入 pairconst int, string item(213, Los Angeles);
codes.insert(item);也可使用一条语句创建匿名 pair 对象并将它插入 codes.insert(pairconst int, string (213, Los Angeles));因为数据项是按键排序的所以不需要指出插入位置。 对于 pair 对象可以使用 first 和 second 成员来访问其两个部分了 pairconst int, string item(213, Los Angeles);
cout item.first item.second endl;如何获得有关 multimap 对象的信息呢成员函数 count() 接受键作为参数并返回具有该键的元素数目。成员函数 lower_bound() 和 upper_bound() 将键作为参数且工作原理与处理 set 时相同。成员函数 equal_range() 用键作为参数且返回两个迭代器它们表示的区间与该键匹配。为返回两个值该方法将它们封装在一个 pair 对象中这里 pair 的两个模板参数都是迭代器。例如下面的代码打印 codes 对象中区号为 718 的所有城市 pairmultimapKeyType, string::iterator, multimapKeyType, string::iterator range cods.equal_range(718);
cout Cities with area code 718:\n;
std::multimapKeyType, std::string::iterator it;
for (it - range.first; it ! range.seconde; it){cout (*it).second endl;
}在声明中可使用 C11 自动类型推断功能这样代码将简化为如下所示 auto range codes.equal_range(718);
cout Cities with area code 718:\n;
for (auto it range.first; it ! range.second; it){cout (*it).second endl;
}下面的程序演示了上述大部分计数它也是用 typedef 来简化代码 // multimap.cpp -- use a multimap#includeiostream
#includestring
#includemap
#includealgorithmtypedef int KeyType;
typedef std::pairconst KeyType, std::string Pair;
typedef std::multimapKeyType, std::string MapCode;int main(){using namespace std;MapCode codes;codes.insert(Pair(415,San Francisco));codes.insert(Pair(510, Oakland));codes.insert(Pair(718, Brooklyn));codes.insert(Pair(718, Staten Island));codes.insert(Pair(415, San Rafael));codes.insert(Pair(510, Berkeley));cout Number of cities with area code 415: codes.count(415) endl;cout Number of cities with area code 718: codes.count(718) endl;cout Number of cities with area code 510: codes.count(510) endl;cout Area Code City\n;MapCode::iterator it;for(it codes.begin(); it!codes.end(); it){cout (*it).first (*it).second endl;}pairMapCode::iterator, MapCode::iterator range codes.equal_range(718);cout Cities with area code 718:\n;for (it range.first; it!range.second; it){cout (*it).second endl;}return 0;
}下面的是程序的输出 Number of cities with area code 415: 2
Number of cities with area code 718: 2
Number of cities with area code 510: 2
Area Code City415 San Francisco415 San Rafael510 Oakland510 Berkeley718 Brooklyn718 Staten Island
Cities with area code 718:
Brooklyn
Staten Island无序关联容器C11
无序关联容器是对容器概念的另一种改进。与关联容器一样无序关联容器也将值与键关联起来并使用键来查找值。但底层的差别在于关联容器是基于树结构的而无序关联容器是基于数据结构哈希表的这旨在提高添加和删除元素的速度以及提高查找算法的效率。有4种无序关联容器它们是 unordered_set、unordered_multiset、unordered_map 和 unordered_multimap将在附录 G 更详细地介绍。
