突破编程_C++_STL教程（ multimap 的实战应用）

C++ STL教程： multimap 的实战应用

h8062651

1127人浏览 · 2024-03-15 09:58:15

h8062651 · 2024-03-15 09:58:15 发布

1 std::multimap 应用于自定义数据结构

std::multimap 是 C++ 标准库中的一个容器，它存储的元素都是键值对，并且允许有重复的键。这对于一些需要记录多个相同键值的场景非常有用。

如果需要将 std::multimap 应用于自定义数据结构，则要确保自定义的数据结构满足以下条件：

键值的可比较性：std::multimap 中的元素是按照键的顺序进行排序的。因此，自定义数据结构的键必须是可以比较的，即需要重载 < 运算符或者提供一个比较函数。
合适的键值对表示：std::multimap 存储的是键值对，所以需要定义一个合适的方式来表示你的数据结构中的键和值。

下面是一个简单的例子，展示了如何将 std::multimap 应用于自定义数据结构：

#include <iostream>  
#include <map>  
#include <string>  
  
// 自定义数据结构  
struct Person {  
    std::string name;  
    int age;  
  
    Person(const std::string& name, int age) : name(name), age(age) {}  
  
    // 重载 < 运算符以定义比较规则  
    bool operator<(const Person& other) const {  
        return age < other.age;  // 按照年龄进行排序  
    }  
};  
  
int main() 
{  
    // 创建一个 std::multimap，键为 Person，值为 int  
    std::multimap<Person, int> people;  
  
    // 插入元素  
    people.insert({Person("Alice", 25), 1});  
    people.insert({Person("Bob", 30), 2});  
    people.insert({Person("Charlie", 25), 3});  
    people.insert({Person("David", 20), 4});  
  
    // 遍历并打印元素  
    for (const auto& pair : people) {  
        std::cout << pair.first.name << ": " << pair.first.age << ", Value: " << pair.second << std::endl;  
    }  
  
    return 0;  
}

上面代码的输出为：

David: 20, Value: 4
Alice: 25, Value: 1
Charlie: 25, Value: 3
Bob: 30, Value: 2

上面的这个例子定义了一个 Person 结构体作为键，它包含了一个名字和一个年龄。并且重载了 < 运算符以定义比较规则，这里按照年龄进行排序。然后，创建了一个 std::multimap，键为 Person，值为 int。并插入了一些元素，遍历打印了它们。

注意，由于是按照年龄进行排序，并且允许有重复的键（即相同年龄的人），所以在这个例子中，Alice 和 Charlie 由于年龄相同，它们会按照插入的顺序在 multimap 中相邻存储。

2 std::multimap 的主要应用场景

文件系统映射： 在文件系统中，一个物理文件可能对应多个符号链接。multimap 可以用来存储这些映射关系，其中键是物理文件的路径，而值则是对应的符号链接路径。

DNS 服务器： 在 DNS（域名系统）中，一个 IP 地址可能对应多个 URL（统一资源定位符）。multimap 可以用来存储这些映射，其中键是IP地址，而值则是对应的URL。

统计和计数： 在需要统计某个键出现的次数或者与某个键相关的多个值时，multimap 也是很有用的。你可以将键存储为统计的类别或标识，而将值存储为计数或相关的具体数据。

数据字典： 当需要快速根据某个键查找多个相关的值时，multimap 可以作为一种数据字典使用。例如，可以根据某个主题查找相关的多个文章或资料。

电话簿应用： 在电话簿中，同一个人可能拥有多个电话号码。使用 multimap，可以方便地存储和检索一个人的所有电话号码。键可以是人的姓名，而值则是对应的电话号码。

2.1 std::multimap 应用于文件系统映射

在文件系统中，一个文件可能有多个硬链接指向它。在这种情况下，我们可以使用 std::multimap 来记录这些链接到文件路径的映射关系。键是文件的实际路径，而值则是指向该文件的硬链接路径。

下面是一个简单的示例代码，展示了如何使用 std::multimap 来存储和检索文件与硬链接之间的映射关系：

#include <iostream>  
#include <map>  
#include <string>  
#include <vector>  

int main()
{
	// 创建一个 std::multimap，键为文件实际路径，值为硬链接路径  
	std::multimap<std::string, std::string> fileLinks;

	// 插入一些文件和对应的硬链接路径  
	fileLinks.insert({ "/path/to/actual/file", "/path/to/link1" });
	fileLinks.insert({ "/path/to/actual/file", "/path/to/link2" });
	fileLinks.insert({ "/another/actual/file", "/another/link1" });
	fileLinks.insert({ "/another/actual/file", "/another/link2" });
	fileLinks.insert({ "/another/actual/file", "/another/link3" });

	// 遍历并打印文件和对应的硬链接路径  
	for (const auto& pair : fileLinks) {
		std::cout << "Actual File: " << pair.first << std::endl;
		std::cout << "Hard Links:";
		auto range = fileLinks.equal_range(pair.first);
		for (auto it = range.first; it != range.second; ++it) {
			std::cout << " " << it->second;
		}
		std::cout << std::endl;
	}

	// 查找特定文件的硬链接  
	std::string filePathToFind = "/path/to/actual/file";
	auto range = fileLinks.equal_range(filePathToFind);
	std::cout << "Hard links for " << filePathToFind << ":" << std::endl;
	for (auto it = range.first; it != range.second; ++it) {
		std::cout << " " << it->second << std::endl;
	}

	return 0;
}

上面代码的输出为：

Actual File: /another/actual/file
Hard Links: /another/link1 /another/link2 /another/link3
Actual File: /another/actual/file
Hard Links: /another/link1 /another/link2 /another/link3
Actual File: /another/actual/file
Hard Links: /another/link1 /another/link2 /another/link3
Actual File: /path/to/actual/file
Hard Links: /path/to/link1 /path/to/link2
Actual File: /path/to/actual/file
Hard Links: /path/to/link1 /path/to/link2
Hard links for /path/to/actual/file:
 /path/to/link1
 /path/to/link2

在这个示例中，首先创建了一个 std::multimap，键是文件的实际路径，值是硬链接的路径。然后，插入了一些示例数据和对应的硬链接。接着，遍历了整个 multimap 并打印了每个文件的实际路径以及它所有的硬链接。最后，使用 equal_range 方法查找特定文件的硬链接，并打印了结果。

需要注意的是，在实际的文件系统中，硬链接和文件路径的映射关系通常是由操作系统维护的，并且可以通过特定的系统调用来查询。上面的示例仅仅是为了展示 std::multimap 在这种场景下的一个可能应用方式，而不是实际的文件系统实现。在实际应用中，应该使用操作系统提供的API来查询和操作文件系统的链接关系。

1.2 std::multimap 应用于DNS 服务器

在 DNS（域名系统）服务器的上下文中，std::multimap 可以被用来存储 DNS 记录，特别是当同一个域名可能对应多个 IP 地址时（例如，一个域名可能同时有一个 IPv4 地址和一个 IPv6 地址）。

以下是一个简化的示例，说明如何使用 std::multimap 来模拟一个 DNS 服务器的功能。注意：这个示例没有考虑 DNS 协议的复杂性或网络编程的细节。

#include <iostream>  
#include <string>  
#include <map>  
  
// 假设的 DNS 记录结构  
struct DNSRecord {  
    std::string ipAddress;  
    std::string type;  // 例如：A (IPv4), AAAA (IPv6) 等  
};  
  
// 使用 multimap 存储 DNS 记录  
std::multimap<std::string, DNSRecord> dnsRecords;  
  
// 添加 DNS 记录到 multimap  
void addDNSRecord(const std::string& domain, const DNSRecord& record) {  
    dnsRecords.insert({domain, record});  
}  
  
// 根据域名查询 DNS 记录  
std::vector<DNSRecord> queryDNS(const std::string& domain) {  
    std::vector<DNSRecord> results;  
    auto range = dnsRecords.equal_range(domain);  
    for (auto it = range.first; it != range.second; ++it) {  
        results.push_back(it->second);  
    }  
    return results;  
}  
  
int main() 
{  
    // 添加一些示例 DNS 记录  
    addDNSRecord("example.com", {"192.168.1.1", "A"});  
    addDNSRecord("example.com", {"2001:db8:1::1", "AAAA"});  
    addDNSRecord("anotherdomain.net", {"10.0.0.1", "A"});  
  
    // 查询并打印 DNS 记录  
    std::string domainToQuery = "example.com";  
    std::cout << "DNS records for " << domainToQuery << ":" << std::endl;  
    auto records = queryDNS(domainToQuery);  
    for (const auto& record : records) {  
        std::cout << "IP: " << record.ipAddress << ", Type: " << record.type << std::endl;  
    }  
  
    return 0;  
}

上面代码的输出为：

DNS records for example.com:
IP: 192.168.1.1, Type: A
IP: 2001:db8:1::1, Type: AAAA

在这个示例中，定义了一个 DNSRecord 结构体来存储 DNS 记录的信息（IP 地址和记录类型）。然后使用 std::multimap<std::string, DNSRecord> 来存储 DNS 记录，其中键是域名，值是 DNSRecord 结构体。接下来使用 addDNSRecord 函数来添加 DNS 记录，使用 queryDNS 函数来根据域名查询 DNS 记录。在 main 函数中，添加了一些示例 DNS 记录，并查询了 “example.com” 的记录。

1.3 std::multimap 应用于统计和计数

假设我们有一个在线平台，用户可以对不同的项目进行评分，并且每个用户可以对同一个项目多次评分。我们想要跟踪每个用户的所有评分记录，以便后续分析或显示给用户。

下面是一个使用 std::multimap 来存储和统计用户评分记录的示例：

#include <iostream>  
#include <map>  
#include <string>  
#include <vector>  

// 假设的评分结构  
struct Rating {
	int score; // 评分，例如 1-5 星  
	std::string timestamp; // 评分时间戳  
};

int main() 
{
	// 使用 multimap 存储用户评分记录，键是用户名，值是评分和时间戳  
	std::multimap<std::string, Rating> userRatings;

	// 假设这是从数据库或用户输入中获取的评分数据  
	std::vector<std::pair<std::string, Rating>> rawRatings = {
		{"user1", {5, "2023-03-01 10:00"}},
		{"user2", {4, "2023-03-01 11:00"}},
		{"user1", {3, "2023-03-01 12:00"}},
		{"user2", {5, "2023-03-01 13:00"}},
		{"user3", {2, "2023-03-01 14:00"}},
		// ... 更多评分数据  
	};

	// 将原始评分数据添加到 multimap 中  
	for (const auto& rating : rawRatings) {
		userRatings.insert(rating);
	}

	// 统计和输出每个用户的平均评分  
	std::map<std::string, double> averageRatings;
	for (const auto& userGroup : userRatings) {
		std::string username = userGroup.first;
		int sum = 0;
		int count = 0;
		auto range = userRatings.equal_range(username);
		for (auto it = range.first; it != range.second; ++it) {
			sum += it->second.score;
			count++;
		}
		if (count > 0) {
			double average = static_cast<double>(sum) / count;
			averageRatings[username] = average;
		}
	}

	// 输出每个用户的平均评分  
	for (const auto& avgRating : averageRatings) {
		std::cout << "User: " << avgRating.first << ", Average Rating: " << avgRating.second << std::endl;
	}

	return 0;
}

上面代码的输出为：

User: user1, Average Rating: 4
User: user2, Average Rating: 4.5
User: user3, Average Rating: 2

这个例子首先定义了一个 Rating 结构体来存储评分和对应的时间戳。然后，使用 std::multimap<std::string, Rating> 来存储用户的评分记录，其中键是用户名，值是评分和时间戳。

假设有一组原始的评分数据，这些数据可能是从数据库或用户输入中获取的。将这些数据添加到 multimap 中。

接下来，遍历 multimap 来计算每个用户的平均评分。并且使用 equal_range 函数来获取每个用户的所有评分记录，然后计算平均值。这些平均值被存储在一个 std::map<std::string, double> 中，其中键是用户名，值是平均评分。

最后，遍历这个 map 并输出每个用户的平均评分。

这个示例展示了 std::multimap 在处理可能有重复键（在这种情况下是用户名）的统计和计数问题时的有用性。通过存储额外的信息（如时间戳），我们可以进行更复杂的分析，比如查看评分趋势或分析特定时间段的评分。

2 实现一个简单的 std::multimap 容器

实现一个完整的 std::multimap 容器是一个相当复杂的任务，因为需要考虑到许多细节，比如红黑树的实现、迭代器、异常安全性等。但是，为了展示基本的思路，可以简化这个过程，使用红黑树作为底层数据结构，实现元素的插入与打印。

注意红黑树具有以下五个关键性质：

（1）每个节点要么是红色，要么是黑色。
（2）根节点是黑色。
（3）所有叶子节点（NIL或空节点）是黑色。
（4）如果一个节点是红色的，则它的两个子节点都是黑色。
（5）对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

这些性质确保了红黑树在插入、删除节点后仍然能够保持相对平衡，从而保证了树的查找、插入和删除操作的时间复杂度为O(log n)。

如下是使用红黑树作为底层数据结构的 std::multimap 容器实现：

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

enum Color { RED, BLACK };

template <typename K, typename V>
struct Node {
	std::vector<std::pair<K,V>> datas;
	Color color;
	Node* left;
	Node* right;
	Node* parent;

	Node(std::vector<std::pair<K, V>> datas_, Color c = RED, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr)
		: datas(datas_), color(c), parent(p), left(l), right(r) {}
};

template <typename K, typename V>
class SimpleMultimap
{
public:
	SimpleMultimap() : root(nullptr) {}

	// 插入元素  
	void insert(const K& key, const V& value) {
		root = insert(root, key, value);
	}

	// 打印元素  
	void print() {
		inorderTraversal(root);
		std::cout << std::endl;
	}

	// 析构函数，用于释放内存  
	~SimpleMultimap() {
		// 递归删除所有节点  
		deleteTree(root);
	}
private:
	// 递归删除树
	void deleteTree(Node<K, V>* node) {
		if (node != nullptr) {
			deleteTree(node->left);
			deleteTree(node->right);
			delete node;
		}
	}

	// 辅助函数：检查节点是否是红色或黑色  
	bool isRed(Node<K, V>* node) const {
		if (node == nullptr) return false;
		return node->color == RED;
	}

	bool isBlack(Node<K, V>* node) const {
		if (node == nullptr) return true;
		return node->color == BLACK;
	}

	// 左旋  
	void leftRotate(Node<K, V>*& x) {
		Node<K, V>* y = x->right;
		x->right = y->left;
		if (y->left) y->left->parent = x;
		y->parent = x->parent;
		if (!x->parent) root = y;
		else if (x == x->parent->left) x->parent->left = y;
		else x->parent->right = y;
		y->left = x;
		x->parent = y;
	}

	// 右旋  
	void rightRotate(Node<K, V>*& x) {
		Node<K, V>* y = x->left;
		x->left = y->right;
		if (y->right) y->right->parent = x;
		y->parent = x->parent;
		if (!x->parent) root = y;
		else if (x == x->parent->right) x->parent->right = y;
		else x->parent->left = y;
		y->right = x;
		x->parent = y;
	}

	// 插入修复  
	void fixInsert(Node<K, V>*& k) {
		while (k != root && isRed(k->parent)) {
			if (isRed(k->parent->parent->left) == (k == k->parent->right)) {
				Node<K, V>* u = k->parent->parent->left;
				if (u) u->color = RED;
				k->parent->color = BLACK;
				k->parent->parent->color = RED;
				k = k->parent->parent;
			}
			else {
				if (k == k->parent->left) {
					k = k->parent;
					rightRotate(k);
				}
				k->parent->color = BLACK;
				k->parent->parent->color = RED;
				leftRotate(k->parent->parent);
			}
		}
		root->color = BLACK;
	}

	// 插入节点  
	Node<K, V>* insert(Node<K, V>*& node, const K& key, const V& value) {
		if (node == nullptr) {
			return new Node<K, V>(std::vector<std::pair<K, V>>{std::make_pair(key,value)});
		}

		if (key < std::get<0>(node->datas[0])) {
			node->left = insert(node->left, key, value);
			node->left->parent = node;
		}
		else if (key > std::get<0>(node->datas[0])) {
			node->right = insert(node->right, key, value);
			node->right->parent = node;
		}
		else {
			node->datas.emplace_back(std::make_pair(key, value));
			return node;
		}

		// 修复红黑树性质  
		if (isRed(node->right) && isRed(node->left)) {
			node->color = RED;
			node->left->color = BLACK;
			node->right->color = BLACK;
		}
		else if (isRed(node->parent) && isRed(node->parent->parent) &&
			(node == node->parent->right ||
			(node->parent == node->parent->parent->left &&node == node->parent->left))) {
			node->parent->color = BLACK;
			node->parent->parent->color = RED;
			if (node == node->parent->left) {
				rightRotate(node->parent->parent);
			}
			else {
				leftRotate(node->parent->parent);
			}
		}

		if (node->parent == nullptr) {
			root = node;
		}

		fixInsert(node);
		return node;
	}

	// 中序遍历打印，用于验证  
	void inorderTraversal(Node<K, V>* node) {
		if (node != nullptr) {
			inorderTraversal(node->left);
			for_each(node->datas.begin(), node->datas.end(), [](std::pair<K, V>& val) {
				std::cout << std::get<0>(val) << ":" << std::get<1>(val) << std::endl;
			});
			inorderTraversal(node->right);
		}
	}

private:
	Node<K, V>* root;


};

int main()
{
	SimpleMultimap<int, int> valMap;
	valMap.insert(1, 2);
	valMap.insert(1, 3);
	valMap.insert(2, 2);
	valMap.insert(2, 2);
	valMap.insert(2, 6);
	valMap.insert(3, 9);

	valMap.print(); // 打印集合

	return 0;
}

上面代码的输出为：

1:2
1:3
2:2
2:2
2:6
3:9

上面的这段代码定义了一个简单的集合类 SimpleMultimap，但请注意，它并不是真正的红黑树实现，尽管代码中有一些红黑树的元素，如颜色枚举、左旋和右旋操作。它更接近于一个多值 B 树（B 树的一个变种），其中每个节点可以包含多个键值对。
可以参考对比前面教程"突破编程_C++_STL教程（ map 的实战应用）"中"实现一个简单的 std::map 容器"的章节，最大的区别就是，将 struct Node 中的 K key; V value; 调整成为 std::vector<std::pair<K,V>> datas; ，这样便可以存储重复元素。