如何将已排序的std::list<std::pair>转换为std::map

Question

我有一个 `std::list>`，我知道它是按照 `std::string` 元素排序的。

由于我想基于 `std::string` 元素做很多 `std::find_if`，因此我认为使用带有 `lower_bound` 和 `upper_bound` 的 `std::map` 更加适合。

事实上，我想以一种高效的方式向 `std::map` 中插入元素。因此，我想使用一个额外的迭代器来加速 `insert` 操作。

我认为最简单的方法是使用 `const_reverse_iterator` 遍历 `std::list` 并使用 `std::map` 的 `begin()`。

您会采用这种方式吗？还是这个想法不好？

谢谢！

- Wok

---

不要在标题上加[C++]，这就是标签的作用。 - NullUserException

有了grddev和Luther Blissett提供的答案，我的表现与最初的建议相当（使用begin()而不是end()）。 但是，两者都很简洁。 我接受grddev的答案因其简单性，但我会记住std：：inserter。 谢谢大家！ - Wok

Answer 1

如果你已经有一个根据谓词 Predicate 排序过的列表，你只需要执行以下操作：

std::list< std::pair<std::string, double> > sorted_list;
std::map<string, double, Predicate> map(sorted_list.begin(), sorted_list.end());

map 构造函数在列表已排序的情况下具有线性时间复杂度，否则为 O(n*log n)。您可以像处理其他任何对象一样直接使用该映射。

如果您稍后想要将结果返回到列表中，则可以执行相反的操作：

sorted_list.assign(map.begin(), map.end());

- grddev

---

这个答案的优点在于它的简洁明了。谢谢！ - Wok

Answer 2

您可以使用std :: copy和std :: inserter：

std::copy(the_list.begin(),the_list.end(),std::inserter(the_map,the_map.begin()));  

因为列表< pair >的迭代器具有与map< X,Y >的迭代器兼容的值类型。

- Nordic Mainframe

---

+1：这个方案性能同样出色，而且可以与现有的地图一起使用。 - grddev

在这里使用std::inserter(the_map,the_map.begin())或std::inserter(the_map,the_map.end())更好，考虑到列表已经排序了吗？ - clstrfsck

其实我有一个疑问，问题是 end 不会被重新实现，也就是说它在 inserter 被创建的时候就已经是 end，并且不会保持为 end，因此我不知道复杂度是否是线性的。 - Matthieu M.

看了一下insert_iterator，性能不太好，因为在插入时，它会在前一个插入之后插入迭代器，这意味着"慢速"地图插入将被执行。 - grddev

我使用begin()或end()这个解决方案的性能大致相同。感谢您提供如此有趣的答案。 - Wok

Answer 3

我会对列表进行迭代，将每一对插入到一个映射中，或者使用Luther Blissett描述的巧妙方法。
我不明白你试图做什么，这意味着它要么会导致无法阅读的代码，要么你偏离了正题。
你为什么要这样做？
你能否更改代码，在第一次返回一个映射而不是一个列表?

- the_drow

---

我必须首先使用std::list，因为有一些元素具有相同的std::string键。然后，在最后有一些操作让我使用std::map。在这种情况下，我可能会在过程中稍早考虑使用std::map，但问题仍然是相关的。 - Wok

您考虑过使用std::multimap吗？请参阅此处：http://www.sgi.com/tech/stl/Multimap.html - the_drow