Wie man eine sortierte std :: list von std :: pair in eine std :: map konvertiert

Question

Ich habe eine std::list< std::pair<std::string,double> >, von der ich weiß, dass sie nach der std::string element sortiert ist.

Seit Ich mag würde eine Menge std::find_if basierend auf dem std::string Element tun, glaube ich, ein std::map<string,double,MyOwnBinaryPredicate> mit lower_bound und upper_bound würde mehr ausreichend sein.

Tatsache ist, dass ich insert Elemente in der std::map in einer effizienten Weise will. Daher möchte ich einen zusätzlichen Iterator verwenden, um die insert schneller zu machen.

Ich glaube, der einfachste Weg, ein const_reverse_iterator zu gehen durch die std::list nutzen würde und die begin() der std::map zu verwenden.

Würdest du es so machen, oder ist es eine schlechte Idee?

Danke!

Answer 1

Wenn Sie bereits eine sortierte Liste, die Predicate nach dem Prädikat sortiert ist, können Sie nur die folgenden:

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

Der map Konstruktor hat lineare Zeitkomplexität, wenn Ihre Liste bereits sortiert, O (n * log n) sonst. Sie können dann direkt mit der Karte arbeiten, wie Sie es auch tun würden.

Wenn Sie später die Ergebnisse zurück in Ihre Liste wollen könnten Sie tun genau das Gegenteil:

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

Answer 2

Sie können std :: copy und std :: Inserter verwenden:

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

weil der Iterator für eine Liste < Paar> einen Werttyp kompatibel ist < X, Y> 's Iteratoren abzubilden.

Answer 3

Ich würde einfach auf der Liste iterieren und jedes Paar in eine Karte einfügen oder die ordentliche Methode verwenden, die Luther Blissett beschrieben hat.
Die Tatsache, dass ich nicht verstehe, was Sie versuchen zu tun, bedeutet, dass es entweder zu unlesbarem Code führt oder dass Sie weit weg sind.
Warum machst du es so?
Können Sie den Code ändern, um eine Karte an Sie anstelle einer Liste an erster Stelle zurückzugeben?