Esiste un contenitore ordinato in STL

Question

ALL,

Esiste un contenitore ordinato in AWL? Quello che voglio dire è il seguente:

Ho un std :: vector dove Foo è una classe personalizzata. Ho anche un comparatore di qualche tipo che confronterà i campi della classe Foo.

Ora, da qualche parte nel mio codice che sto facendo:

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

che ordinare il vettore secondo le regole io definisco nel comparatore.

Ora voglio inserire un elemento di classe Foo in quel vettore. Se potessi vorrei scrivere solo:

mysortedvector.push_back(Foo()); 

e ciò che sarebbe accaduto è che il vettore metterà questo nuovo elemento in base al confronto al suo posto.

Invece, in questo momento devo scrivere:

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

che è solo uno spreco di tempo, dal momento che il vettore è già ordinato e tutto quello che serve è quello di posizionare il nuovo elemento in modo appropriato.

Ora, a causa della natura del mio programma, non posso usare std :: map <> poiché non ho coppie chiave/valore, solo un vettore semplice.

Se si utilizza stl :: list, è necessario chiamare di nuovo ordinamento dopo ogni inserimento.

Grazie per tutti i suggerimenti che è possibile fornire.

Answer 1

Sì, std::set, std::multiset, std::map e std::multimap sono tutti ordinati utilizzando std::less come l'operazione di confronto di default. La struttura dati sottostante utilizzata è in genere un albero di ricerca binario bilanciato come un albero rosso-nero. Quindi se si aggiunge un elemento a queste strutture di dati e poi si itera sugli elementi contenuti, l'output sarà ordinato. La complessità dell'aggiunta di N elementi alla struttura dei dati sarà O (N log N), o lo stesso di ordinare un vettore di N elementi usando qualsiasi ordinamento di complessità O (log N) comune.

Nel tuo scenario specifico, dal momento che non hai coppie chiave/valore, std::set o std::multiset è probabilmente la soluzione migliore.

Answer 2

Non credo che la funzionalità esiste in STL, uno std :: vector può solo tipo con partizione, nth_element, stable_partition, partial_sort, stable_sort e sorta.

Si potrebbe tuttavia creare un wrapper per 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; 
      }  
     } 
    } 

};