sottrarre due std :: vector degli oggetti senza ordine

Question

Ho due vettori di oggetto. Qualcosa di simile:

std::vector<thing> all_things; 
std::vector<thing> bad_things; 

voglio ottenere un terzo vettore che contiene le good_things. In altre parole, ogni oggetto in all_thing che non si appartiene a bad_things:

std::vector<thing> good_things=subtract(all_things,bad_things); 

Tutte le idee su come implementare sottrarre in modo più efficiente e standard.

P.S i vettori possono NON essere ordinato perché la classe cosa non ha alcuna cosa da ordinare da. Grazie!

Modifica: e non voglio apportare alcuna modifica a all_things. ad es.

void substract(const std::vector<thing>& a, const std::vector<thing>& b); 

Answer 1

Dai commenti, i tuoi thing s possono essere ordinati, ma in modo insignificante.

E questo è ok.

Ordinarli senza senso.

Scrivere una funzione che richiede due thing s e dare loro un ordine privo di significato che è coerente e due cose si confrontano solo l'un l'altro se sono uguali.

Chiama questo bool arb_order_thing(thing const&, thing const&).

Ora std::sort entrambi i vettori e utilizzare std::set_difference.

Ora, questo può essere costoso se le cose sono costose da copiare.Quindi, invece, crea due vettori di thing const*, scrivi bool arb_order_thing_ptr(thing const*, thing const*) (quali dereferenze e confronti usando l'ordinamento senza significato), ordina i vettori di puntatori che lo usano, usa set_difference usando quello, quindi converti in un vector<thing>.

In alternativa, è consigliabile scrivere un hash thing const* (non uno std::hash<thing*> perché è globale e maleducato) e utilizzare unordered_set<thing const*> s per eseguire il lavoro manualmente. Hash il più piccolo dei due vettori, quindi eseguire un test std::copy_if contro l'hash sull'altro vettore.

Answer 2

Se non è possibile ordinarli, è possibile utilizzare il metodo forza bruta. Basta confrontare i vettori. Per esempio:

std::vector<Thing> all; 
std::vector<Thing> bad; 
std::vector<Thing> good (all.size()); 
auto it = std::copy_if (all.begin(), all.end(), good.begin(), 
    [&bad](const Thing& t){return std::find(bad.begin(), bad.end(), t) == bad.end();}); 
all.resize(std::distance(all.begin(),it)); 

Answer 3

Se thing è costoso da costruire/copia e il suo contenitore è lunga e mali sono schiaccianti, non è una buona idea di costruire un stesso array lungo 'non male'. In realtà una matrice di flag di all.size() x good.size() deve essere compilata in base al confronto thing. Se l'unicità è assicurata, la iterazione attraverso i cattivi potrebbe essere risparmiata. Ma O (N) è comunque la complessità.

Answer 4

Vorrei suggerire un codice simile a mkaes, ma con qualche aggiustamento:

std::vector<thing> substract(const std::vector<thing>& a, const std::vector<thing>& b) { 
    std::vector<thing> sub; 
    sub.reserve(a.size()); 
    for (const auto &item : a) { 
     if (std::find(b.begin(), b.end(), item) == b.end()) { 
      sub.push_back(a); 
     } 
    } 
    return sub; 
} 

E 'la versione brutale di ciò che si vuole raggiungere. Ma è il meglio che puoi fare se non riesci a ordinare elementi di vettori. Ricorda però che devi essere in grado di confrontare due oggetti del tipo item, il che significa che dovrai fornire operator==.