时间戳

首页 > 解决方案 > 使用 std::map 的递归堆栈分配如何工作？

c++ - 使用 std::map 的递归堆栈分配如何工作？

问题描述

具有内部引用的堆栈分配容器如何知道何时分配其子级？

例如：

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];) 这段代码是不是非常不正确，并且对未定义的行为做出了太多假设？

标签： c++memorystdmap

解决方案

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

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

推荐阅读