【C++】＜知识点＞标准模板库STL（下）

文章目录

六、set与multiset

1. 常用成员函数

2. pair模板

3. set

4. multiset

七、map与multimap

1. map

2. multimap

3. 应用实例

八、容器适配器

1. stack

2. queue

3. priority_queue

九、算法

六、set与multiset

1. 常用成员函数

iterator find(const T& val)	查找值为val的元素，返回其迭代器。若未找到，则返回end()
iterator insert(const T& val)	将val插入容器并返回其迭代器。若set类型对象调用insert，返回值类型为pair<迭代器类型名, bool>
void insert(iterator first, iterator last)	将区间[first, last)插入容器
int count(const T& val)	统计容器内有多少个和val相同的元素
iterator lower_bound(const T& val)	查找最大位置的it，使得[begin, it)中所有元素都比val小
iterator upper_bound(const T& val)	查找最小位置的it，使得[it, end)中所有元素都比val大
pair<iterator, iterator> equal_range(const T& val)	同时求lower_bound和upper_bound
iterator erase(iterator it)	删除it指向的元素，返回其后面元素的迭代器（之后不要再用该迭代器++）。另外，erase函数也有重载，可以删除指定元素，还可以删除指定区间。

2. pair模板

/* pair模板内容 */
template <class _T1, class _T2>
struct pair
{
    typedef _T1 first_type;
    typedef _T2 second_type;
    _T1 first;
    _T2 second;

    pair() : first(), second() {}

    pair(const _T1& _a, const _T1& _b) : first(_a), second(_b) {}

    template <class _U1, class _U2>
    pair(const pair<_U1, _U2>& _p) : first(_p.first), second(_p.second) {}
}

/* 第三个构造函数示例：*/
pair<int, int> p(pair<double, double>(5.5, 4.6));
//则p.first = 5, p.second = 4

/* map/multimap容器里放着的都是pair模板类的对象，并按照first从小到大排序 */

3. set

(1) set类模板：

template < class Key, class Pred = less<Key>, class A = allocator<Key> >
class set{...}

//less模板，通过<比较大小，因此自定义类内要重载<
template <class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) {
        return x < y;
    }
};

(2) 注意：

插入set中已有的元素时，会忽略插入。
当未传入Pred时，默认是按照less从小到大排序。
当传入Pred时，可以按照自定义的排序规则来构建set。
若Key不是基本数据类型，Key类内部要重载运算符<，且形参要写上const否则报错。

(3) 代码示例：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

class Stu {
private:
	int number;
public:
	Stu() :number(0) {}

	Stu(int a) :number(a) {}

	int getNumber() {
		return this->number;
	}

	friend bool operator<(const Stu& s1, const Stu& s2) {
		return s1.number < s2.number;
	}

	friend ostream& operator<<(ostream& cout, const Stu& s) {
		cout << s.number;
		return cout;
	}

	friend void printStu(const set<Stu>& s) {
		set<Stu>::const_iterator i;
		for (i = s.begin(); i != s.end(); ++i) {
			cout << (*i).number << " ";
		}
		cout << endl;
	}
};

int main()
{
	//创建包含Stu类的set
	set<Stu> s;
	s.insert(Stu(10));
	s.insert(Stu(50));
	s.insert(Stu(4));
	s.insert(Stu(18));
	s.insert(Stu(60));
	printStu(s);//4 10 18 50 60
	//set插入重复元素50，不会插入成功
	typedef set<Stu>::iterator IT;
	pair<IT, bool> ret = s.insert(Stu(50));
	if (ret.second) {
		cout << "插入成功！" << endl;
	}
	else {
		cout << "插入失败！" << endl;
	}
	//同时求取lower_bound和upper_bound
	pair<IT, IT> bounds = s.equal_range(20);
	cout << *bounds.first << " " << *bounds.second << endl;//50 50
	//删除元素60
	s.erase(60);//等价于s.erase(Stu(60));
	printStu(s);//4 10 18 50
	return 0;
}

4. multiset

(1) multiset类模板：

template < class Key, class Pred = less<Key>, class A = allocator<Key> >
class multiset{...}

(2) 注意：

multiset允许元素重复，不同于set。
multiset插入元素后只是返回iterator。而set插入可能会失败因此返回pair<iterator, bool>。

(3) 代码示例：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

class Stu {
private:
	int number;
public:
	Stu() :number(0) {}

	Stu(int a) :number(a) {}

	int getNumber() {
		return this->number;
	}

	friend bool operator<(const Stu& s1, const Stu& s2) {
		return s1.number < s2.number;
	}

	friend ostream& operator<<(ostream& cout, const Stu& s) {
		cout << s.number;
		return cout;
	}

	friend void printStu(const multiset<Stu>& s) {
		multiset<Stu>::const_iterator i;
		for (i = s.begin(); i != s.end(); ++i) {
			cout << (*i).number << " ";
		}
		cout << endl;
	}
};

int main()
{
	//创建包含Stu类的set
	multiset<Stu> s;
	s.insert(Stu(10));
	s.insert(Stu(50));
	s.insert(Stu(4));
	s.insert(Stu(18));
	s.insert(Stu(60));
	printStu(s);//4 10 18 50 60
	//set插入重复元素50，会插入成功
	typedef multiset<Stu>::iterator IT;
	IT ret = s.insert(Stu(50));
	if (ret != s.end()) {
		cout << "插入成功！" << endl;
		printStu(s);//4 10 18 50 50 60
	}
	else {
		cout << "插入失败！" << endl;
	}
	//同时求取lower_bound和upper_bound
	pair<IT, IT> bounds = s.equal_range(20);
	cout << *bounds.first << " " << *bounds.second << endl;//50 50
	//删除元素60
	s.erase(60);//等价于s.erase(Stu(60));
	printStu(s);//4 10 18 50 50
	//统计50元素的个数
	cout << s.count(50) << endl;//2
	return 0;
}

七、map与multimap

1. map

(1) map类模板：
template < class Key, class T, class Pred = less<Key>, class A = allocator<Key> >
class map{
    ...
    typedef pair<const Key, T>    value_type;
    ...
}
(2) 注意：

map里面存储的对象都是pair类型的，且按照pair的first成员变量（关键字）来排序。
map不允许有相同的关键字对象。
创建pair类的对象有三种方式：
①pair<int, double>(1, 5.6);
②map<int, double>::value_type(1, 2.6);
③make_pair(1, 4.6);
map实例化的容器对象可以使用"[]"。
"[key]"返回关键字为key的对象引用（若该对象的关键字不存在，则调用无参构造器创建对象）。
"[key] = value"可以修改关键字为key的对象的值为value。

(3) 代码示例：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
using namespace std;

int main()
{
	//创建map对象及添加元素
	typedef map<int, double> mid;
	mid m;
	m.insert(pair<int,double>(15, 2.6));
	m.insert(mid::value_type(26,5.12));//value_type是map内部声明的，等价于pair<int, double>
	m.insert(make_pair(4, -0.25));//make_pair也能创建pair对象
	//迭代器遍历map
	mid::const_iterator p;
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	//添加重复key为15的元素，失败
	pair<mid::const_iterator, bool> insert_ret = m.insert(make_pair(15,8.6));
	if (insert_ret.second) {
		cout << "添加成功" << endl;
	}
	else {
		cout << "添加失败" << endl;
	}
	//使用"[key] = value"修改m中关键字为key的值为value
	m[15] = 8.6;
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	return 0;
}

2. multimap

(1) multimap类模板：

template < class Key, class T, class Pred = less<Key>, class A = allocator<Key> >
class multimap{
    ...
    typedef pair<const Key, T>    value_type;
    ...
}

(2) 注意：

multimap创建的对象与map类似，但是允许有相同关键字对象。
multimap实例化的容器对象不能使用"[]"!
multimap修改指定关键字的元素的值，只能先用find等函数来确定其迭代器p，然后修改其第二个元素p->second = newValue。

(3) 代码示例：

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

int main()
{
	//创建multimap对象及添加元素
	typedef multimap<int, double> mmid;
	mmid m;
	m.insert(pair<int, double>(90, 6.54));
	m.insert(mmid::value_type(48, -0.652));
	m.insert(make_pair(107, 5.14));
	//迭代器遍历multimap
	mmid::const_iterator p;
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	//添加重复元素48，成功
	p = m.insert(make_pair(48, 4.8));
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	//统计关键字为48的元素个数
	cout << m.count(48) << endl;
	//查找关键字为90的元素
	p = m.find(90);
	if (p != m.end()) {
		cout << "找到了：";
		cout << "(" << p->first << ", " << p->second << ") " << endl;
	}
	else {
		cout << "未找到" << endl;
	}
	//删除关键字为48的元素
	m.erase(48);
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	//修改元素key为107的元素的值为5.2
	mmid::iterator modi = m.find(107);
	if (modi != m.end()) {
		modi->second = 5.2;
	}
	for (p = m.begin(); p != m.end(); ++p) {
		cout << "(" << p->first << ", " << p->second << ") ";
	}
	cout << endl;
	return 0;
}

3. 应用实例

【1】题目来源：MOOC--郭炜老师的C++面向对象设计课程。

【2】题目要求：

【3】分析：

因为需要频繁的进行查找操作，因此使用查找快速的数据结构尤为重要。
由于查询的是score，可以将score作为查询的关键字。同时，题目中规定score可以重复，因此采用multimap。
创建一个类Stu，Stu中存在三种属性：姓名、学号和成绩。将score作为multimap的关键字，将姓名和学号作为multimap的值。因此，在Stu类中将姓名和学号再次打包为一个类。

【4】代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <string>
using namespace std;

/* Stu类 */
class Stu {
public:
	class NameID {
	public:
		string name;	//姓名
		int id;			//学号
	};
	//成员变量
	double score;		//成绩
	NameID nameid;		//姓名和学号
};

int main()
{
	//创建multimap容器对象
	multimap<double, Stu::NameID> m;
	//键盘读取数据
	string cmd;
	Stu st;
	while (cin >> cmd) {
		//识别"Add"，往m中添加pair对象
		if (cmd == "Add") {
			cin >> st.nameid.name >> st.nameid.id >> st.score;
			m.insert(make_pair(st.score, st.nameid));
			/*for (multimap<double, Stu::NameID>::iterator p = m.begin(); p != m.end(); ++p) {
				cout << p->second.name << " " << p->second.id << " " << p->first << endl;
			}*/
		}
		//识别"Query"，查找比指定分数低的最高分获得者信息
		else if (cmd == "Query") {
			double score_tmp;
			cin >> score_tmp;
			multimap<double, Stu::NameID>::iterator ret = m.lower_bound(score_tmp);
			if (ret != m.begin()) {//查找成功,若多个分数相同则打印id最高
				--ret;
				multimap<double, Stu::NameID>::iterator it_max = ret;
				double targetScore = ret->first;
				int id_Max = ret->second.id;
				while (ret->first == targetScore) {
					if (ret->second.id > id_Max) {
						id_Max = ret->second.id;
						it_max = ret;
					}
					if (ret == m.begin()) {
						break;
					}
					else {
						--ret;
					}
				}
				cout << it_max->second.name << " " << it_max->second.id << " " << it_max->first << endl;
			}
			else {//查找失败
				cout << "Nobody" << endl;
			}
		}
		else {
			cout << "命令无效，请重新输入！" << endl;
		}
	}
	return 0;
}

八、容器适配器

1. stack

(1) stack类模板：
template < class T, class Cont = deque<T> >
class stack {
    ...
}
(2) 注意：

stack上可以进行push、pop和top操作，针对的都是栈顶元素。
stack可以使用vector、list和deque来实现。stack类模板中第二个参数表示用哪种结构来实现，当不传入时默认是deque实现。

(3) 代码示例：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stack>
using namespace std;

int main()
{
	//创建栈s
	stack<int> s;
	s.push(1);
	s.push(58);
	s.push(34);
	s.push(85);
	//获取栈顶元素
	cout << s.top() << endl;//85
	//弹出栈顶元素
	s.pop();
	cout << s.top() << endl;//34
	return 0;
}

2. queue

(1) queue类模板：
template < class T, class Cont = deque<T> >
class queue {
    ...
}
(2) 注意：

queue可以使用list和deque实现，默认是deque实现。
queue也有pop、push和front操作，但是pop和front操作都针对队头，push针对队尾。
back成员函数可以返回队尾元素的引用。

(3) 代码示例：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;

int main()
{
	//创建单向队列q
	queue<int> q;
	q.push(15);
	q.push(520);
	q.push(1314);
	q.push(666);
	//弹出所有元素，并输出
	while (!q.empty()) {
		cout << q.front() << endl;
		q.pop();
	}
	return 0;
}

3. priority_queue

(1) priority_queue类模板：
template < class T, class Cont = vector<T>, class Compare = less<T> >
class priority_queue {
    ...
}
(2) 注意：

priority_queue可以使用vector和deque实现，默认使用vector实现。
priority_queue底层使用堆排序，保证最大元素总是位于队头。
priority_queue中，push和pop的时间复杂度都是O(log n)。top的时间复杂度为O(1)。
针对总是要获取最大值或最小值的情况，可以考虑使用priority_queue。

(3) 代码示例：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
int main()
{
	//创建优先级队列，将最小的元素放置于队头
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(89);
	pq.push(55);
	pq.push(4);
	pq.push(108);
	//弹出队头，并输出
	while (!pq.empty()) {
		cout << pq.top() << endl;
		pq.pop();
	}
	return 0;
}