我需要一个稍微不同的多重映射

Question

我在寻找一个C ++容器类，这是很多像多重映射，但略有不同。容器将存储字符串对。但是，当我检索使用密钥K从容器中的项目，我想找到的所有项目，其中K开始与项目本身的关键。

E.G。如果我用钥匙“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之做到这一点？我的直觉是，我需要正常<操作者插入，和一个特殊的一个用于检索。

感谢

雨果

Answer 1

我建议使用一个特里结构。

基本上你有每独特字符1个节点的树。 您的算法将是O（米）为两个查找和插入，其中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搜索会给你：“你好”，“你好”，你想要的。它不会给你“再见”，因为你没有穿越过这个结果节点。

Answer 2

首先，性病::多重映射，则可以不具有用于插入和检索一个不同的排序。

二，任何总排序是不是你的目的，这意味着它不会呈现答案设置你想要的时间间隔不够好。

我要么搜索与一个查找所有前缀的每个（你可以通过记住下一个的长度较短前缀等优化它），或使用一个Trie树（而是它要求更少的空间一PATRICIA线索）。