Jak przekonwertować posortowane std :: lista std :: pair na std :: map

Question

Mam std::list< std::pair<std::string,double> >, które wiem, że jest posortowane zgodnie z std::string element.

Ponieważ chciałbym zrobić wiele std::find_if opartą na elemencie std::string, wierzę std::map<string,double,MyOwnBinaryPredicate> z lower_bound i upper_bound byłoby bardziej odpowiednie.

Faktem jest, że chcę insert elementów w std::map w skuteczny sposób. Dlatego chcę użyć dodatkowego iteratora, aby przyspieszyć działanie insert.

Wierzę, najprostszym sposobem byłoby użyć const_reverse_iterator przejść przez std::list i używać begin() z std::map.

Czy zrobiłbyś to w ten sposób, czy to zły pomysł?

Dzięki!

Answer 1

Jeśli masz już posortowaną listę, która jest posortowana według orzecznika Predicate, wystarczy wykonać następujące czynności:

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

Konstruktor map ma liniową złożoność czas, jeśli lista jest już posortowane, O (n * log n) w przeciwnym razie. Następnie możesz pracować bezpośrednio z mapą, tak jak każdą inną.

Jeśli chcesz później wyniki z powrotem na liście można po prostu zrobić coś przeciwnego:

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

Answer 2

można użyć std :: kopię i std :: wprowadzające:

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

ponieważ iterator dla pary lista <> ma typ wartości zgodnego mapowania < x, y> 's iteratory.

Answer 3

Chciałbym po prostu powtórzyć listę i wstawić każdą parę do mapy lub użyć starannej metody opisanej przez Luthera Blissetta.
Fakt, że nie otrzymuję tego, co próbujesz zrobić, oznacza, że ​​spowoduje to nieczytelny kod lub że jesteś daleko.
Dlaczego robisz to w ten sposób?
Czy możesz zmienić kod, aby zamiast niego wyświetlić mapę zamiast na początku?