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 ele开发者_开发问答ment
.
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!
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());
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.
I would just iterate on the list and insert every pair into a map or use the neat method Luther Blissett has described.
The fact that I don't get what are you trying to do means it will either result in unreadable code or that you are way off.
Why are you doing it this way?
Can you change the code to return a map to you instead of a list in the first place?
精彩评论