有这样的 map :
typedef std::string Path; // has this format "/<a>/<b>/<c>"
typedef std::vector<std::string> Paths;
typedef std::map<std::string, Paths> PathMapping;
PathMapping mathMapping; // ( "/a/b/c" --> "/a/b/c1", "a/b/c2" )
( "/a/b/d" --> "/a/b/d1", "a/b/d2" )
("/a/b/c/d" --> "a/b/c/d1", "a/b/c/d2" ) // not allowed
如何检查 map 中是否有其他键的子字符串?
最佳答案
map
中的键是按字典顺序排序的,因此,如果一个键A
将成为另一个键B
的前缀,则:
A
在B
之前A
也是A
和B
之间的任何键的前缀因此,我们可以在 map 中执行简单的扫描(此处为
m
):auto current = m.begin();
for (auto it = next(current), end = m.end(); it != end; ++it ) {
// Note: if current is not a prefix of "it", then it cannot be a prefix
// of any key that comes after "it", however of course "it" could
// be such a prefix.
// current is not a prefix of "it" if "it" is shorter
if (it->first.size() <= current->first.size()) { current = it; continue; }
// current is not a prefix of "it"
if (it->first.substr(0, current->first.size()) != current->first) {
current = it; continue;
}
// current is a prefix
std::cout << "'" << current->first << "' is a prefix of '" << it->first << "'\n";
}
注意:没有必要计算子字符串,不分配的
starts_with
函数会更好,但是确实可以理解。您可以检查full code here。
关于c++ - 如何检查两个键是否具有相同的前缀?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23181145/