views:

141

answers:

3

Hello!

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!

+3  A: 

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.

Luther Blissett
std::inserter()? well you learn something new everyday :)
the_drow
+1: This has equally good performance and also works with an existing map
grddev
Is using `std::inserter(the_map,the_map.begin())` or `std::inserter(the_map,the_map.end())` better here, given that the list is sorted?
spong
Actually I have a doubt, the problem is that `end` won't be reactualised, ie it's `end` at the time the `inserter` is created, it does not stay `end`, and therefore I don't know if the complexity is linear.
Matthieu M.
Hmm, looking at [insert_iterator](http://www.cplusplus.com/reference/std/iterator/insert_iterator/), the performance is not great, since upon insertion the iterator after the previous insert, which means the "slow" map insertion will be performed.
grddev
I have about the same performance using this solution with `begin()` or `end()`. Thanks for this really interesting answer.
wok
A: 

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?

the_drow
I have to use a std::list in the first place, because there are elements which have the same std::string key. Then there are operations which let me use a std::map in the end. I might consider using a std::map a bit earlier in the process, but the question is still relevant in this case.
wok
have you considered using std::multimap? See here: http://www.sgi.com/tech/stl/Multimap.html
the_drow
+7  A: 

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());
grddev
+1: I forgot about the linear ctor for sorted. Great!
Luther Blissett
This answer's advantage is its simplicity. Thank you!
wok