STL教程(七)——map

如需转载,请注明出处。

序列容器是管理数据的宝贵工具,但对大多数应用程序而言,序列容器不提供方便的数据访问机制。举个简单的示例,当我们用它处理姓名和地址时,在这种场景下,序列容器可能并不能如我们所愿。一种典型的方法是通过名称来寻找地址。如果记录保存在序列容器中,就只能通过搜索得到这些数据。相比而言,map 容器提供了一种更有效的存储和访问数据的方法。

map 容器是关联容器的一种。在关联容器中,对象的位置取决于和它关联的键的值。键可以是基本类型,也可以是类类型。亚博yabo线上投注经常被用来作为键,如果想要保存姓名和地址的记录,就可以这么使用。名称通常可能是一个或多个亚博yabo线上投注。关联容器中的对象位置的确定取决于容器中的键的类型,而且对于特定容器类型的内部组织方式,不同的?STL?有不同的实现。

map 类模板定义在 map 文件头中,它定义了一个保存 T 类型对象的 map,每个 T 类型的对象都有一个关联的 K 类型的键。容器内对象的位置是通过比较键决定的。可以用适当的键值从 map 容器中检索对象。图 1 展示了一个用名称作为键的 map 容器,对象是整数值,用来表示年龄。

不要因为 map 使用 less 对元素排序就被误导,这些元素并没有被组织成一个简单的有序序列,STL map 容器对元素的组织方式并没有具体要求,但元素一般都会保存在一个平衡二叉树中。容器中的元素被组织成一个平衡二叉树,因而树的高度——根节点和叶节点之间的高度是最低的。如果每个节点的左子树和右子树的高度差不超过 1,那么可以说这棵二叉树就是平衡的。图 2 展示了图 1 所表示的 map 容器可能的平衡二叉树。

图 2 所示的树有 3 层,所以从根节点开始,找到任意的元素最多需要 3 步。这里选择的根节点可以使树的高度最小,而且对于每个父节点来说,它的键值大于它的左子节点,但小于它的右子节点。为了保持二叉树的平衡,当添加一个新的元素时,可能会导致根节点发生改变。所以显然,在添加新元素时,为了保持树的平衡,会产生一些额外的开销。作为回报,容器中的元素越多,相对于线性排列和非平衡树,平衡树组织元素的效率也越高。从包含 n 个元素的平衡二叉树中检索一个随机元素所需的时间为 O(log2n),从序列中检索元素所需的时间为 O(n)。

注意,O(n) 计算时间随着参数的增加而增加。O 被认为是有序的,O(n) 表明线性执行时间在以 n 增加。O(log2n) 计算时间远没有 n 增加得快,因为它是以 log2n 计算的。

与Map相关的一些基本函数:

begin() - 返回map中第一个元素的迭代器
end() - 返回map中最后一个元素后面的理论元素的迭代器
size() - 返回map中元素的数量
max_size() - 返回map可容纳的最大元素数
empty() - 返回map是否为空
insert(keyvalue,mapvalue) - 向map添加新元素
erase(iterator position) - 删除迭代器指向的位置处的元素
erase(const g) - 从map中删除键值“g”
clear() - 从map中删除所有元素

#include  
#include  
#include  

using namespace std; 

int main() 
{ 

	// empty map container 
	map gquiz1; 

	// insert elements in random order 
	gquiz1.insert(pair(1, 40)); 
	gquiz1.insert(pair(2, 30)); 
	gquiz1.insert(pair(3, 60)); 
	gquiz1.insert(pair(4, 20)); 
	gquiz1.insert(pair(5, 50)); 
	gquiz1.insert(pair(6, 50)); 
	gquiz1.insert(pair(7, 10)); 

	// printing map gquiz1 
	map::iterator itr; 
	cout << "\nThe map gquiz1 is : \n"; 
	cout << "\tKEY\tELEMENT\n"; 
	for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) { 
		cout << '\t' << itr->first 
			<< '\t' << itr->second << '\n'; 
	} 
	cout << endl; 

	// assigning the elements from gquiz1 to gquiz2 
	map gquiz2(gquiz1.begin(), gquiz1.end()); 

	// print all elements of the map gquiz2 
	cout << "\nThe map gquiz2 after"
		<< " assign from gquiz1 is : \n"; 
	cout << "\tKEY\tELEMENT\n"; 
	for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
		cout << '\t' << itr->first 
			<< '\t' << itr->second << '\n'; 
	} 
	cout << endl; 

	// remove all elements up to 
	// element with key=3 in gquiz2 
	cout << "\ngquiz2 after removal of"
			" elements less than key=3 : \n"; 
	cout << "\tKEY\tELEMENT\n"; 
	gquiz2.erase(gquiz2.begin(), gquiz2.find(3)); 
	for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
		cout << '\t' << itr->first 
			<< '\t' << itr->second << '\n'; 
	} 

	// remove all elements with key = 4 
	int num; 
	num = gquiz2.erase(4); 
	cout << "\ngquiz2.erase(4) : "; 
	cout << num << " removed \n"; 
	cout << "\tKEY\tELEMENT\n"; 
	for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
		cout << '\t' << itr->first 
			<< '\t' << itr->second << '\n'; 
	} 

	cout << endl; 

	// lower bound and upper bound for map gquiz1 key = 5 
	cout << "gquiz1.lower_bound(5) : "
		<< "\tKEY = "; 
	cout << gquiz1.lower_bound(5)->first << '\t'; 
	cout << "\tELEMENT = "
		<< gquiz1.lower_bound(5)->second << endl; 
	cout << "gquiz1.upper_bound(5) : "
		<< "\tKEY = "; 
	cout << gquiz1.upper_bound(5)->first << '\t'; 
	cout << "\tELEMENT = "
		<< gquiz1.upper_bound(5)->second << endl; 

	return 0; 
} 

输出:

The map gquiz1 is : 
	KEY	ELEMENT
	1	40
	2	30
	3	60
	4	20
	5	50
	6	50
	7	10


The map gquiz2 after assign from gquiz1 is : 
	KEY	ELEMENT
	1	40
	2	30
	3	60
	4	20
	5	50
	6	50
	7	10


gquiz2 after removal of elements less than key=3 : 
	KEY	ELEMENT
	3	60
	4	20
	5	50
	6	50
	7	10

gquiz2.erase(4) : 1 removed 
	KEY	ELEMENT
	3	60
	5	50
	6	50
	7	10

gquiz1.lower_bound(5) : 	KEY = 5		ELEMENT = 50
gquiz1.upper_bound(5) : 	KEY = 6		ELEMENT = 50

Map的所有函数列表:

insert()-在map容器中插入具有特定键的元素。 。
count()-返回映射中键值为'g'的元素的匹配数。
equal_range()-返回对的迭代器。该对指的是一个范围的边界,该范围包括容器中具有等于k的键的所有元素。
erase()-用于从容器中擦除元素。
rend()-返回一个反向迭代器,它指向映射中第一个键值对之前的理论元素(被认为是它的反向结束)。
rbegin()-返回一个反向迭代器,它指向map的最后一个元素。
find()- 如果找到,则返回映射中具有键值“g”的元素的迭代器,否则返回迭代器结束。
crbegin()返回一个常量反向迭代器,引用映射容器中的最后一个元素。

crend()返回一个常量反向迭代器,指向map中第一个元素之前的理论元素。
cbegin()返回一个引用映射容器中第一个元素的常量迭代器。

cend()返回一个常量迭代器,指向multimap中最后一个元素后面的理论元素。
emplace() - 将键及其元素插入映射容器中。
max_size()-返回map容器可容纳的最大元素数。
upper_bound()- 返回第一个元素的迭代器,该元素等效于具有键值'g'的映射值,或者肯定会在map中具有键值'g'的元素之后返回
operator = -将容器的内容分配给不同的容器,替换其当前内容。
lower_bound()- 返回第一个元素的迭代器,该元素等效于具有键值'g'的映射值,或者肯定不会在映射中具有键值'g'的元素之前。
emplace_hint()- 使用给定的提示将键及其元素插入到映射容器中。
value_comp()-返回确定map中元素排序方式的对象(默认情况下为“<”)。
key_comp()函数STL-返回确定map中元素排序方式的对象(默认情况下为“<”)。
size()-返回map中元素的数量。
empty()-返回map是否为空。
begin()返回映射中第一个元素的迭代器。

end()将迭代器返回到map中最后一个元素后面的理论元素
operator [] -此运算符用于引用运算符内给定位置的元素。
clear()-从地图中删除所有元素。
at()函数用于返回与键k相关联的元素的引用。

swap()函数用于交换两个映射的内容,但映射必须是相同的类型,尽管大小可能不同。