首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >std::map的递归堆栈分配是如何工作的?

std::map的递归堆栈分配是如何工作的?
EN

Stack Overflow用户
提问于 2018-06-11 08:55:18
回答 1查看 59关注 0票数 1

堆栈分配的容器如何知道何时分配它们的子级?

例如:

class Trie {
    public:
    struct Node {
        map<char, Node> letters;
        bool end;
    };

    Node root;

    /** Initialize your data structure here. */
    Trie() {

    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *iter = &root;
        for(auto c: word) {
            iter = &iter->letters[c];
        }
        iter->end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *iter = &root;
        for(auto c: word) {
            if(iter->letters.find(c) == iter->letters.end()) return false;
            iter = &iter->letters[c];
        }
        return iter->end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *iter = &root;
        for(auto c: prefix) {
            if(iter->letters.find(c) == iter->letters.end()) return false;
            iter = &iter->letters[c];
        }
        return true;
    }
};

这段代码可以工作,但我不完全确定原因。(这是我在LeetCode上对Trie问题的解决方案。)

我有一个简单的堆栈分配根Node,其中包含char -> Node的映射。我的问题是,子节点是什么时候实际分配的?在引用letters (iter = &iter->letters[c];)下的节点时会发生这种情况吗?这段代码是不是非常不正确,并且对未定义的行为做了太多的假设?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-06-11 09:47:02

std::map::operator[]允许您在密钥不在容器中的情况下使用map[key] = value的语义。想象一下,如果您使用大小为nstd::vector执行此操作:如果您调用v[v.size()],那么至少可以这样说,该引用是对无主内存的引用。如果希望拥有它,则必须首先调整容器的大小,以确保键(索引)在容器的范围内。

因此,当您调用operator[]时,容器将检查您的键是否存在,如果键不存在,则默认为它构造一个值,然后返回对它的引用,就好像它一直在那里一样。这就是为什么operator[]是一个变异函数;如果键不存在,容器的状态将在新值的分配和缺省构造之后发生变异。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50789332

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档