如何将 std::pair 的排序 std::list 转换为 std::map [英] How to convert a sorted std::list of std::pair to a std::map

问题描述

我有一个 std::list<std::pair<std::string,double>>，我知道是按照std::string element排序的.

I have got a std::list< std::pair<std::string,double> >, which I know is sorted according to the std::string element.

由于我想做很多基于 std::string 元素的 std::find_if，我相信 std::map<string,double,MyOwnBinaryPredicate> 与 lower_bound 和 upper_bound 会更合适.

Since I would like to do a lot of std::find_if based on the std::string element, I believe a std::map<string,double,MyOwnBinaryPredicate> with lower_bound and upper_bound would be more adequate.

事实是我想以一种有效的方式在 std::map 中 insert 元素.所以我想使用一个额外的迭代器来使 insert 更快.​​

The fact is that I want to insert elements in the std::map in an efficient way. So I want to use an additional iterator to make the insert faster.

我相信最简单的方法是使用 const_reverse_iterator 遍历 std::list 并使用 begin()std::map.

I believe the easiest way would be to use a const_reverse_iterator to go through the std::list and to use the begin() of the std::map.

你会这样做，还是一个坏主意?

Would you do it this way, or is it a bad idea?

谢谢！

推荐答案

如果你已经有一个排序列表，按照谓词Predicate排序，你可以这样做:p>

If you already have a sorted list, which is sorted according to the predicate Predicate, you can just do the following:

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).然后，您可以像使用其他地图一样直接使用地图.

The map constructor has linear time complexity if your list is already sorted, O(n*log n) otherwise. You can then work directly with the map as you would any other.

如果您稍后希望将结果返回到您的列表中，您可以做相反的事情:

If you later want the results back in your list you could just do the opposite:

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

这篇关于如何将 std::pair 的排序 std::list 转换为 std::map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！