STL 详解

set——集合

set<int> STL_set

set为关联容器。为一种体现集合性质的容器。

其中不允许有重复元素。
并且set中的元素是排好序的（升序）。

用法

set<int> STL_set;
//---对整体的操作---
STL_set.clear();	//清空
STL_set.empty();	//返回是否为空
STL_set.size();	//返回元素个数
//---对元素的操作---
STL_set.insert(...);	//在集合中插入元素
STL_set.erase(...);	//删除集合中的元素
STL_set.count(...);	//返回元素的个数【由于set不能存在重复元素，故只能返回0或1
//---迭代器---
STL_set.begin();
STL_set.end();
STL_set.find(...);		//返回一个指向被查找到元素的迭代器，未找到返回set::end()
STL_set.lower_bound(...)	//返回大于等于某值的第一个元素的迭代器
STL_set.upper_bound(...)	//返回大于某个值元素的迭代器

自定义性

set可支持自定义类型，但需要重载<运算符。

struct type   //用来存棋盘状态
{
	...;

	bool operator<(type x) const
	{
		return ...;
	}
}

实现

内部以红黑树的形式实现。

应用场景

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。
同时可以实现数据去重。

衍生STL

multiset: 关键字可重复出现的set。
unordered_set: 未排序的set（用hash函数组织）。
unordered_multiset: 未排序的可重复出现的set。

map——映射

map<int, int> STL_map

map为关联容器。为一种体现映射关系的容器，每个关键字对应一个值。

数据会根据键值大小关系排序（升序）。

数据元素都是成对出现(pair)。
每一对中的第一个值称之为关键字(key)（也称键值），每个关键字只能在map中出现一次。
第二个称之为该关键字的对应值(value)（也称实值）。

用法

map<int, string> STL_map;
//---初始构造---
STL_map = {{1,"a"},{2,"b"}};		//为c++11标准
//---数组操作---
STL_map[25252] = "niconiconi";	//如果没有对应key则插入，如果已经存在则会修改value
//---对整体的操作---
STL_map.clear();
STL_map.empty();
STL_map.size();
//---对元素的操作---
	//insert过于麻烦不予讲解。
STL_map.erase(...);	//删除对应key的元素，成功删除返回1，否则返回0
STL_map.count(...);	//返回对应key元素的个数【由于map不能存在重复key，故只能返回0或1
//---迭代器---
STL_map.begin();
STL_map.end();
STL_map.find(...);	//返回查找元素的迭代器，未找到返回map::end()
STL_map.lower_bound(...)	//返回key大于等于某值的第一个元素的迭代器
STL_map.upper_bound(...)	//返回key大于某个值元素的迭代器

自定义性

set可支持自定义类型，但需要重载<运算符。

struct type   //用来存棋盘状态
{
	...;

	bool operator<(type x) const
	{
		return ...;
	}
}

实现

内部以红黑树的形式实现。

应用场景

hash