利用STL之map取巧做题过程

前言：这是我的一道作业题，为了减少代码量，我使用map进行数据保存，因为课堂进度并未涉及STL，所以我使用map就显得有些取巧

题目概述

main.cpp

#include <iostream> #include "world.h" using namespace std; void test_1() { person mike, jack, lily, carson, sucie; group school(0), family_1(1), family_2(1); // make group (act as a society) school.addMember(mike); school.addMember(jack); school.addMember(lily); family_1.addMember(mike); family_1.addMember(carson); family_2.addMember(jack); family_2.addMember(lily); family_2.addMember(sucie); // construct relationship in the society school.makeFriend(mike, jack); school.makeFriend(mike, lily); // display the society cout << "\n------ SCHOOL -----\n"; school.displayGroup(); cout << "\n------ FAMILY_1 -----\n"; family_1.displayGroup(); cout << "\n------ FAMILY_2 -----\n"; family_2.displayGroup(); } void test_2() { person Baidu, Alibaba, Tencent, NTES, Kingsoft_Antivirus, _360safe; group BAT(1), ECommerce(1), Security(1); // make group (act as a society) BAT.addMember(Baidu); BAT.addMember(Alibaba); BAT.addMember(Tencent); ECommerce.addMember(Baidu); ECommerce.addMember(Alibaba); ECommerce.addMember(Tencent); ECommerce.addMember(NTES); Security.addMember(Kingsoft_Antivirus); Security.addMember(_360safe); // display the society cout << "\n------ BAT -----\n"; BAT.displayGroup(); cout << "\n------ ECommerce -----\n"; ECommerce.displayGroup(); cout << "\n------ Security -----\n"; Security.displayGroup(); } void test_3() { person p0, p1, p2, p3, p4; group g0(0), g1(0), g2(1); // make group (act as a society) g0.addMember(p0); g0.addMember(p1); g0.addMember(p2); g1.addMember(p0); g1.addMember(p3); g2.addMember(p3); g2.addMember(p4); // construct relationship in the society g1.makeFriend(p0, p3); g2.breakRelation(p3, p4); g0.deleteMember(p2); // display the society cout << "\n------ G0 -----\n"; g0.displayGroup(); cout << "\n------ G1 -----\n"; g1.displayGroup(); cout << "\n------ G2 -----\n"; g2.displayGroup(); } void test_4() { person p[50]; group g0(0), g1(1); int p_count; cin >> p_count; // make group (act as a society) for (int i = 0; i < p_count/2; i++) g0.addMember(p[i]); for (int i = p_count/2; i < p_count; i++) g1.addMember(p[i]); // construct relationship in the society for (int i = 0; i < p_count/5; i += 2) g0.makeFriend(p[i], p[i+1]); for (int i = p_count/2; i < p_count*3/4-1; i += 2) g1.breakRelation(p[i], p[i+1]); for (int i = p_count/4; i < p_count/2; i++) g0.deleteMember(p[i]); for (int i = p_count*3/4; i < p_count; i++) g1.deleteMember(p[i]); // display the society cout << "\n------ G0 -----\n"; g0.displayGroup(); cout << "\n------ G1 -----\n"; g1.displayGroup(); } int main() { int test_id; cin >> test_id; switch (test_id) { case 1: test_1(); break; case 2: test_2(); break; case 3: test_3(); break; case 4: test_4(); break; default: cout << "wrong input\n"; } return 0; } /* ---------- structure for 'world.h' ---------- * define the struct and the class functions by yourself #(^_^)# * the member function is not complete, add something as you need struct person; class group { void displayGroup(); bool addMember(person &p); bool deleteMember(person &p); bool makeFriend(person &p1, person &p2); bool breakRelation(person &p1, person &p2); }; */

思路

group的private成员显然需要一个容器保存每一个加进来的person，且每一个person，都需要一个容器保存他的friends，起初我是将这个容器放在了person的类定义里，但是测试时发现这样不同group类型对象中的person的friends是一样的。所以需要把friends也放进group中。 至此问题就简化成，需要一个容器保存对象，而每个对象又有自己的保存其他对象的容器，于是我想到了std::map，将person::id作为map::key_type，并使用vector<int>保存每个friends的id。通过std::map自带的接口以及<algorithm>中的泛型算法，题目便简化了很多。

world.h实现

#ifndef WORLD_H #define WORLD_H #include <vector> #include <map> #include <iostream> #include <algorithm> using namespace std; static int num = 0; struct person { int id; person(): id(num) { ++num; } }; class group { private: map<int, vector<int>> members; bool known; public: group(int i): known(i) {} void displayGroup(); bool addMember(person &p); bool deleteMember(person &p); bool makeFriend(person &p1, person &p2); bool breakRelation(person &p1, person &p2); }; bool group::addMember(person &p) { if (members.find(p.id) == members.end() && p.id < 9900) { vector<int> temp; members.insert(pair<int, vector<int>>(p.id, temp)); if (known) { for (auto &a: members) { if (a.first != p.id) { a.second.push_back(p.id); members[p.id].push_back(a.first); } } } return true; } return false; } bool group::deleteMember(person &p) { if (members.find(p.id) != members.end()) { members.erase(p.id); return true; } return false; } bool group::makeFriend(person &p1, person &p2) { if (members.find(p1.id) != members.end() && members.find(p2.id) != members.end()) { members[p1.id].push_back(p2.id); members[p2.id].push_back(p1.id); return true; } return false; } bool group::breakRelation(person &p1, person &p2) { vector<int>::iterator a = find(members[p1.id].begin(), members[p1.id].end(), p2.id); vector<int>::iterator b = find(members[p2.id].begin(), members[p2.id].end(), p1.id); if (members.find(p1.id) != members.end() && members.find(p2.id) != members.end() && a != members[p1.id].end() && b != members[p2.id].end()) { members[p1.id].erase(a); members[p2.id].erase(b); return true; } return false; } void group::displayGroup() { for (auto &m: members) { cout << "Person_" << m.first << ": "; if (!m.second.size()) cout << "null"; for (int i = 0; i < m.second.size(); ++i) { cout << m.second[i]; cout << ((i + 1 < m.second.size()) ? ", " : ""); } cout << endl; } } #endif

当然，代码可能还能进一步简化， 此处不作深入。

Reference：www.cplusplus.com