c++ - 如何检查是否存在具有相同前缀的两个 key ？

Question

有这样的 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

如何检查映射中是否有键是另一个键的子字符串？

Answer 1

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 .