HackerRank C++面试，中等难度题目 - Attribute Parser

去除字符串首尾的空白字符（包括空格、制表符、换行符和回车符）

void trim(string &s) {size_t start = s.find_first_not_of(" \t\n\r");size_t end = s.find_last_not_of(" \t\n\r");if (start == string::npos) {s = "";} else {s = s.substr(start, end - start + 1);}
}

• 参数: string &s - 传入的字符串引用，函数会直接修改该字符串。
• 通过使用引用，你可以确保函数内部对字符串的修改直接影响到传入的原始字符串，而不是它的副本。这样可以避免额外的拷贝和内存分配。
• 在C++中，find_first_not_of 和 find_last_not_of 是 std::string 类的成员函数，用于查找字符串中第一个或最后一个不匹配指定字符集的字符的位置。
• 使用 find_first_not_of 方法找到字符串中第一个不是空格、制表符、换行符或回车符的字符位置。
• 如果 start 等于 string::npos，说明整个字符串都是空白字符，将字符串置为空字符串。
• 否则，使用 substr 方法提取从 start 到 end 之间的子字符串，并赋值给原字符串 s。

从格式化的属性字符串中提取键值对，并将其存储在一个向量中

vector<pair<string, string>> parse_attrs(const string &s) {// 初始化一个空的向量attrs用于存储解析后的键值对。vector<pair<string, string>> attrs;// 初始化位置指针pos为0，用于遍历输入字符串。在遍历数组或容器时，size_t 常被用作循环变量的类型，因为它能够处理所有可能的索引值。size_t pos = 0;while (pos < s.size()) {// 跳过字符串开头的所有空白字符。while (pos < s.size() && isspace(s[pos])) {pos++;}if (pos >= s.size()) {break;}// 查找下一个等号的位置，如果找不到则退出循环。size_t equal_pos = s.find('=', pos); // 查找字符串 s 中从位置 pos 开始的第一个等号（'='）字符的位置。if (equal_pos == string::npos) {break;}string attr_name = s.substr(pos, equal_pos - pos);trim(attr_name);pos = equal_pos + 1;// 跳过等号后的所有空白字符。while (pos < s.size() && isspace(s[pos])) {pos++;}// 检查当前字符是否为双引号，如果不是则退出循环。if (pos >= s.size() || s[pos] != '"') {break;}pos++; // 找到下一个双引号的位置，提取其中的子字符串作为值。size_t value_start = pos;size_t value_end = s.find('"', pos);if (value_end == string::npos) {break;}string attr_value = s.substr(value_start, value_end - value_start);pos = value_end + 1; // 更新位置指针到双引号后的下一个字符。// 将解析出的键值对添加到向量中。attrs.emplace_back(attr_name, attr_value);}return attrs;
}

• emplace_back: 这是 vector 类的一个成员函数，用于在容器的末尾直接构造元素。

main函数

int main() {// 读取两个整数N和Q，分别表示标签行数和查询次数。int N, Q;cin >> N >> Q;cin.ignore();// tag_stack用于存储当前打开的标签。vector<string> tag_stack;// attributes用于存储每个标签路径下的属性。unordered_map<string, unordered_map<string, string>> attributes;for (int i = 0; i < N; ++i) {string line;getline(cin, line);if (line.empty()) continue;// 如果遇到关闭标签（以</开头），则从tag_stack中弹出最后一个标签。if (line[1] == '/') {if (!tag_stack.empty()) {tag_stack.pop_back();}} else {line = line.substr(1, line.size() - 2); // 去掉字符串 line 的第一个字符和最后一个字符istringstream iss(line); // 创建了一个输入字符串流// 从字符串流 iss 中读取第一个单词（即标签名），并将其存储在 tag_name 变量中string tag_name;iss >> tag_name;// 从字符串流 iss 中读取剩余的内容（即标签的属性部分）string attr_str;getline(iss >> ws, attr_str); // 跳过任何前导空白字符（由 ws 表示）并读取直到行尾的所有内容// 从格式化的属性字符串中提取键值对，并将其存储在一个向量中vector<pair<string, string>> attrs = parse_attrs(attr_str);// 将当前的 tag_name 添加到 tag_stack 的末尾tag_stack.push_back(tag_name);// 构建一个表示当前标签路径的字符串string current_path;for (const string& tag : tag_stack) {if (!current_path.empty()) {current_path += ".";}current_path += tag;}for (const auto& attr : attrs) {attributes[current_path][attr.first] = attr.second;}}}for (int i = 0; i < Q; ++i) {string query;getline(cin, query);size_t tilde_pos = query.find('~');if (tilde_pos == string::npos) {cout << "Not Found!" << endl;continue;}string path = query.substr(0, tilde_pos);string attr = query.substr(tilde_pos + 1);// 确保在 attributes 中存在指定的路径 path，并且在这个路径下存在指定的属性 attr。if (attributes.find(path) != attributes.end() && attributes[path].find(attr) != attributes[path].end()) {cout << attributes[path][attr] << endl;} else {cout << "Not Found!" << endl;}}return 0;
}

• unordered_map<string, unordered_map<string, string>> attributes; 是一个嵌套的哈希表（也称为字典或映射），用于存储HTML标签的属性。
• getline 函数从输入流 cin 中读取字符，直到遇到换行符（‘\n’），但不包括换行符。读取的字符被存储到字符串 line 中。
• attributes.find(path) 尝试在 attributes 中找到键为 path 的元素。
  如果找到了这个路径，find 方法返回一个迭代器，指向找到的元素；否则，返回 attributes.end()。
• 然后，attributes[path].find(attr) 尝试在这个内部的 unordered_map 中找到键为 attr 的元素。
• 同样地，如果找到了这个属性，find 方法返回一个迭代器，指向找到的元素；否则，返回 attributes[path].end()。