Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

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.

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.

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?

Thanks!

like image 911
Wok Avatar asked Aug 05 '10 07:08

Wok


2 Answers

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

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());
like image 127
grddev Avatar answered Oct 02 '22 17:10

grddev


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 a list< pair > has a value type compatible to map< X,Y >'s iterators.

like image 21
Nordic Mainframe Avatar answered Oct 02 '22 16:10

Nordic Mainframe