堆栈分配的容器如何知道何时分配它们的子级?
例如:
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];
)下的节点时会发生这种情况吗?这段代码是不是非常不正确,并且对未定义的行为做了太多的假设?
发布于 2018-06-11 09:47:02
std::map::operator[]
允许您在密钥不在容器中的情况下使用map[key] = value
的语义。想象一下,如果您使用大小为n
的std::vector
执行此操作:如果您调用v[v.size()]
,那么至少可以这样说,该引用是对无主内存的引用。如果希望拥有它,则必须首先调整容器的大小,以确保键(索引)在容器的范围内。
因此,当您调用operator[]
时,容器将检查您的键是否存在,如果键不存在,则默认为它构造一个值,然后返回对它的引用,就好像它一直在那里一样。这就是为什么operator[]
是一个变异函数;如果键不存在,容器的状态将在新值的分配和缺省构造之后发生变异。
https://stackoverflow.com/questions/50789332
复制相似问题