Gibt es einen sortierten Container in AWL

Question

ALL,

Gibt es einen sortierten Container in STL? Was ich meine, ist folgendes:

Ich habe ein Std :: Vector wo Foo ist eine maßgeschneiderte Klasse. Ich habe auch einen Vergleicher, der die Felder der Klasse Foo vergleicht.

Nun, irgendwo in meinem Code ich tue:

std::sort(myvec.begin(), myvec.end(), comparator); 

, die den Vektor nach den Regeln sortieren werde ich in den Komparator definieren.

Jetzt möchte ich ein Element der Klasse Foo in diesem Vektor einfügen. Wenn ich könnte, würde Ich mag nur schreiben:

mysortedvector.push_back(Foo()); 

und was passieren würde, ist, dass der Vektor dieses neue Element gesetzt wird entsprechend dem Komparator an seinem Platz.

Stattdessen jetzt muß ich schreiben:

myvec.push_back(Foo()); 
std::sort(myvec.begin(), myvec.end(), comparator); 

, die nur eine Verschwendung von Zeit, da der Vektor bereits sortiert ist und alles, was ich brauche, ist in geeigneter Weise das neue Element zu platzieren.

Jetzt kann ich wegen der Art meines Programms nicht std :: map <> als ich habe keine Schlüssel/Wert-Paare, nur ein einfacher Vektor.

Wenn ich stl :: list benutze, muss ich nach jedem Einfügen erneut sortieren aufrufen.

Vielen Dank für Ihre Vorschläge.

Answer 1

Ja, std::set, std::multiset, std::map und std::multimap alle sortiert std::less als Standardvergleichsoperation verwendet wird. Die zugrunde liegende Datenstruktur ist typischerweise ein ausgewogener binärer Suchbaum, beispielsweise ein Rot-Schwarz-Baum. Wenn Sie also ein Element zu diesen Datenstrukturen hinzufügen und dann über die enthaltenen Elemente iterieren, wird die Ausgabe in sortierter Reihenfolge angezeigt. Die Komplexität des Hinzufügens von N Elementen zu der Datenstruktur ist O (N log N) oder das gleiche wie das Sortieren eines Vektors von N Elementen unter Verwendung einer beliebigen gemeinsamen O (log N) -Komplexitätssortierung.

In Ihrem spezifischen Szenario, da Sie keine Schlüssel/Wert-Paare haben, ist std::set oder std::multiset wahrscheinlich Ihre beste Wette.

Answer 2

Ich glaube nicht, die Funktionalität existiert in AWL, ein std :: vector kann nur Art mit Partition, nth_element, stable_partition, partial_sort, stable_sort und Art.

Sie könnten jedoch einen Wrapper für std :: vector

#include <vector> 

template <class T> 
class VectorSortWrapper 
{ 
public: 
    std::vector<T> m_VectorSorted; 

    void InsertSortedAscending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() <= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

    void InsertSortedDecending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() >= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

};