元素dataSTL关联容器—map

题记:写这篇博客要主是加深自己对元素data的认识和总结实现算法时的一些验经和训教,如果有错误请指出,万分感谢。

    

  不同于顺序容器,关联容器并不在线性配置中存储元素。相反,它们提供了一个键到值得映射。一般地,关联容器的插入、删除和查找时间都相同,为 O( log(N) )

 STL提供了4个关联容器,包括:map、multimap、set、multimap。这些容器都将元素存储在一个有序的、相似于树的数据结构中。

  上面重要介绍了 map 的一些属性和方法。

      pair工具类

  在学习关联容器之前,必须先熟习 pair 类,这个类定义在 <utility> 头文件中。pair 是一个类模板,它将两个值组织在一起,这两个值的类型可能不同。可以通过 first 和 second 大众数据成员来拜访这两个值。为 pair 定义了 operator== 和 operator < 来比拟 first 和 second 元素。

  以下是一些例子:

#include<utility>
#include<string>
#include<iostream>

using namespace std;
 
int main()
{
	//two-argument ctor and default ctor
	pair<string, int> mypair("hello",5),myOtherPair;

	//can assign directyly to first and second
	myOtherPair.first = "hello";
	myOtherPair.second = 6;

	//copy ctor.
	pair<string, int> myThirdPair(myOtherPair);

	//operator<
	if(mypair < myOtherPair)
		cout<< "myPair is less than myOtherPair!"<<endl;
	else
		cout<< "myPair is greater than or equal to myOtherPair!"<<endl;

	//operator ===
	if(myOtherPair == myThirdPair)
		cout<< "myOtherPair is equal to myThirdPair!"<<endl;
	else
		cout<<"myOtherPair is not equal to myThirdPair!"<<endl;

	return 0;
}

    

  标准库还提供了一个工具函数模板 make_pair( ) ,它能从两个变量结构一个 pair 。例如,可以如下应用这个工具函数模板。

 pair<int, int > aPair = make_pair( 5, 10 ) ;

    

  当然,在这种情况下,可以只应用两参数的结构函数。不过,如果想把一个 pair 传递给一个函数,make_pair( ) 将更有用。不同于类模板,函数模板可以从参数推导出类型,因此可以应用 make_pair( ) 来结构一个 pair ,而无需显式地指定类型

      tips:在 pair 中应用指针类型很危险,因为 pair 复制结构函数和赋值操作符只实现指针类型的浅复制和赋值。

  

  map

  map 是最有用的容器之一。它存储的是键/值对而不是一个值。插入、查找和删除都基于键实现,值只是“顺带的”。“映射”(map)一词就是源于其概念理解,即容器将键“映射”至值。

  map 会基于元素的键来保证元素有序,因此插入、删除和查找都取对数时间。平日 map 实现为某种形式的平衡树,如红黑树。不过,客户并不会看到这个树结构。

  如果要基于一个“键”值来存储和获得元素,就应该应用 map。

  结构映射

  map 模板取4个类型:键类型、值类型、比拟类型和分配类型。如果忽略了比拟和分配器参数,结构 map 就与结构一个 vector 或 list 很是相似,只不够要在模板中分别指定键和值类型。例如,以下代码会结构一个 map ,这个映射应用 int 作为键,并保存 Data 类的对象作为值(在此没有提供其完全定义):

#include<map>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	
	return 0;

    

  插入元素

    

  向诸如 vector 和 list 等顺序容器插入元素时,总是要指定要在哪里增长元素。 map 以及其他关联容器则与此不同。 map 外部实现会确定保存新元素的位置。你要做的只是提供键和值。

  在插入元素是,要记着重要的一点,map 支持所谓的 “唯一键”。map 中的每一个元素都必须有一个不同键。如果想支持多个元素有相同的键,就必须应用 multimap。

  向 map 中插入元素有两种方法,一种比拟笨,另外一张没那么笨。

  insert ( ) 方法

  向 map 中增长一个元素的笨方法是 insert ( ) 方法。对此,一个问题必须指定键/值对作为一个 pair 对象。第二个问题是,基本形式 insert ( ) 的返回值是 iterator 和 bool 的一个队(pair)。为什么会返回这么庞杂的返回值,原因是,如果已经有指定键的元素,insert ( ) 不会重写(覆盖)这个元素的值。所返回 pair 的 bool 元素会指示 insert ( ) 是不是确切插入了新的键/值对。iterator 会指示 map 中有指定键的元素(可能为新值,也可能为本来的值,这取决于插入是不是成功)。例如:

#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	pair<map<int, Data>::iterator, bool> ret;

	ret = dataMap.insert(make_pair(1,Data(4)));
	if(ret.second)
		cout<<"insert successed!"<<endl;
	else
		cout<<"insert failed!"<<endl;

	ret = dataMap.insert(make_pair(1,Data(6)));
    if(ret.second)
		cout<<"insert successed!"<<endl;
	else
		cout<<"insert failed!"<<endl;
	
	return 0;
}

  运行结果:

    元素和data

    

  重载operator [ ]

  向 map 插入元素还有一个不那么笨的方法,这就是通过重载的 operator [ ] 。重要是在语法上有区别:要分别指定键和值。另外 operator[ ] 总能成功。如果不存在有给定键的元素值,它会用该键和值分别创建一个新的元素,如果已经存在给定键的元素, operator [ ] 会把现有的元素值替换为新指定的值。上面的例子还是后面的例子,只不过这里应用了 operator [ ] 而不是 insert ( ) .

    每日一道理
心的本色该是如此。成,如朗月照花,深潭微澜,不论顺逆,不论成败的超然,是扬鞭策马,登高临远的驿站;败,仍滴水穿石,汇流入海,有穷且益坚,不坠青云的傲岸,有“将相本无主,男儿当自强”的倔强。荣,江山依旧,风采犹然,恰沧海巫山,熟视岁月如流,浮华万千,不屑过眼烟云;辱,胯下韩信,雪底苍松,宛若羽化之仙,知退一步,海阔天空,不肯因噎废食。
#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	dataMap[1] = Data(4);
	dataMap[1] = Data(6);//replace the element with key 1
	
	return 0;
}

  不过,对于 operator[ ] 有一点警告:它总是会结构一个新的值对象,即使并不需要应用这个对象。因此,要求元素值(值对象)有一个默许结构函数,而且这种做法可能没有 insert( ) 效率高。

    

  map 迭代器

  map 迭代器的任务于顺序容器迭代器的任务很相似。重要区别在于,这里的迭代器指示的是键/值对而不是一个值。要想拜访值,必须获得 pair 对象的 second 字段。例如:

#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	dataMap[1] = Data(4);
	dataMap[1] = Data(6);//replace the element with key 1

	for(map<int, Data>::iterator it = dataMap.begin(); it !=dataMap.end(); ++it)
	{
		cout<< it->second.getVal()<<endl;
	}
	
	return 0;
}

      tips:1、迭代器一般不必 - > 操作符,(*it).second.getVal( ) 这一句与以上表达式的功能相称。

             2、可以通过非 const 迭代器修改元素的值,但是不能修改元素的键,即使是应用一个非 const 迭代器也不答应。这是因为修改键会破坏 map 中元素的有序顺序。

             3、map 迭代器是双向的。

    

      查找元素:

  映射基于所提供的键可以在对数时间内实现元素查找。如果你已经知道映射中有给定键的元素,查找这个元素最简单的方法就是通过 operator[ ] 。operator[ ] 的利益是它会返回一个元素。可以直接应用(如果长短 const 映射,还可以修改)该元素引用,而不必费心要把值从 pair 对象中取出来。以下对象是对前一个例子的拓展,在此对 Data 对象调用了 setVal( ) 方法,并指定键位1.

#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	dataMap[1] = Data(4);
	dataMap[1] = Data(6);//replace the element with key 1
	dataMap[1].setVal(100);

	for(map<int, Data>::iterator it = dataMap.begin(); it !=dataMap.end(); ++it)
	{
		cout<< it->second.getVal()<<endl;
	}
	
	return 0;
}

  不过,如果不知道元素是不是存在,可能不想应用 operator [ ] ,因为如果没有找到给定键的元素,它会基于这个键插入一个新元素。还有一种做法,map 提供了一个 find( ) 方法,如果存在有指定键的元素,它会返回指示这个元素的一个 iterator ,如果 map 中不存在这样的元素,它就会返回 end iterator 。例如:

#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	map <int ,Data> dataMap;
	dataMap[1] = Data(4);
	dataMap[1] = Data(6);//replace the element with key 1
    
	map<int, Data>::iterator it = dataMap.find(1);
	if(it !=dataMap.end())
		(*it).second.setVal(100);
	cout<<(*it).second.getVal()<<endl;
	
	return 0;
}

  

  删除元素

  map 答应在特定迭代器位置删除一个元素,或者删除一个给定迭代器区间中的所有元素。这两个操作的运行时间分别是摊分常量时间和对数时间。从客户的角度看,这两个 erase( ) 方法与顺序容器中的删除方法相称,不过,映射有一个突出的特性,这就是他还提供了另一个版本的 erase ( ) ,可以删除与一个键匹配的元素。

#include<map>
#include<iostream>
using namespace std;

class Data
{
public:
	Data(int val = 0){mVal = val;}
	int getVal() const {return mVal;}
	void setVal(int val){mVal =val;}

protected:
	int mVal;
};

int main()
{
	//#inlcude ,Data class definition ,and begining of main function omitted
	map <int ,Data> dataMap;
	dataMap[1] = Data(4);

	cout<<"There are "<<dataMap.count(1)<< " element with key 1"<<endl;
	dataMap.erase(1);
	cout<<"There are "<<dataMap.count(1)<< " elemeent with key 1"<<endl;
	
	return 0;
}

  没了。

    

文章结束给大家分享下程序员的一些笑话语录: 真正的程序员喜欢兼卖爆米花,他们利用CPU散发出的热量做爆米花,可以根据米花爆裂的速度听出正在运行什么程序。

--------------------------------- 原创文章 By
元素和data
---------------------------------

原文地址:https://www.cnblogs.com/jiangu66/p/3112858.html