c++ - 使用哪种 STL 结构？

Question

我需要一个解决方案，它将存储一个非唯一的键值对。我不想重复键（空间效率），我想专注于查找速度（插入新数据的效率不太重要）。我将在这里使用 std::multimap 。但我将不得不查找符合某些范围标准的键。

最复杂的例子：键是字符串，值不重要。我想找出所有值，哪些键以“Lol”开头。或者我想找出所有值，哪些键“介于”“bar”和“foo”之间。

我可以用多图来做吗？我的第二个想法是使用排序向量，它将指向值向量。像这样的东西：

std::vector<std::string, std::vector<T>> sorted_vec;

然后我可以轻松满足搜索条件。但我真的很关心查找的性能。这是一个正确的方法吗？

Answer 1

是的，您可以使用 std::multimap。为了完成您的范围基查询，您可以在头文件算法中使用两种算法 std::lower_bound 和 std::upper_bound 。

Answer 2

或者我想找出所有值，哪些键“介于”“bar”和“foo”之间。

如果你有 Boost，我建议使用boost::flat_map（它只是标头库）——它在. 通常，由于更好的紧凑性/局部性，它比std::map具有更好的查找。

否则使用

vector<pair<string,value>>
or
vector<pair<string,vector<value>>> //(for re-use of keys)
// instead of pair, you may use just struct if you concerned with lexicographical compare

加上std::sort

加上 std:: equal_range / lower_bound

Answer 3

您应该使用Patricia trie。

libstdc++ 中有一个，尽管它是非标准的。

如果您要坚持使用标准容器，我认为您的排序矢量解决方案是最好的。