深拷贝、shared_ptr、memory context
map、pair 的应用
收获很大的一次作业 qvq

# Homework4 - 内存管理相关

# 编写深拷贝容器

基于我们给的代码框架，编写一个容器 MyContainer，用该容器维护一个堆内存上的数组

该内存容器是一个典型的 RAII 容器，通过这个练习学习如何使用 RAII 来安全管理资源

	#include <iostream>
	using namespace std;

	class MyContainer {
	public:
	MyContainer(int size) : _size(size) {
	_data = new int[size];
	_count ++;
	}

	~MyContainer() {
	if(_data != nullptr){
	delete[] _data;
	_data = nullptr;// 防止二次释放
	}
	_count --;
	}

	MyContainer(const MyContainer &Other) {
	_data = new int(Other._size);
	for(int i = 0; i < Other._size; i++){
	_data[i] = Other._data[i];
	}
	_size = Other._size;
	_count ++;
	}

	MyContainer &operator=(const MyContainer &Other){
	if (this != &Other){
	delete[] _data;
	_size = Other._size;
	_data = new int[_size];
	copy(Other._data, Other._data + _size, _data);
	}
	return *this;
	}

	// 去掉了参数当中的 const，写了另外一个版本，没有考虑自己 move 给自己的情况，不然会丢失数据……
	//log：看错题目了，这个函数实现的是拷贝赋值不是移动构造，那没事了
	MyContainer &operator=(MyContainer &Other){
	_size = Other._size;
	_data = Other._data;
	Other._data = nullptr;
	Other._size = 0;
	return *this;
	}

	int size() const {
	return _size;
	}

	int* data() const {
	return _data;
	}

	static int count() {
	return _count;
	}

	static int _count;

	private:
	// C++11 引入的 initializer_list
	int *_data{nullptr};
	int _size{0};
	};

	int MyContainer::_count = 0;

	void test1(){
	MyContainer m(5);
	std::cout << m.count() << std::endl;

	MyContainer m2(m);
	std::cout << m2.count() << std::endl;

	MyContainer m3 = m2;
	std::cout << m3.count() << std::endl;
	}
	// 1 2 3

	void test2(){
	MyContainer m1(5);
	std::cout << m1.count() << std::endl;

	MyContainer m2 = m1;
	std::cout << m2.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;
	}
	// 1 2 0

	void test3(){
	MyContainer m1(3);
	std::cout << m1.count() << std::endl;

	MyContainer m2 = m1;//copy
	std::cout << m2.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	m1 = m2;// 赋值
	std::cout << m1.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	m2 = m1;// 赋值
	std::cout << m2.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	int * prev_ptr = m1.data();
	m1 = m1;// 赋值
	std::cout << m1.count() << std::endl;
	std::cout << (m1.data() == prev_ptr) << std::endl;

	}
	// 1 2 0 2 0 2 0 2 1

	void test4(){
	MyContainer m1(3);
	std::cout << m1.count() << std::endl;

	{
	MyContainer m2 = m1;
	std::cout << m2.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	m1 = m2;
	std::cout << m1.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	m2 = m1;
	std::cout << m2.count() << std::endl;
	std::cout << (m2.data() == m1.data()) << std::endl;

	}

	std::cout << m1.count() << std::endl;
	}
	// 1 2 0 2 0 2 0 1

	int main(){
	test1();
	test2();
	test3();
	test4();
	return 0;
	}

# 析构函数

无参数、无返回值、不能重载

离开作用域后自动销毁

释放空间时记得将指针设为 nullptr，防止出现多次释放和悬挂指针的情况

# 拷贝构造函数

一个对象，多个副本，副本之间是独立的关系。

创建对象时，用一同类的对象对其初始化的时候进行调用。

复制拷贝构造、传参拷贝构造、返回值拷贝构造

# 移动构造函数

移动构造函数移动堆中的资源，即不像复制构造函数复制现有对象的数据并将其分配给新对象移动构造函数只是使声明对象的指针指向临时对象的数据并清空临时对象的指针。因此，移动构造函数可以防止在内存中不必要地复制数据。

移动构造函数的工作看起来有点像默认的成员复制构造函数，但在这种情况下，它会清空临时对象的指针，防止多个对象指向同一内存位置。

# 扩展学习

# explicit 关键字

指定构造函数或转换函数 (C++11 起) 为显式，即它不能用于隐式转换和复制初始化.
explicit 指定符可以与常量表达式一同使用。函数若且唯若该常量表达式求值为 true 才为显式. (C++20 起)

构造函数为什么会使用 explicit 关键字进行标注

如果不使用 explicit，对于 MyContainer m = 10 ，编译器会进行隐式类型转换，此时程序的行为可能不符合我们预期
有的时候利用 explicit 的特性可以帮助我们简化代码，但可能会对可读性造成影响

# 成员变量定义时为什么加上

这是一个好习惯，可以防止一些因未初始化问题导致的难以分析的 bug

	int *_data{nullptr};
	int _size{0};

# 可以尝试在构造函数、拷贝构造、拷贝赋值中插入打印语句，查看下列代码的输出

# OO 优化

MyContainer get(){
  MyContainer m {1};
  return m;
}
int main(){
  MyContainer m = get();
  return 0;
}

可以先猜测一下共输出多少语句，再运行程序
- 拷贝了 1 次？2 次？3 次？
- 我在 x86-64 gcc 7.5 上用 - O0 优化的输出结果中，并没有任何拷贝的发生，只有一次构造和一次析构
  cxy 的测试，输出结果如下：
  create my container!
  destroy my container!
如果实际输出的结果比你预想的要少，可以查看以下链接进一步了解
- https://stackoverflow.com/questions/12953127/what-are-copy-elision-and-return-value-optimization
  copy elision 拷贝的省略
  Copy elision is an optimization implemented by most compilers to prevent extra (potentially expensive) copies in certain situations. It makes returning by value or pass-by-value feasible 可行的 in practice (restrictions apply 限制应用).

# 报错

free(): double free detected in tcache 2
free（）：在 tcache 2 中检测到双空闲，在执行程序的过程中对同一块内存单元进行了两次 free () 操作

# 操作符重载

对于系统的所有操作符，一般情况下，只支持基本数据类型和标准库中提供的 class，对于用户自己定义的 class，如果想支持基本操作，比如比较大小，判断是否相等，等等，则需要用户自己来定义关于这个操作符的具体实现。

https://www.cnblogs.com/ZY-Dream/p/10068993.html

# 引用计数的共享内存容器 Shared Container

目标

基于我们给的代码框架，编写一个容器 SharedContainer，用该容器维护一个堆内存上的 Content 对象。

这个堆内存上的对象可被一个或多个 SharedContainer 所共享，当没有 SharedContainer 持有这个对象的话，则销毁这个对象。

	#include <iostream>

	class Content {
	public:
	explicit Content(int id) : id(id) {
	std::cout << "create " << std::to_string(id) << std::endl;
	}

	~Content() {
	std::cout << "destroy " << std::to_string(id) << std::endl;
	}

	private:
	int id{-1};
	char data[1024]{};
	};

	class SharedContainer {
	public:
	//TODO
	explicit SharedContainer(int mem_id){
	_data = new Content(mem_id);
	_ref_count = new int[1];
	*_ref_count = 1;
	}
	//TODO
	~SharedContainer(){
	_ref_count = _ref_count - 1;
	if(*_ref_count <= 0){
	if(_data != nullptr) {
	delete _data;
	_data = nullptr;
	}
	}
	}
	//TODO
	SharedContainer(const SharedContainer &other){
	_data = other._data;
	_ref_count = other._ref_count;
	_ref_count = _ref_count + 1;
	}
	//TODO
	SharedContainer& operator=(const SharedContainer &other){
	if(this != &other){
	_ref_count = _ref_count - 1;
	if(*_ref_count <= 0) delete _data;
	}
	_data = other._data;
	_ref_count = other._ref_count;
	if(this != &other){
	_ref_count = _ref_count + 1;
	}
	return *this;
	}
	//TODO
	int get_count() const{
	return *_ref_count;
	}

	SharedContainer(const SharedContainer &&) = delete;
	SharedContainer &operator=(const SharedContainer &&) = delete;

	private:
	Content *_data{nullptr};
	int *_ref_count{nullptr};
	//TODO: design your own reference counting mechanism

	};

	void test1(){
	SharedContainer m1(1);
	SharedContainer m2 = m1;
	SharedContainer m3(m2);
	std::cout << m1.get_count() << std::endl;
	std::cout << m2.get_count() << std::endl;
	std::cout << m3.get_count() << std::endl;
	}

	void test2(){
	SharedContainer m1(1);
	SharedContainer m2 = m1;
	m1 = m1;// 需要考虑拷贝构造的时候，自己给自己赋值的情况
	{
	SharedContainer m3 = m1;
	std::cout << m1.get_count() << std::endl;
	}
	std::cout << m1.get_count() << std::endl;
	std::cout << m2.get_count() << std::endl;
	}

	void test3(){
	SharedContainer m1(1);
	SharedContainer m2(2);
	m1 = m2;
	std::cout << m1.get_count() << std::endl;
	std::cout << m2.get_count() << std::endl;
	{
	SharedContainer m3(3);
	m1 = m3;// 此时已经没有指向 Content1 的指针，应该手动销毁
	std::cout << m1.get_count() << std::endl;
	std::cout << m2.get_count() << std::endl;
	std::cout << m3.get_count() << std::endl;
	}
	std::cout << m1.get_count() << std::endl;
	std::cout << m2.get_count() << std::endl;

	}

	int main(){
	test1();
	test2();
	test3();
	return 0;
	}

# 扩展学习【待查看】

思考如何扩展本练习中的共享内存容器，以支持对任意类型内存的共享
- 请参考 shared_ptr 的基本原理，可能需要一些模板编程的知识
有了 shared_ptr，我们是不是可以只需要创建资源，剩下的都交给 shared_ptr 管理
- shared_ptr 可能产生循环引用而导致的内存泄漏
- shared_ptr 的额外性能开销
  - 标准库的 shared_ptr 不是线程安全的
shared_ptr 既然能清理不被使用的内存，那么垃圾收集又是什么？
- 前者回收资源是 eager 的；后者回收资源是 lazy 的
- 前者有循环引用问题；后者没有
- ...

# 智能指针的简介

垃圾回收机制已经大行其道，得到了诸多编程语言的支持，例如 Java、Python、C#、PHP 等。而 C++ 虽然从来没有公开得支持过垃圾回收机制，但 C98/03 标准中，支持使用 auto_ptr 智能指针来实现堆内存的自动回收；C11 新标准在废弃 auto_ptr 的同时，增添了 unique_ptr、shared_ptr 以及 weak_ptr 这 3 个智能指针来实现堆内存的自动回收。

相较于普通指针，智能指针可以在适当时机自动释放分配的内存。

C++ 智能指针底层是采用引用计数的方式实现的。

均可直接参考 cppreference。

# shared_ptr

http://c.biancheng.net/view/7898.html

	std::shared_ptr<int> p1; // 不传入任何实参
	std::shared_ptr<int> p2(nullptr); // 传入空指针 nullptr, 指向空指针，计数为 0
	std::shared_ptr<int> p3(new int(10)); // 明确指向
	// 调用拷贝构造函数
	std::shared_ptr<int> p4(p3);// 或者 std::shared_ptr<int> p4 = p3;
	// 调用移动构造函数
	std::shared_ptr<int> p5(std::move(p4)); // 或者 std::shared_ptr<int> p5 = std::move (p4);

空的 shared_ptr 指针，其初始引用计数为 0，而不是 1。

同一普通指针不能同时为多个 shared_ptr 对象赋值，否则会导致程序发生异常。

在初始化 shared_ptr 智能指针时，还可以自定义所指堆内存的释放规则。对于申请的动态数组来说，shared_ptr 指针默认的释放规则是不支持释放数组的，只能自定义对应的释放规则，才能正确地释放申请的堆内存。

# unique_ptr

https://xhy3054.github.io/cpp-unique-ptr/

unique_ptr 内部存储一个内置指针，当 unique_ptr 析构时，它的析构函数将会负责析构它持有的对象。
unique_ptr 提供了 operator*() 和 operator->() 成员函数，像内置指针一样，我们可以使用 * 解引用 unique_ptr，使用 -> 来访问 unique_ptr 所持有对象的成员。
unique_ptr 并不提供 copy 操作，这是为了防止多个 unique_ptr 指向同一对象。
但 unique_ptr 提供了 move 操作，因此我们可以用 std::move() 来转移 unique_ptr。

# weak_ptr

weak_ptr 是为了配合 shared_ptr 而引入的一种智能指针，它指向一个由 shared_ptr 管理的对象而不影响所指对象的生命周期，也就是将一个 weak_ptr 绑定到一个 shared_ptr 不会改变 shared_ptr 的引用计数。不论是否有 weak_ptr 指向，一旦最后一个指向对象的 shared_ptr 被销毁，对象就会被释放。从这个角度看，weak_ptr 更像是 shared_ptr 的一个助手而不是智能指针。

我们不能使用 weak_ptr 直接访问对象。那么我们如何判断 weak_ptr 指向对象是否存在呢？C++ 中提供了 lock 函数来实现该功能。如果对象存在，lock () 函数返回一个指向共享对象的 shared_ptr，否则返回一个空 shared_ptr。

# *pointer 指针还是地址自增？

https://stackoverflow.com/questions/8208021/how-to-increment-a-pointer-address-and-pointers-value

(*ptr)++; // The value pointed at by ptr is incremented

注意 operator precedence—— the ++ operator takes precedence over the * operator, and the () operators take precedence over everything else.

# 内存管理 memory context (MC)

主要考察析构函数

由于 libc 原生的内存管理 API 的种种问题（例如，内存泄露和 double-free），某些数据库管理系统基于这些 API 实现了新的动态内存管理机制。具体地，这些实现中引入了一个称为 “memory context” 的概念（后文简称为 “MC”），动态内存管理不再直接使用 malloc / free 等函数，而是调用某个 MC 对象提供的 API 进行。这些 MC 对象被组织为树状结构，如图 1 所示。这样，使用者不再需要为之前分配的每个内存块调用 free 等函数，而是等到相应的 MC 对象被销毁时统一地归还其下的动态内存。同时，由于树状结构的存在，在销毁较为高层的 MC 对象时，处于低层次的 MC 对象也同样会被销毁。这种机制极大降低了管理动态内存的心智负担，更好地避免了内存泄露和 double-free 等问题。

可参考 Homework4 中 “内存管理” 的 pdf

经过分析，用左子树表示子节点，用右子树表示兄弟节点构造树的结构。

“如果一个 MC 有多个子 MC，那么按照创建这些子 MC 的顺序进行销毁”-》可以看出应该采用后序遍历

“如果一个 MC 下的内存块，按照分配顺序的逆序（即，后进先出）的顺序进行销毁”-》可以看出用 stack 的数据结构模拟

	#include <cassert>
	#include <functional>
	#include <iostream>
	#include <memory>
	#include <string>
	#include <unordered_map>
	#include <vector>
	#include <stack>
	using namespace std;

	// 除了 TODO 标出的部分，不要修改原有的声明和定义，否则后果自负！

	class MemoryContext {
	public:
	/**
	* @param parent 父节点，可能为 nullptr
	*/
	MemoryContext(MemoryContext *parent);

	~MemoryContext();

	// 禁止拷贝和移动
	MemoryContext(const MemoryContext &) = delete;
	MemoryContext &operator=(const MemoryContext &) = delete;
	MemoryContext(MemoryContext &&) = delete;
	MemoryContext &operator=(MemoryContext &&) = delete;

	using chunk_id_t = std::string;

	void alloc(const chunk_id_t &chunk_id);

	void release(MemoryContext * ptr);

	private:
	// TODO: your code
	MemoryContext * parentMC;
	MemoryContext * leftMC;// 子节点
	MemoryContext * rightMC;// 兄弟节点
	stack<chunk_id_t> chunk;

	};

	MemoryContext::MemoryContext(MemoryContext *parent) {
	// TODO: your code
	parentMC = parent;
	leftMC = nullptr;
	rightMC = nullptr;

	if(parentMC != nullptr){
	MemoryContext * tmp = parent->leftMC;
	if(tmp == nullptr){
	parent -> leftMC = this;
	}else{
	while(tmp -> rightMC != nullptr){
	tmp = tmp->rightMC;
	}
	tmp -> rightMC = this;
	}
	}
	}

	MemoryContext::~MemoryContext() {
	// TODO: your code
	MemoryContext * pointer = this;
	if(pointer == nullptr) return;
	while(pointer->parentMC != nullptr){
	pointer = pointer -> parentMC;
	}
	MemoryContext::release(pointer);
	}

	void MemoryContext::release(MemoryContext * ptr){
	if(ptr == nullptr) return;
	MemoryContext * child = ptr->leftMC;
	MemoryContext * next = nullptr;
	while(child != nullptr){
	release(child);
	next = child -> rightMC;
	// delete child;
	child = next;
	}
	chunk_id_t str = "";
	while(!ptr->chunk.empty()){
	str = ptr->chunk.top();
	ptr->chunk.pop();
	cout << "Chunk " + str + " freed." <<endl;
	}
	}



	void MemoryContext::alloc(const chunk_id_t &chunk_id) {
	chunk.push(chunk_id);
	}

	void test_1() {
	std::unique_ptr<MemoryContext> A = std::make_unique<MemoryContext>(nullptr);
	A->alloc("1");
	A->alloc("2");
	A->alloc("3");
	}

	void test_2() {
	std::unique_ptr<MemoryContext> A = std::make_unique<MemoryContext>(nullptr);
	MemoryContext *B = new MemoryContext(A.get());
	MemoryContext *C = new MemoryContext(B);

	A->alloc("1");
	A->alloc("2");
	A->alloc("3");
	B->alloc("1/1");
	B->alloc("1/2");
	B->alloc("1/3");
	C->alloc("1/1/1");
	C->alloc("1/1/2");
	C->alloc("1/1/3");
	}

	void test_3() {
	std::unique_ptr<MemoryContext> A = std::make_unique<MemoryContext>(nullptr);
	MemoryContext *B = new MemoryContext(A.get());
	MemoryContext *C = new MemoryContext(A.get());
	MemoryContext *D = new MemoryContext(B);
	MemoryContext *E = new MemoryContext(C);
	MemoryContext *F = new MemoryContext(C);
	MemoryContext *G = new MemoryContext(E);

	A->alloc("1");
	A->alloc("2");
	A->alloc("3");
	B->alloc("1/1");
	C->alloc("1/2");
	D->alloc("1/1/1");
	D->alloc("1/1/2");
	G->alloc("1/2/1/1");
	}

	void test_4() {
	std::unique_ptr<MemoryContext> A = std::make_unique<MemoryContext>(nullptr);
	MemoryContext *B = new MemoryContext(A.get());
	MemoryContext *C = new MemoryContext(A.get());
	MemoryContext *D = new MemoryContext(B);
	MemoryContext *E = new MemoryContext(B);
	MemoryContext *F = new MemoryContext(C);
	MemoryContext *G = new MemoryContext(C);

	A->alloc("1");
	A->alloc("2");
	A->alloc("3");
	B->alloc("1/1");
	C->alloc("1/2");
	D->alloc("1/1/1");
	D->alloc("1/1/3");
	E->alloc("1/1/2");
	F->alloc("1/2/1");
	G->alloc("1/2/3");
	G->alloc("1/2/5");
	G->alloc("1/2/2");
	G->alloc("1/2/4");
	}

	void test_5() {
	std::unique_ptr<MemoryContext> A = std::make_unique<MemoryContext>(nullptr);
	MemoryContext *B = new MemoryContext(A.get());
	MemoryContext *C = new MemoryContext(A.get());
	MemoryContext *D = new MemoryContext(B);
	MemoryContext *G = new MemoryContext(C);

	A->alloc("2");
	A->alloc("1");
	A->alloc("3");
	A->alloc("4");
	B->alloc("2/1");
	B->alloc("3/5");
	C->alloc("1024/2");
	C->alloc("1024/1");
	G->alloc("8192/1/4095");
	}

	#define REGISTER_TEST_CASE(name) \
	{ #name, name }

	int main() {
	std::unordered_map<std::string, std::function<void()>>
	test_functions_by_name = {
	REGISTER_TEST_CASE(test_1), REGISTER_TEST_CASE(test_2),
	REGISTER_TEST_CASE(test_3), REGISTER_TEST_CASE(test_4),
	REGISTER_TEST_CASE(test_5),
	};

	std::string test_case_name;
	std::cin >> test_case_name;
	auto it = test_functions_by_name.find(test_case_name);
	assert(it != test_functions_by_name.end());
	auto fn = it->second;
	fn();
	}

	// 摸了 1h30min 但是不是很懂

# cpp 中 this 的理解

在 C++ 中，每一个对象都能通过 this 指针来访问自己的地址。this 指针是所有成员函数的隐含参数。因此，在成员函数内部，它可以用来指向调用对象。

# stack

pop 不返回参数，只是弹出

需要用 top 函数进行顶层元素的访问

# 报错

basic_string::_M_construct null not valid 错误的原因

将 String 初始化为 NULL，这显然是非常降智的

# UI 设计

公司 A 开发设计软件。请逐步实现功能。

具体可参见 UI.pdf

	// 改代码的 group 功能有些问题，无法正常访问

	#include<iostream>
	#include<string>
	#include<vector>
	#include<algorithm>

	using namespace std;

	struct rectangle{
	string id;
	int red;
	int green;
	int blue;
	string type;
	double grey;
	};

	struct group{
	vector<rectangle *> mem;
	string gid;
	};

	bool cmp1(rectangle a, rectangle b){
	int aid = stoi(a.id.substr(1));
	int bid = stoi(b.id.substr(1));
	if(aid < bid){
	return true;
	}else{
	return false;
	}
	}

	bool cmp2(rectangle a, rectangle b){
	double agrey = a.grey;
	double bgrey = b.grey;
	if(agrey < bgrey){
	return true;
	}else if(agrey > bgrey){
	return false;
	}else{
	return cmp1(a,b);
	}
	}

	vector<string> split(string str){
	string delimiter = " ";
	size_t pos = 0;
	string token;
	vector<string> ret;
	while((pos = str.find(delimiter)) != std::string::npos){
	token = str.substr(0, pos);
	if(!token.empty()) ret.push_back(token);
	str.erase(0, pos+delimiter.length());
	}
	ret.push_back(str);
	return ret;
	}


	int main(){
	int n;
	cin >> n;
	cin >> ws;
	vector<rectangle> rec;
	vector<group> grp;
	vector<string> op;
	string operation;

	while(n--){
	getline(cin, operation);
	op = split(operation);
	if(op[0] == "Add"){
	rectangle foo;
	foo.type = op[1];
	foo.id = op[2];
	foo.red = 0;
	foo.green = 0;
	foo.blue = 0;
	foo.grey = 0;
	rec.push_back(foo);
	}else if(op[0] == "Group"){
	int num = stoi(op[1]);
	group foo;
	foo.gid = op[op.size() - 1];
	for(int i = 2; i < 2 + num; i++){
	for(auto& item : rec){
	if(item.id == op[i]){
	foo.mem.push_back(&item);
	break;
	}
	}
	}
	grp.push_back(foo);
	}else if(op[0] == "Set"){
	if(op[1].substr(0,1) == "P"){
	for(auto &item: rec){
	if(item.id == op[1]){
	if(item.type == "normal"){
	item.red = stoi(op[2]);
	item.green = stoi(op[3]);
	item.blue = stoi(op[4]);
	}else if(item.type == "reverse"){
	item.red = 255 - stoi(op[2]);
	item.green = 255 - stoi(op[3]);
	item.blue = 255 -stoi(op[4]);
	}else{
	item.red = stoi(op[2]);
	item.green = 0;
	item.blue = 0;
	}
	break;
	}
	}
	}else{
	for(auto &gp: grp){
	if(gp.gid == op[1]){
	for(auto &item: gp.mem){
	if(item->type == "normal"){
	item->red = stoi(op[2]);
	item->green = stoi(op[3]);
	item->blue = stoi(op[4]);
	}else if(item->type == "reverse"){
	item->red = 255 - stoi(op[2]);
	item->green = 255 - stoi(op[3]);
	item->blue = 255 -stoi(op[4]);
	}else{
	item->red = stoi(op[2]);
	item->green = 0;
	item->blue = 0;
	}
	}
	break;
	}
	}
	}

	}
	}

	getline(cin, operation);
	if(operation == "Normal"){
	sort(rec.begin(), rec.end(), cmp1);
	}else if(operation == "Gray"){
	for(auto &item:rec){
	item.grey = item.red * 0.299 + item.green * 0.587 + item.blue * 0.114;
	}
	sort(rec.begin(), rec.end(), cmp2);
	}
	for(auto &item:rec){
	cout << item.id <<" " << item.red << " "<< item.green << " "<< item.blue <<endl;
	}

	for(auto &item: rec){
	cout << item.type << endl;
	}

	for(auto &gp: grp){
	cout << gp.gid << endl;
	for(auto &item:gp.mem){
	cout << item->type << endl;
	}
	for(int i = 0; i < gp.mem.size(); i++){
	cout << gp.mem[i]->type << endl;
	}
	}

	}

	// 抽象了一个 set 函数，缩了 20 行

	#include<iostream>
	#include<string>
	#include<vector>
	#include<algorithm>

	using namespace std;

	struct rectangle{
	string id;
	int red;
	int green;
	int blue;
	string type;

	rectangle():id(""),red(0), green(0),blue(0), type(""){};//struct 的初始化

	double grey(){
	return red * 0.299 + green * 0.587 + blue * 0.114;
	}

	//set 归 set，初始化归初始化
	void set(int r, int g, int b){
	red = r; green = g; blue = b;
	if(type == "reverse"){
	red = 255 - r;
	green = 255 - g;
	blue = 255 - b;
	}else if(type == "single"){
	green = 0;
	blue = 0;
	}
	}
	};

	struct group{
	vector<string> mem;
	string gid;
	};

	bool cmp1(rectangle a, rectangle b){
	int aid = stoi(a.id.substr(1));
	int bid = stoi(b.id.substr(1));
	if(aid < bid){
	return true;
	}else{
	return false;
	}
	}

	bool cmp2(rectangle a, rectangle b){
	if(a.grey() < b.grey()){
	return true;
	}else if(a.grey() > b.grey()){
	return false;
	}else{
	return cmp1(a,b);
	}
	}

	vector<string> split(string str){
	string delimiter = " ";
	size_t pos = 0;
	string token;
	vector<string> ret;
	while((pos = str.find(delimiter)) != std::string::npos){
	token = str.substr(0, pos);
	if(!token.empty()) ret.push_back(token);
	str.erase(0, pos+delimiter.length());
	}
	ret.push_back(str);
	return ret;
	}


	int main(){
	int n;
	cin >> n;
	cin >> ws;
	vector<rectangle> rec;
	vector<group> grp;
	vector<string> op;
	string operation;

	while(n--){
	getline(cin, operation);
	op = split(operation);
	if(op[0] == "Add"){
	rectangle foo;
	foo.type = op[1];
	foo.id = op[2];
	rec.push_back(foo);
	}else if(op[0] == "Group"){
	int num = stoi(op[1]);
	group foo;
	foo.gid = op[op.size() - 1];
	for(int i = 2; i < 2 + num; i++){
	for(auto& item : rec){
	if(item.id == op[i]){
	foo.mem.push_back(item.id);
	break;
	}
	}
	}
	grp.push_back(foo);
	}else if(op[0] == "Set"){
	if(op[1].substr(0,1) == "P"){
	for(auto &item: rec){
	if(item.id == op[1]){
	item.set(stoi(op[2]), stoi(op[3]), stoi(op[4]));
	break;
	}
	}
	}else{
	for(auto &gp: grp){
	if(gp.gid == op[1]){
	vector<string> gpmem = gp.mem;
	for(int i = 0; i < gpmem.size(); i++){
	for(auto &item: rec){
	if(item.id == gpmem[i]){
	item.set(stoi(op[2]), stoi(op[3]), stoi(op[4]));
	break;
	}
	}
	}
	}
	}
	}
	}
	}
	getline(cin, operation);
	if(operation == "Normal"){
	sort(rec.begin(), rec.end(), cmp1);
	}else if(operation == "Gray"){
	sort(rec.begin(), rec.end(), cmp2);
	}
	for(auto &item:rec){
	cout << item.id <<" " << item.red << " "<< item.green << " "<< item.blue <<endl;
	}
	}

	// 佬的代码

	#include <bits/stdc++.h>

	using namespace std;

	struct RECT {
	string type;
	int R;
	int G;
	int B;

	// 将 set 的函数抽象出来重复调用
	void set(int r, int g, int b) {
	R = r; G = g; B = b;

	if (type == "reverse") {
	R = 255 - R;
	G = 255 - G;
	B = 255 - B;
	} else if (type == "single") {
	G = 0;
	B = 0;
	}
	}

	// 不用单独存一个 gray 的量，用函数进行比较
	double gray() {
	return R0.299 + G0.587 + B*0.114;
	}
	};

	bool cmpgray(pair<int, RECT> a, pair<int, RECT> b) {
	if (a.second.gray() == b.second.gray()) {
	return a.first < b.first;
	}
	return a.second.gray() < b.second.gray();
	}

	bool cmpi(pair<int, RECT> a, pair<int, RECT> b) {
	return a.first < b.first;
	}

	map<int, vector<int>> groups;
	map<int, RECT> rects;

	int main() {


	int N;
	cin >> N;
	while (N--) {
	string cmd;
	cin >> cmd;

	if (cmd == "Add") {
	RECT tmp{};
	cin >> tmp.type;
	int id;
	scanf(" P%d", &id);
	rects[id] = tmp;
	} else if (cmd == "Set") {
	int id;
	if (scanf(" P%d", &id) == 1) {
	int r, g, b;
	cin >> r >> g >> b;
	rects[id].set(r, g, b);
	} else {
	scanf(" G%d", &id);

	vector<int> gr = groups[id];
	int r, g, b;
	cin >> r >> g >> b;
	for (int i: gr) {
	rects[i].set(r, g, b);
	}
	}

	} else if (cmd == "Group") {
	int N1;
	cin >> N1;
	vector<int> tmp;
	while (N1 --) {
	int t;
	scanf(" P%d", &t);
	tmp.push_back(t);
	}

	int gid;
	scanf(" G%d", &gid);
	groups[gid] = tmp;
	}
	}

	string o;
	cin >> o;

	vector<pair<int, RECT>> outputs;

	for (pair<const int, RECT> r: rects) {
	outputs.push_back(r);
	}

	if (o == "Normal") {
	sort(outputs.begin(), outputs.end(), cmpi);
	} else {
	sort(outputs.begin(), outputs.end(), cmpgray);
	}

	for (pair<const int, RECT> r: outputs) {
	cout << "P" << r.first << " " << r.second.R << " " << r.second.G << " " << r.second.B << endl;
	}

	return 0;
	}

# struct

struct 默认成员函数是 public 的

struct 可以写函数

# pair

pair 的定义 ——pair 可以理解为一个结构体，pair 将一对值 (T1 和 T2) 组合成一个值，这一对值可以具有不同的数据类型（T1 和 T2），两个值可以分别用 pair 的两个公有函数 first 和 second 访问。

pair 的应用 ——pair 是将 2 个数据组合成一组数据，当需要这样的需求时就可以使用 pair，如 stl 中的 map 就是将 key 和 value 放在一起来保存。另一个应用是，当一个函数需要返回 2 个数据的时候，可以选择 pair。

# pair 的定义

	pair<T1, T2> p1; // 创建一个空的 pair 对象（使用默认构造），它的两个元素分别是 T1 和 T2 类型，采用值初始化。
	pair<T1, T2> p1(v1, v2); // 创建一个 pair 对象，它的两个元素分别是 T1 和 T2 类型，其中 first 成员初始化为 v1，second 成员初始化为 v2。
	make_pair(v1, v2); // 以 v1 和 v2 的值创建一个新的 pair 对象，其元素类型分别是 v1 和 v2 的类型。
	p1 < p2; // 两个 pair 对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者！(p2.first < p1.first) && (p1.second < p2.second) 则返回 true。
	p1 == p2； // 如果两个对象的 first 和 second 依次相等，则这两个对象相等；该运算使用元素的 == 操作符。
	p1.first; // 返回对象 p1 中名为 first 的公有数据成员
	p1.second; // 返回对象 p1 中名为 second 的公有数据成员

# pair 的初始化

	pair<string, string> anon; // 创建一个空对象 anon，两个元素类型都是 string
	pair<string, int> word_count; // 创建一个空对象 word_count, 两个元素类型分别是 string 和 int 类型
	pair<string, vector<int> > line; // 创建一个空对象 line，两个元素类型分别是 string 和 vector 类型


	pair<string, string> author("James","Joy"); // 创建一个 author 对象，两个元素类型分别为 string 类型，并默认初始值为 James 和 Joy。
	pair<string, int> name_age("Tom", 18);
	pair<string, int> name_age2(name_age); // 拷贝构造初始化

# typedef 简化

	typedef pair<string,string> Author;
	Author proust("March","Proust");
	Author Joy("James","Joy");

# make_pair

	pair<int, double> p1;
	p1 = make_pair(1, 1.2);

	cout << p1.first << p1.second << endl;

	//output: 1 1.2

# struct initialization

https://blog.csdn.net/paulkg12/article/details/85198624

cpp

	create my container!
	destroy my container!

# Homework4 - 内存管理相关

# 编写深拷贝容器

# 析构函数

# 拷贝构造函数

# 移动构造函数

# 扩展学习

# explicit 关键字

# 成员变量定义时为什么加上

# 可以尝试在构造函数、拷贝构造、拷贝赋值中插入打印语句，查看下列代码的输出

# OO 优化

# 报错

# 操作符重载

# 引用计数的共享内存容器 Shared Container

# 扩展学习【待查看】

# 智能指针的简介

# shared_ptr

# unique_ptr

# weak_ptr

# *pointer 指针还是地址自增？

# 内存管理 memory context (MC)

# cpp 中 this 的理解

# stack

# 报错

# UI 设计

# struct

# pair

# pair 的定义

# pair 的初始化

# typedef 简化

# make_pair

# struct initialization

Lecture10-检错与纠错

Lecture11-RAID