STL实践指南之另一种容器：集合

下载本文示例代码
　　这是微软帮助文档中对集合（set）的解释：“描述了一个控制变长元素序列的对象（注：set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分量）的模板类，每一个元素包含了一个排序键（sort key）和一个值(value)。对这个序列可以进行查找、插入、删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关系，并且当游标指向一个已删除的元素时，删除操作无效。”　　而一个经过更正的和更加实际的定义应该是：一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map是一个更好的选择。一个集合通过一个链表来组织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。　　下面是一个例子： //程序：set演示//目的：理解STL中的集合（set）#include ＜string＞#include ＜set＞#include ＜iostream＞using namespace std;int main(int argc, char* argv[]){set ＜string＞ strset;set ＜string＞::iterator si;strset.insert("cantaloupes");strset.insert("apple");strset.insert("orange");strset.insert("banana");strset.insert("grapes");strset.insert("grapes"); for (si=strset.begin(); si!=strset.end(); si ) { cout ＜＜ *si ＜＜ " "; }cout ＜＜ endl;return 0;}// 输出： apple banana cantaloupes grapes orange//注意：输出的集合中的元素是按字母大小顺序排列的，而且每个值都不重复。　　如果你感兴趣的话，你可以将输出循环用下面的代码替换： copy(strset.begin(), strset.end(), ostream_iterator＜string＞(cout, " "));　　.集合（set）虽然更强大，但我个人认为它有些不清晰的地方而且更容易出错，如果你明白了这一点，你会知道用集合（set）可以做什么。　　所有的STL容器　　容器（Container）的概念的出现早于模板（template），它原本是一个计算机科学领域中的一个重要概念，但在这里，它的概念和STL混合在一起了。下面是在STL中出现的7种容器：　　vector（向量）——STL中标准而安全的数组。只能在vector 的“前面”增加数据。　　deque（双端队列double-ended queue）——在功能上和vector相似，但是可以在前后两端向其中添加数据。 　　list（列表）——游标一次只可以移动一步。如果你对链表已经很熟悉，那么STL中的list则是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。　　set（集合）——包含了经过排序了的数据，这些数据的值(value)必须是唯一的。　　map（映射）——经过排序了的二元组的集合，map中的每个元素都是由两个值组成，其中的key（键值，一个map中的键值必须是唯一的）是在排序或搜索时使用，它的值可以在容器中重新获取；而另一个值是该元素关联的数值。比如，除了可以ar[43] = "overripe"这样找到一个数据，map还可以通过ar["banana"] = "overripe"这样的方法找到一个数据。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。　　multiset（多重集）——和集合（set）相似，然而其中的值不要求必须是唯一的（即可以有重复）。　　multimap（多重映射）——和映射（map）相似，然而其中的键值不要求必须是唯一的（即可以有重复）。注意：如果你阅读微软的帮助文档，你会遇到对每种容器的效率的陈述。比如：log(n*n)的插入时间。除非你要处理大量的数据，否则这些时间的影响是可以忽略的。如果你发现你的程序有明显的滞后感或者需要处理时间攸关（time critical）的事情，你可以去了解更多有关各种容器运行效率的话题。　　怎样在一个map中使用类？　　Map是一个通过key（键）来获得value(值)的模板类。　　另一个问题是你希望在map中使用自己的类而不是已有的数据类型，比如现在已经用过的int。建立一个“为模板准备的（template-ready）”类，你必须确保在该类中包含一些成员函数和重载操作符。下面的一些成员是必须的：　　缺省的构造函数（通常为空）　　拷贝构造函数　　重载的”=”运算符　　你应该重载尽可能多的运算符来满足特定模板的需要，比如，如果你想定义一个类作为 map中的键（key），你必须重载相关的运算符。但在这里不对重载运算符做过多讨论了。 //程序：映射自定义的类。//目的：说明在map中怎样使用自定义的类。#include ＜string＞#include ＜iostream＞#include ＜vector＞#include ＜map＞using namespace std;class CStudent{　public :　　int nStudentID;　　int nAge;　public :　　//缺省构造函数——通常为空　　CStudent() { }　　// 完整的构造函数　　CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }　　//拷贝构造函数　　CStudent(const CStudent& ob) 　　{ 　 　nStudentID=ob.nStudentID; nAge=ob.nAge; }　　// 重载“=”　　void operator = (const CStudent& ob) 　　{　　　nStudentID=ob.nStudentID; nAge=ob.nAge; 　　}};int main(int argc, char* argv[]){　map ＜string, CStudent＞ mapStudent;　mapStudent["Joe Lennon"] = CStudent(103547, 22);　mapStudent["Phil McCartney"] = CStudent(100723, 22);　mapStudent["Raoul Starr"] = CStudent(107350, 24);　mapStudent["Gordon Hamilton"] = CStudent(102330, 22);　// 通过姓名来访问Cstudent类中的成员　cout ＜＜ "The Student number for Joe Lennon is " ＜＜ 　(mapStudent["Joe Lennon"].nStudentID) ＜＜ endl;　return 0;}　　TYPEDEF　　如果你喜欢使用typedef关键字，下面是个例子： typedef set ＜int＞ SET_INT;typedef SET_INT::iterator SET_INT_ITER　　编写代码的一个习惯就是使用大写字母和下划线来命名数据类型。　　ANSI / ISO字符串　　ANSI/ISO字符串在STL容器中使用得很普遍。这是标准的字符串类，并得到了广泛地提倡，然而在缺乏格式声明的情况下就会出问题。你必须使用“＜＜”和输入输出流（iostream）代码（如dec, width等）将字符串串联起来。　　可在必要的时候使用c_str()来重新获得字符指针。 　　这是微软帮助文档中对集合（set）的解释：“描述了一个控制变长元素序列的对象（注：set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分量）的模板类，每一个元素包含了一个排序键（sort key）和一个值(value)。对这个序列可以进行查找、插入、删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关系，并且当游标指向一个已删除的元素时，删除操作无效。”　　而一个经过更正的和更加实际的定义应该是：一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map是一个更好的选择。一个集合通过一个链表来组织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。　　下面是一个例子： //程序：set演示//目的：理解STL中的集合（set）#include ＜string＞#include ＜set＞#include ＜iostream＞using namespace std;int main(int argc, char* argv[]){set ＜string＞ strset;set ＜string＞::iterator si;strset.insert("cantaloupes");strset.insert("apple");strset.insert("orange");strset.insert("banana");strset.insert("grapes");strset.insert("grapes"); for (si=strset.begin(); si!=strset.end(); si ) { cout ＜＜ *si ＜＜ " "; }cout ＜＜ endl;return 0;}// 输出： apple banana cantaloupes grapes orange//注意：输出的集合中的元素是按字母大小顺序排列的，而且每个值都不重复。　　如果你感兴趣的话，你可以将输出循环用下面的代码替换： copy(strset.begin(), strset.end(), ostream_iterator＜string＞(cout, " "));　　.集合（set）虽然更强大，但我个人认为它有些不清晰的地方而且更容易出错，如果你明白了这一点，你会知道用集合（set）可以做什么。　　所有的STL容器　　容器（Container）的概念的出现早于模板（template），它原本是一个计算机科学领域中的一个重要概念，但在这里，它的概念和STL混合在一起了。下面是在STL中出现的7种容器：　　vector（向量）——STL中标准而安全的数组。只能在vector 的“前面”增加数据。　　deque（双端队列double-ended queue）——在功能上和vector相似，但是可以在前后两端向其中添加数据。 　　list（列表）——游标一次只可以移动一步。如果你对链表已经很熟悉，那么STL中的list则是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。　　set（集合）——包含了经过排序了的数据，这些数据的值(value)必须是唯一的。　　map（映射）——经过排序了的二元组的集合，map中的每个元素都是由两个值组成，其中的key（键值，一个map中的键值必须是唯一的）是在排序或搜索时使用，它的值可以在容器中重新获取；而另一个值是该元素关联的数值。比如，除了可以ar[43] = "overripe"这样找到一个数据，map还可以通过ar["banana"] = "overripe"这样的方法找到一个数据。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。　　multiset（多重集）——和集合（set）相似，然而其中的值不要求必须是唯一的（即可以有重复）。　　multimap（多重映射）——和映射（map）相似，然而其中的键值不要求必须是唯一的（即可以有重复）。注意：如果你阅读微软的帮助文档，你会遇到对每种容器的效率的陈述。比如：log(n*n)的插入时间。除非你要处理大量的数据，否则这些时间的影响是可以忽略的。如果你发现你的程序有明显的滞后感或者需要处理时间攸关（time critical）的事情，你可以去了解更多有关各种容器运行效率的话题。　　怎样在一个map中使用类？　　Map是一个通过key（键）来获得value(值)的模板类。　　另一个问题是你希望在map中使用自己的类而不是已有的数据类型，比如现在已经用过的int。建立一个“为模板准备的（template-ready）”类，你必须确保在该类中包含一些成员函数和重载操作符。下面的一些成员是必须的：　　缺省的构造函数（通常为空）　　拷贝构造函数　　重载的”=”运算符　　你应该重载尽可能多的运算符来满足特定模板的需要，比如，如果你想定义一个类作为 map中的键（key），你必须重载相关的运算符。但在这里不对重载运算符做过多讨论了。 //程序：映射自定义的类。//目的：说明在map中怎样使用自定义的类。#include ＜string＞#include ＜iostream＞#include ＜vector＞#include ＜map＞using namespace std;class CStudent{　public :　　int nStudentID;　　int nAge;　public :　　//缺省构造函数——通常为空　　CStudent() { }　　// 完整的构造函数　　CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }　　//拷贝构造函数　　CStudent(const CStudent& ob) 　　{ 　 　nStudentID=ob.nStudentID; nAge=ob.nAge; }　　// 重载“=”　　void operator = (const CStudent& ob) 　　{　　　nStudentID=ob.nStudentID; nAge=ob.nAge; 　　}};int main(int argc, char* argv[]){　map ＜string, CStudent＞ mapStudent;　mapStudent["Joe Lennon"] = CStudent(103547, 22);　mapStudent["Phil McCartney"] = CStudent(100723, 22);　mapStudent["Raoul Starr"] = CStudent(107350, 24);　mapStudent["Gordon Hamilton"] = CStudent(102330, 22);　// 通过姓名来访问Cstudent类中的成员　cout ＜＜ "The Student number for Joe Lennon is " ＜＜ 　(mapStudent["Joe Lennon"].nStudentID) ＜＜ endl;　return 0;}　　TYPEDEF　　如果你喜欢使用typedef关键字，下面是个例子： typedef set ＜int＞ SET_INT;typedef SET_INT::iterator SET_INT_ITER　　编写代码的一个习惯就是使用大写字母和下划线来命名数据类型。　　ANSI / ISO字符串　　ANSI/ISO字符串在STL容器中使用得很普遍。这是标准的字符串类，并得到了广泛地提倡，然而在缺乏格式声明的情况下就会出问题。你必须使用“＜＜”和输入输出流（iostream）代码（如dec, width等）将字符串串联起来。　　可在必要的时候使用c_str()来重新获得字符指针。 下载本文示例代码


STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合STL实践指南之另一种容器：集合