在C++地图中搜索带有前缀的所有键

Question

我正在使用地图来存储数据.地图有很大的数据.我想找到具有前缀的键,结果项数量的限制为50.我想使用最快的搜索方式,而不是遍历整个地图并检查,因为map已经是一个结构化的键值容器.

例如,如果我有一些对:

<"foo123", value>

<"foo234", value>

<"bar12", value>

<"foo456", value> 

<"bar200", value>

如果我搜索"foo",它会建议我

foo123, foo234, foo456. 

Answer 1

有两种方法可以想到:

• 第一个是一个名为trie的特殊容器,在C++标准库中没有相应的容器,但您应该能够轻松找到工作版本.

• 第二种方法只是使用以下事实:在a中std::map,密钥"foo"之前进行排序"foo123".使用upper_bound或lower_bound函数快速找到起始范围,然后使用线性搜索.