rimuovendo i duplicati in un vettore di stringhe

Question

Ho un vettore di stringhe:

std::vector<std::string> fName 

che contiene un elenco di nomi di file <a,b,c,d,a,e,e,d,b>.

Voglio sbarazzarsi di tutti i file che hanno duplicati e voglio conservare solo i file che non hanno duplicati nel vettore.

for(size_t l = 0; l < fName.size(); l++) 
{ 
    strFile = fName.at(l); 
    for(size_t k = 1; k < fName.size(); k++) 
    { 
     strFile2 = fName.at(k); 
     if(strFile.compare(strFile2) == 0) 
     { 
      fName.erase(fName.begin() + l); 
      fName.erase(fName.begin() + k); 
     } 
    } 
} 

Questo sta rimuovendo alcuni dei duplicati, ma ha ancora un paio di duplicati di sinistra, hanno bisogno di aiuto nel debugging.

Anche il mio input è simile a <a,b,c,d,e,e,d,c,a> e il mio output previsto è <b> poiché tutti gli altri file b, c, d, e hanno duplicati vengono rimossi.

Answer 1

#include <algorithm> 

template <typename T> 
void remove_duplicates(std::vector<T>& vec) 
{ 
    std::sort(vec.begin(), vec.end()); 
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); 
} 

Nota: questo richiede che T ha operator< e operator== definito.

Perché funziona?

std::sort sorta elementi usando il loro operatore minore di confronto

std::unique rimuove gli elementi consecutivi duplicati, confrontandoli con il loro operatore di uguale confronto

Che cosa devo fare solo gli elementi unici?

Allora è meglio utilizzare std :: map

#include <algorithm> 
#include <map> 

template <typename T> 
void unique_elements(std::vector<T>& vec) 
{ 
    std::map<T, int> m; 
    for(auto p : vec) ++m[p]; 
    vec.erase(transform_if(m.begin(), m.end(), vec.begin(), 
         [](std::pair<T,int> const& p) {return p.first;}, 
         [](std::pair<T,int> const& p) {return p.second==1;}), 
      vec.end()); 
} 

See: here.

Answer 2

Se comprendo correttamente le vostre esigenze, e non sono del tutto sicuro che lo faccia. Vuoi mantenere solo gli elementi nel tuo vettore di cui non ripetere, correggere?

Crea una mappa di stringhe a int, utilizzate per contare le occorrenze di ogni stringa. Cancellare il vettore, quindi copiare solo le stringhe che si sono verificate una sola volta.

map<string,int> m; 
for (auto & i : v) 
    m[i]++; 
v.clear(); 
for (auto & i : m) 
    if(i.second == 1) 
     v.push_back(i.first); 

Oppure, per il compilatore di funzionalità sfidato:

map<string,int> m; 
for (vector<string>::iterator i=v.begin(); i!=v.end(); ++i) 
    m[*i]++; 
v.clear(); 
for (map<string,int>::iterator i=m.begin(); i!=m.end(); ++i) 
    if (i->second == 1) 
     v.push_back(i->first); 

Answer 3

#include <algorithms> 

template <typename T> 
remove_duplicates(std::vector<T>& vec) 
{ 
    std::vector<T> tvec; 
    uint32_t size = vec.size(); 
    for (uint32_t i; i < size; i++) { 
    if (std::find(vec.begin() + i + 1, vec.end(), vec[i]) == vector.end()) { 
     tvec.push_back(t); 
    } else { 
     vec.push_back(t); 
    } 
    vec = tvec; // :) 
    } 
} 

Answer 4

è possibile eliminare i duplicati in O (log n) di runtime e O (n) Spazio:

std::set<std::string> const uniques(vec.begin(), vec.end()); 
vec.assign(uniques.begin(), uniques.end()); 

Ma il runtime O (log n) è un po 'fuorviante, perché lo spazio O (n) in realtà ha allocazioni dinamiche O (n), che sono costose in termini di velocità. Gli elementi devono anche essere comparabili (qui con operator<(), che supporta std::string come confronto lessicografico).

Se si desidera memorizzare solo gli elementi unici:

template<typename In> 
In find_unique(In first, In last) 
{ 
    if(first == last) return last; 
    In tail(first++); 
    int dupes = 0; 
    while(first != last) { 
     if(*tail++ == *first++) ++dupes; 
     else if(dupes != 0) dupes = 0; 
     else return --tail; 
    } 
    return dupes == 0 ? tail : last; 
} 

L'algoritmo prende sopra una serie ordinata e restituisce il primo elemento unico, in un tempo lineare e nello spazio costante. Per ottenere tutti gli uniques in un contenitore, è possibile utilizzarlo in questo modo:

auto pivot = vec.begin(); 
for(auto i(find_unique(vec.begin(), vec.end())); 
    i != vec.end(); 
    i = find_unique(++i, vec.end())) { 
    std::iter_swap(pivot++, i); 
} 
vec.erase(pivot, vec.end()); 

Answer 5

Nonostante abbia già risposto.

ordinamento e unico