时间戳

首页 > 解决方案 > 将元素分配给映射值时的C ++错误访问

c++ - 将元素分配给映射值时的C ++错误访问

问题描述

所以这个问题解释了问题......

背景：

我正在尝试从 HackerRank解决这个问题。

它基本上是一个 html 标签解析器。保证有效输入，属性只是字符串。

我的方法

我创建了一个自定义Tag类，可以存储一个map<string,Tag>其他Tag的，以及一个map<string,string>属性。解析似乎工作正常。

问题

在查询部分，我收到BAD_ACCESS以下查询/html 组合的错误：

4 1
<a value = "GoodVal">
<b value = "BadVal" size = "10">
</b>
</a>
a.b~size

当我尝试b从a. 具体来说，它位于t=t.tags[tag_name]下面的第 118 行。

代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <map>
#include <stack>
using namespace std;

class Tag {
public:
    Tag(){};
    Tag(string name):name(name){};
    string name;
    map<string,Tag> tags = map<string, Tag>();
    map<string,string> attribs=map<string,string>();
};

int main() {
    int lines, queries;
    std::cin>>lines>>queries;

    std:string str;
    getline(cin, str);
    stack<string> open;
    auto tags = map<string, Tag>();
    for (int i = 0; i < lines; i++) {
        getline(cin, str);
        if (str.length()>1){
            // If it's not </tag>, then it's an opening tag
            if  (str[1] != '/') {
                // Parse tag name
                auto wordidx = str.find(" ");
                if (wordidx == -1) {
                    wordidx = str.length()-1.f;
                }
                string name = str.substr(1,wordidx-1);
                auto t = Tag(name);

                string sub = str.substr(wordidx);
                auto equalidx=sub.find("=");

                // Parse Attributes
                while (equalidx != std::string::npos) {
                    string key = sub.substr(1,equalidx-2);
                    sub = sub.substr(equalidx);
                    auto attrib_start = sub.find("\"");
                    sub = sub.substr(attrib_start+1);
                    auto attrib_end = sub.find("\"");
                    string val = sub.substr(0, attrib_end);
                    sub = sub.substr(attrib_end+1);

                    t.attribs[key] = val;
                    equalidx=sub.find("=");
                }

                // If we're in a tag, push to that, else push to the base tags
                if (open.size() == 0) {
                    tags[name] = t;
                } else {
                    tags[open.top()].tags[name]=t;
                }
                open.push(name);
            } else {
                // Pop the stack if we reached a closing tag
                auto wordidx = str.find(">");
                string name = str.substr(2,wordidx-2);

                // Sanity check, but we're assuming valid input
                if (name.compare(open.top())) {
                    cout<<"FUCK"<<name<<open.top()<<endl;
                    return 9;
                }
                open.pop();
            }

        } else {
            std::cout<<"FUCK\n";
        }
    }

    //
    // Parse in queries
    //
    for (int i = 0; i < queries; i++) {
        getline(cin, str);
        Tag t = Tag();
        bool defined = false;


        auto next_dot = str.find(".");
        while (next_dot!=string::npos) {
            string name = str.substr(0,next_dot);
            if (defined && t.tags.find(name) == t.tags.end()) {
                //TAG NOT IN T
                cout<<"Not Found!"<<endl;
                continue;
            }
            t = !defined ? tags[name] : t.tags[name];
            defined = true;

            str = str.substr(next_dot+1);
            next_dot = str.find(".");
        }

        auto splitter = str.find("~");
        string tag_name = str.substr(0,splitter);
        string attrib_name = str.substr(splitter+1);

        if (!defined) {
            t = tags[tag_name];
        } else if (t.tags.find(tag_name) == t.tags.end()) {
            //TAG NOT IN T
            cout<<"Not Found!"<<endl;
            continue;
        } else {
            t = t.tags[tag_name];
        }
        // T is now set, check the attribute
        if (t.attribs.find(attrib_name) == t.attribs.end()) {
            cout<<"Not Found!"<<endl;
        } else {
            cout<<t.attribs[attrib_name]<<endl;
        }

    }

    return 0;
}

我试过的

只需Tag x = t.tags[tag_name];在上面的行中将其定义为新变量，然后执行此操作即可解决此问题，t = x;但为什么会发生这种情况？

此外，以下查询也会失败：a.b.c~height，但在第 99 行尝试获取 a.tags["b"] 时失败。不知道为什么。我本来打算使用上面的hacky修复，但这似乎是我做错了的一个大核心问题。

我建议在 IDE 上运行它并验证解析确实正确。

标签： c++dictionaryhashmapexc-bad-access

解决方案

t=t.tags[tag_name]

此表达式是不安全的，因为您正在复制分配该对象拥有的对象而不是拥有对象。

考虑这一行发生了什么：

  1. 执行地图查找并返回一个Tag&.
  2. 您尝试将其复制分配给t，调用隐式复制分配运算符。
  3. t.tags该运算符从tags复制源的属性中复制分配-它位于t.tags.

结果是您要复制到的对象t在该副本的中间被销毁。这会导致未定义的行为，并且立即崩溃确实是最好的结果，因为它可以准确地告诉您问题出在哪里。（这种问题经常出现在程序稍后的某个时间点，此时您已经失去了找出导致 UB 的原因所需的状态。）

一种解决方法是将源对象移动到临时对象中，然后将该临时对象移动分配到t：

t = Tag{std::move(t.tags[tag_name])};

这会在我们尝试将其放入之前将我们想要分配的数据提升t 出来tt。然后，当t's 赋值运算符转到 replacet.tags时，您尝试分配的数据t不再存在。

但是，这种整体方法涉及大量不必要的复制。最好声明t为Tag const *t;- 让它成为一个标签的指针。然后，您可以移动该指针以指向数据结构中的其他标签，而无需进行复制。

旁注：我前几天刚做了这个问题！这里有一个提示可以帮助你简化事情：你真的需要标签结构吗？是否有一种更简单的查找结构可以代替嵌套标签？

推荐阅读