要使用哪種STL結構？

我需要一個解決方案，它將存儲一個非唯一的鍵 - 值對。我不想重複鍵（空間效率），我想專注於查找速度（插入新數據的效率不那麼重要）。我將在這裏使用std :: multimap。但我將不得不查找鑰匙，它符合一些範圍標準。要使用哪種STL結構？

最複雜的例子：鍵是一個字符串，值並不重要。我想找出所有的值，哪些鍵以「Lol」開頭。或者我想要找出所有的值，哪些鍵在「bar」和「foo」之間。

我可以用multimap嗎？我的第二個想法是使用排序向量，它將指向值的向量。類似的東西：

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

然後，我可以輕鬆滿足搜索條件。但我真的很關心查找的性能。這是一個正確的方法嗎？

來源

2013-04-07 Dejwi

這聽起來像一個有序的矢量地圖更多沿着你所描述的線條，但我不確定它對你來說足夠多才多藝。 – WhozCraig 2013-04-07 01:03:04

如果插入不重要，我認爲''vector''會比''map''更受歡迎，因爲後者是基於rb-tree的。 ''struct foo {};矢量;''也許沒問題。 – gongzhitaao 2013-04-07 01:04:07

是的，你可以使用std :: multimap。爲了完成您的範圍基礎查詢，您可以在頭文件算法中使用兩個算法std :: lower_bound和std :: upper_bound。

來源

2013-04-07 03:28:50

我想我在lower_bound和upper_bound上犯了一個錯誤。這兩個算法對於multimap迭代器來說是無效的。改爲使用multimap :: lower_bound和multimap :: upper_bound。 – 2013-04-07 04:57:40

首先，由於Dejwi需要「鍵在酒吧和foo之間」 - 那麼[equal_range]（http://en.cppreference.com/w/cpp/container/multimap/equal_range）會比lower_bound + upper_bound更好。其次，因爲他「真的關心查找的性能」 - multimap是一個糟糕的選擇 - 由於更好的局部性，排序的向量會更快。 – 2013-04-08 14:26:05