【C++ Primer】STL容器Map - c++编程基础

MAP容器
1）概念：map 是一个容器,它用于储存数据并且能从一个数据集合中取出数据。它的数据组成包含两项,一个是它的数据值,一个是用于排序的关键字。其中关键字是惟一的,它用于将数据自动排序。而每个元素的数据值与关键字无关,可以直接改变。

【重点】内部结构采用RB_TREE(红黑树)。查找复杂度：O(log2N)

2）使用
需加载的头文件: #include
using namespace std;
模板原型:
template <
class Key, //关键字的数据类型
class Type, //数据值的数据类型
class Traits = less, //提供比较两个元素的关键字来决定它们在 map容器中的相对位置。它是可选的,它的默认值是 less
class Allocator=allocator > //代表存储管理设备。它是可选的,它的默认值为allocator >
>

3）map 容器特点:
(1)是一个相关联的容器,它的大小可以改变,它能根据关键字来提高读取数据能力。
(2)提供一个双向的定位器来读写取数据。
(3)已经根据关键字和一个比较函数来排好序。
(4)每一个元素的关键字都是惟一的。
(5)是一个模板,它能提供一个一般且独立的数据类型。
4）有关map最详细的介绍详见资源
STL MAP详细资源下载
5）结合map方法给出了一个综合测试代码：
[html]
#include
#include
#include
using namespace std;

map ctr;

int print_one_item(map ::const_iterator cp)//用于打印 map 的一个元素
{
cout<<"("<first<<" , "<second<<") ";

return 0;
}

void test_equal_range()//测试equal_range()的功能
{
//pair第一个迭代器返回第一个大于或等于给定的关键字的元素
//pair第二个迭代器返回第一个比给定的关键字大的元素。

pair ::const_iterator, map ::const_iterator> p;

p=ctr.equal_range(2);

if(p.first!=ctr.end())
{
cout<<"The first element which key >= 2 is: ";
//cout<<"("<first<<" , "<second<<") ";
print_one_item(p.first); //调用子程序来打印一项
cout< }
if(p.second!=ctr.end())
{
cout<<"The first element which key > 2 is: ";
cout<<"("<first<<" , "<second<<") ";
cout< }

}

void creat_map()
{
ctr.insert(pair (1,'a'));
ctr.insert(pair (2,'b'));
ctr.insert(pair (3,'b'));
ctr.insert(pair (4,'c'));
ctr.insert(pair (5,'d'));
ctr.insert(pair (1,'c'));
}

void erase_map()//删除某一个元素
{

map ::iterator cp=ctr.find(2);
ctr.erase(cp);//删除关键值等于 2 的元素
}

void clear_map()
{
ctr.clear();//清空 map 容器（删除全部元素）
if(ctr.empty())//map 容器为空时
cout<<"The container is empty"< else
cout<<"The container is not empty"< }

int print()//用于打印一个 map 容器
{
map::const_iterator cp;
for(cp=ctr.begin();cp!=ctr.end();cp++)//让 cp 从 c 的开始到结束打印 cp 对应的值
print_one_item(cp); //调用子程序来打印一个元素

return 0;
}

void print_first_element()
{
map ::iterator cp;//迭代器
cp=ctr.begin(); //定位到 ctr 的开始位置
cout<<"The first element is:"<second< }
void key_compare_map() //key_comp取得一个比较对象的副本以对 map 容器中的元素进行排序。
{
map c;
map >::key_compare kc = c.key_comp() ;
if(kc( 1, 2 ))
cout<<"kc(1,2) is true"< else
cout<<"kc(1,2) is false"<
if(kc( 2, 1 ))
cout<<"kc(2,1) is true"< else
cout<<"kc(2,1) is false"< }
void lower_bound_map()
{
map ::iterator cp;
/* 返回一个指向第一个关键字的值是大于等于一个给定值的元素的定位器,或者返回指向 map 容
器的结束的定位器
*/
cp=ctr.lower_bound(2);//返回第一个大于等于2的元素的定位器

if(cp!=ctr.end())
{
cout<<"The first element which key >= 2 is: ";
print_one_item(cp);//调用子程序来打印一项
cout< }

}

void compare_map()
{
map ctr1,ctr2;
int i;
for(i=0;i<3;i++)
{
ctr1.insert(pair (i,'a'+i));
ctr2.insert(pair (i,'A'+i));
}
if(ctr1!=ctr2)//当 ctr1 与 ct2 不同时
cout<<"They are not equal"< else//当 ctr1 与 ctr2 相同时
cout<<"They are equal"<
}
void comp_map()

【C++ Primer】STL容器Map(一)