2

我正在寻找一个 C++ 容器类，它很像多图，但略有不同。容器将存储成对的字符串。但是当我使用键 K 从容器中检索项目时，我想找到 K 以项目自己的键开头的所有项目。

EG 如果我使用键“abcde”，我想查找键为“adc”和“abcde”的项目，而不是“abcqz”。

或以伪 C++ 形式：

multimap2<string, string>  myMultiMap;
myMultiMap.insert( pair("abcde", "hello"));
myMultiMap.insert( pair("abc",   "Hi"));
myMultiMap.insert( pair("abcqz", "goodbye"));

// prints 2
cout << myMultiMap.count("abcde") << endl;

// prints "hello"  and  "Hi"
cout << myMultiMap.everything_which_matches("abcde") << endl;

// prints "Hi"
cout << myMultiMap.everything_which_matches("abc") << endl;

// prints "goodbye"
cout << myMultiMap.everything_which_matches("abcqz") << endl;

插入时间并不重要，但我需要快速访问这些项目。是否可以通过创建特殊的 < 运算符来使用普通的 Multimap 执行此操作？我的预感是，我需要普通的 < 操作符来进行插入，并需要一个特殊的操作符来进行检索。

谢谢

雨果

4

2 回答 2

11

我建议使用trie。

基本上你有一棵树，每个唯一字符有 1 个节点。对于查找和插入，您的算法都是 O(m)，其中 m 是字符串的长度。

所以按照你的例子：

"abcde", "hello" 
 "abc",  "Hi"
"abcqz", "goodbye"

然后你会有以下尝试：

       a
       |
       b
       |
       c       (c holds data of hi)
     /  \
    d    q
    |    |
    e    z (z holds data of goodbye)    (e holds data of hello)

要进行查找，您只需从根节点（上面未显示根节点）开始，然后跟随输入字符串中的下一个字符。每次到达具有数据结果的节点时，您都​​会将其作为输出字符串之一。

因此，搜索 abcde 会为您提供：“hi”、“hello”，如您所愿。它不会给你“再见”，因为你没有遍历那个结果节点。

于 2009-01-18T14:56:11.043 回答
1

首先，使用 std::multimap，插入和检索不能有不同的顺序。

其次，任何总排序都不足以满足您的目的，这意味着它不会将您想要的答案集呈现为间隔。

我要么使用一个查找来搜索所有前缀（您可以通过记住下一个较短前缀的长度等来优化它）或使用 Trie（而是需要更少空间的 PATRICIA trie）。

于 2009-01-18T15:25:08.487 回答