发布时间 : 2024/5/1 4:57:30 星期三 文章STL应用篇更新完毕开始阅读3a18734ee518964bcf847cf8

fruits.insert(\fruits.insert(\fruits.insert(\fruits.insert(\输出set

set::iterator itEnd = fruits.end();

for (set::iterator it=fruits.begin(); it != itEnd; it++) cout << *it << \输出结果

apple apple banana banana orange

4.3.3. map

map是字典的抽象数据结构(ADT)。map中的所有的元素都会根据key自动进行排序，而且所有的元素都是唯一的。map中的所有的元素都是pair，即键(key)和值(value)组成的序列(pair中的第一个元素为key，第二个元素为value)。

map中的迭代器的种类为双向存取迭代器(bidirectional-access-iterator)。 请看下面的例子：

构建一个map

typedef std::map EMPLOYEE_MAP; EMPLOYEE_MAP employees;

往map中添加数据

employees.insert(EMPLOYEE_MAP::value_type(25301, \employees.insert(EMPLOYEE_MAP::value_type(25302, \employees.insert(EMPLOYEE_MAP::value_type(25303, \employees.insert(EMPLOYEE_MAP::value_type(25304, \employees.insert(EMPLOYEE_MAP::value_type(25305, \输出map

EMPLOYEE_MAP::iterator itEnd = employees.end();

for (EMPLOYEE_MAP::iterator it = employees.begin(); it != itEnd; ++it) { std::cout << it->first << \

std::cout << it->second << endl; } 输出结果 25301-A 25302-B 25303-C 25304-D 25305-E

4.3.4. multimap

multimap和map基本相同，所不同的是，一个multimap中的key可以重复。

multimap中的迭代器的种类为双向存取迭代器(bidirectional-access-iterator)。

multimap的操作同map。

4.3.5. 其它

这里要提到的就是hashtable，即哈希表的抽象数据结构(ADT)。

因为hashtable不是STL标准的一部分，部分编译器(如Microsoft Visual C++)并没有提供hashtable的实现。

hashtable中的迭代器的种类为前向迭代器(forward-iterator)。

在SGI的STL中，有hashtable的实现，其中的hash_set,hash_map,hash_multiset, hash_multimap都是基于hashtable而构建的，是hashtable的适配器(Adaptor)。而在Microsoft Visual C++的STL中，并没有提供STL的实现。其中的

hash_set,hash_map,hash_multiset,hash_multimap都是基于STL中的hash算法而构建的。

hash_set的操作基本同set；

hash_map的操作基本同map；

hash_multiset的操作基本同multiset； hash_multimap的操作基本同multimap。

5． 算法

STL中的算法以迭代器为参数，通过作用于迭代器而达到处理容器数据的目的。所有的算法都前两个参数都是以对迭代器（iterator），通常称为first和last。事实上，算法所处理的迭代器范围为[first,last)，如果first==last则表明此范围为空。按照处理问题的不同，STL算法可分为四组，分别是：

1.不改变序列的算法(None-mutating sequence Algorithm)

2.改变序列的算法(Mutating sequence Algorithm)

3.排序以及相关算法(Sorting and related Algorithm) 4.常用数字算法(Generalized numeric Algorithm)

很多算法都有if版本，如remove_if，这类算法会根据判断条件进行相应的操作；有一些算法具有copy_if或copy版本，不同于非copy_if或copy版本的是，这些操作将获取的值改写另外的迭代器。

本文并不打算对这些算法作详细的介绍，只是对这些算法做简单性的描述。更多的内容，推荐参考《C++ Primer》或《STL和泛型程序设计》。 5.1. 改变序列的算法

这类算法以输入迭代器(input-iterator)为输入参数，但不改写迭代器迭代器范围内的数据。典型的算法有：find、count、equal、search、for_each等。

5.2. 不改变序列的算法

这类算法以输入迭代器(input-iterator)为输入参数，往往还带有一个输出迭代器(output-iterator)，对输入迭代器(input-iterator)处理的结果写入输出迭代器。典型的算法有：copy、transform、remove、rotate、reverse、fill、replace等。 5.3. 排序以及相关算法

这类算法往往以双向迭代器(bidirectional-iterator)为输入输出参数，对迭代器范围内的数据进行排序，最终序列里面的值都会发生改变。之所以把排序以及相关算法和”不改变序列的算法”分离出来是因为这类算法解决了是算法领域的一类问题，而且这类问题在算法领域的重要性异常突出。典型的算法有：sort、partial_sort、nth_element、qsort、stable_sort、partition、merge、inplace_merge等。

5.4. 常用数字算法

这类算法往往以双向迭代器(bidirectional-iterator)为输入输出参数，对迭代器范围内的数据进行数字操作(如内积等)，最终序列里面的值都会发生改变。这类算法解决的是数学领域相关的问题，因此被划为一类。典型的算法有：next_permutation、pre_permutation、inner_product等。

6． 适配器(Adaptor)

适配器(Adaptor)是为了增强功能或/和添加约束，对容器、迭代器、算法重新进行了包装的模板类。设计模式中的Decorate模式的基本思想是实现适配器(Adaptor)的理论/实践基础。在STL中，适配器可分为三类：容器适配器、迭代器适配器以及算法适配器。 6.1. 容器适配器

容器适配器是对特定的容器进行Decorate而形成的新的模板类。常见的容器适配器有： 1.vector适配器

stack：堆栈，是一种FILO的数据结构。

2.deque适配器

priority_queue：优先级队列，队列里面的所有数据都是按照优先级进行排序的。

queue：单向队列。 3.list适配器

slist：单向链表。

4.hashtable的适配器

hash_map,hash_set,hash_multimap,hash_multiset

6.2. 迭代器适配器

迭代器适配器是对特定的迭代器进行Decorate而形成的新的模板类。常见的迭代器适配器有：

1.反向迭代器(reverse iterator)

相对迭代器(iterator)，反向迭代器(reverse iterator)是按照相反的顺序对容器的数据进行访问的，如

vector::reverse_iterator ritBegin = vec.rbegin();

vector::reverse_iterator ritEnd = vec.rend(); 2.插入迭代器(insert iterator)

插入迭代器简化了向容器中插入元素的工作，指定了向容器中插入元素的位置。STL中有三种插入迭代器：

n 前向插入迭代器

在容器的前面插入元素，如调用容器的push_front n 后向插入迭代器

在容器的后面插入元素，如调用容器的push_back n 任意插入迭代器

在容器的任意位置插入元素，如调用容器的insert 3.原始存储迭代器(raw storage itertor)

允许算法将其结果保存到没有初始化的内存中。 6.3. 函数适配器

函数对象适配器是对某类特定函数对象进行Decorate而形成的新的模板类。常见的迭代器适配器有： 1.否定者 (negator)

STL中有两个否定者not1和not2，分别对一元和二元谓词(predicate)的执行结果取反。 2.绑定者(Binder)

STL中有两个绑定者binder1st和binder2nd(你可以通过调用函数bind1st和bind2nd分别构建这两个绑定者)，分别将特定值绑定到函数对象的第1个和第2个参数s。 3.函数指针函数适配器(Adaptors for pointers to function)

因为STL中的算法一般都使用函数对象作为参数。如果需要使用原始的函数指针用于这些算法的输入参数，那么我们就需要将这些原始指针转化成特定的函数对象。STL提供了这样的转换函数，包括：

n 转化成员函数：mem_fun，mem_fun_ref，mem_fun1，mem_fun1_ref n 转化非成员函数：ptr_fun

7． 资源

1. STL中文站：http://www.stlchina.org 2. Boost：http://www.boost.org/

3. SGI STL：http://www.sgi.com/tech/stl/ 4. STL port：http://www.stlport.org/

参考文献

1.STL源码剖析/候捷；武汉：华中科技大学出版社，2002.6

2.Effective STL /Scott Douglas Meyers著

3.The Standard Template Library Tutorials, Johannes Weidl,1994.4

4.C++ Primer第三版/(美)Stanley B.Lippman,Josee Lajoie著；潘爱民,张丽译；北京：中国电力出版社

C++标准模板库（STL）中map使用详解 (2011-03-01 09:07:03) 转载 标签： 分类： 探访Cpp 杂谈

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

下面举例说明什么是一对一的数据映射。比如一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可能轻易描述，很明显学号用int描述，姓名用字符串描述(本篇文章中不用char *来描述字符串，而是采用STL中string来描述),下面给出map描述代码：

Map mapStudent; 1. map的构造函数

map共提供了6个构造函数，这块涉及到内存分配器这些东西，略过不表，在下面我们将接触到一些map的构造方法，这里要说下的就是，我们通常用如下方法构造一个map： Map mapStudent; 2. 数据的插入

在构造map容器后，我们就可以往里面插入数据了。这里讲三种插入数据的方法：

第一种：用insert函数插入pair数据，下面举例说明(以下代码虽然是随手写的，应该可以在VC和GCC下编译通过，大家可以运行下看什么效果，在VC下请加入这条语句，屏蔽