Confronto personalizzato, uguaglianza ed equivalenza con il STL

Confronto personalizzato, uguaglianza ed equivalenza con il STL

Iniziamo con il seguente estratto di codice: 

std::vector< std::pair<int, std::string> > v1 = ... // v1 is filled with data
std::vector< std::pair<int, std::string> > v2 = ... // v2 is filled with data
std::vector< std::pair<int, std::string> > results;
  
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
  
std::set_difference(v1.begin(), v1.end(),
                    v2.begin(), v2.end(),
                    std::back_inserter(result),
                    compareFirst);

Ci sono 2 set di dati rappresentati da 2 vettori ordinati v1 e v2, su cui applichiamo un std::set_difference (vedi Algoritmi sugli insiemi). Questo std::set_difference scrive il suo output in results , con std::back_inserter assicurando che tutti gli output vengano respinti nei risultati.

Una particolarità però:a std::set_difference viene fornito un operatore di confronto personalizzato :compareFirst .

Per impostazione predefinita, std::set_difference confronta gli elementi con il confronto predefinito su std::pair (che confronta sia il primo che il secondo elemento della coppia), e qui con compareFirst vogliamo confrontare le coppie solo sul loro primo elemento. compareFirst non è nell'STL, quindi cercheremo di implementarlo noi stessi.

Prima di passare all'implementazione, abbiamo già un interessante take away qui. Anche se std::set_difference aspettarsi che il suo input sia ordinato, è possibile utilizzarlo (o qualsiasi algoritmo sugli elementi ordinati) basato su un comparatore (chiamiamolo C) diverso dal comparatore utilizzato per l'ordinamento, a condizione che gli elementi siano ordinati anche per questo comparatore C. Nel nostro caso, ad esempio, utilizziamo un std::set_difference che confronta le coppie in base ai loro primi elementi, sebbene queste coppie siano state ordinate sia in base al primo che al secondo elemento. Ma poiché ciò implica che sono a fortiori ordinato per primo, è completamente OK per farlo.

Ora implementiamo compareFirst . Un codice naturale, ingenuo, al primo tentativo sarebbe simile a:

bool compareFirst(const std::pair<int, std::string>& p1, const std::pair<int, std::string>& p2)
{
    return p1.first == p2.first; // not final code, bug lurking here!
}

In realtà, questa implementazione non darà affatto i risultati attesi. Ma perché?? Dopotutto, set_difference dovrebbe controllare se un dato elemento è uguale a un altro nell'altra raccolta, giusto?

Il minimo che possiamo dire è che questo sembra del tutto innaturale e il resto di questo post consisterà nel capire come siamo arrivati ​​a questo e perché in realtà è del tutto normale.

Per capirlo, dobbiamo considerare l'STL come diviso approssimativamente in 2 parti:la parte che opera su elementi SORTED e la parte che opera su elementi che NON sono SORTED.

La parte SORTED dell'STL

In questa parte ci sono contenitori associativi (std::map , std::multimap , std::set , std::multiset ), perché i loro elementi sono ordinati.

Anche alcuni algoritmi rientrano in questa categoria, perché presuppongono che gli elementi su cui operano siano ordinati:std::set_difference , std::includes o std::binary_search per esempio.

La parte UNSORTED del STL

In questa parte ci sono contenitori di sequenza (std::vector , std::list , std::deque e std::string ), perché i loro elementi non sono necessariamente ordinati.

E gli algoritmi che rientrano in questa categoria sono quelli che non necessitano che i loro elementi siano ordinati, come std::equal , std::count o std::find per esempio.

Confronto tra elementi

Esistono due modi per esprimere "a è uguale a b" in C++:

  • il modo naturale:a == b . Questo si chiama uguaglianza . L'uguaglianza si basa su operator== .
  • altrimenti:a non è minore di b e b non è minore di a, quindi !(a<b) && !(b<a) . Questo si chiama equivalenza . L'equivalenza si basa su operatore .

Quindi sorgono naturalmente due domande sull'equivalenza.

In che cosa differisce dall'uguaglianza?

Per tipi semplici come int , e in realtà per la maggior parte dei tipi in pratica, l'equivalenza è effettivamente la stessa cosa dell'uguaglianza. Ma come indicato da Scott Meyers nell'articolo STL effettivo 19, ci sono alcuni tipi non troppo esotici in cui i due non sono la stessa cosa, come ad esempio le stringhe senza distinzione tra maiuscole e minuscole.

Perché un modo così inverosimile di esprimere una cosa semplice?

Quando un algoritmo confronta gli elementi in una raccolta, è facile capire che deve esserci solo un modo di confrontarli (avere più comparatori è ingombrante e crea un rischio di incoerenza). Quindi è necessario scegliere tra il confronto basato su operator== o su operator< .

Nella parte SORTED dell'STL la scelta è già fatta:per definizione di ordinamento, gli elementi devono essere confrontabili con operator<(o una funzione simil (operatore<) personalizzata). La parte UNSORTED sull'altro lato non ha questo vincolo e può usare l'operatore naturale==.

Implementazione del comparatore

Il NON ORDINATO parte dell'STL utilizza operator== per eseguire confronti, mentre il ORDINATO parte utilizza operatore . E gli operatori di confronto personalizzati devono seguire questa logica.

Ora capiamo come implementare il nostro operatore personalizzato compareFirst per std::set_difference , che opera su elementi ordinati:

bool compareFirst(const std::pair<int, std::string>& p1, const std::pair<int, std::string>& p2)
{
    return p1.first < p2.first; // correct, STL-compatible code.
}

Tutto questo è fondamentale da comprendere per utilizzare l'STL in modo efficiente.