How to convert sorted std :: list std :: pair to std :: map

Question

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

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

The thing is, I want to insert elements in std::map efficient way. Therefore, I want to use an additional iterator to make insert faster.

I believe the easiest way is to use const_reverse_iterator to go through std::list and use begin() std::map .

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

Thanks!

Answer 1

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

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

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

If you later want to return the results in your list, you can simply do the opposite:

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

Answer 2

You can use std :: copy and std :: inserter:

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

because the iterator for the <pair> list has a value type compatible with the display of <X, Y> iterators.

Answer 3

I would simply iterate over the list and insert each pair into the map or use the neat method described by Luther Blissett.
The fact that I am not getting what you are trying to do means that it will either result in unreadable code or that you are gone. Why are you doing this? Can you change the code to return a map instead of a list in the first place?