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

Question

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

因为我希望做了很多std::find_if基于对std::string元素,相信std::map<string,double,MyOwnBinaryPredicate>与lower_bound和upper_bound会更充足.

事实是,我希望以有效的方式使用insert元素std::map.所以我想使用额外的迭代器来insert加快速度.

我认为,最简单的方法是使用一个const_reverse_iterator要经过std::list和使用begin()的std::map.

你会这样做,还是一个坏主意？

谢谢!

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());