Spingendo dati unici nel vettore

Question

ho i seguenti dati:

FolioA Name1 100 
FolioA Name2 110 
FolioA Name3 100 
FolioB Name1 100 
FolioB Name3 106 
FolioC Name1 108 
FolioC Name2 102 
FolioC Name3 110 

voglio inserire solo nomi unici (cioè Name1, Nome2 e NAME3, ogni volta) in

std::vector<std::string> name; 

come ho iterare attraverso i dati.

Così, ho il seguente codice dove ho memorizzato i dati in una mappa chiamata di prova:

std::map<std::string, std::map<std::string, double> >test; 
std::map<std::string, std::map<std::string, double > >::iterator it1 = test.begin(), end1 = test.end(); 
    while (it1 !=end1) { 
     std::map<std::string, double>::iterator it2 = it1->second.begin(), end2=it1->second.end(); 
     **name.push_back(it2->first);** 
     ++it2; 
    } 
    ++it1; 
} 

Ma, attualmente spingendo i dati nel nome il modo in cui io sono ha 3 istanze di Name1, 2 di Name2 e 3 di Name3, che è previsto dal mio codice. Come faccio a correggerlo per avere solo nomi univoci.

Answer 1

Dal momento che si desidera mantenere prima istanza per un determinato nome, si dovrà eseguire un ricerca del nome ad un certo punto. Un semplice algoritmo che coinvolge solo il vostro vettore sarebbe quella in grado di verificare se la voce è già esistente utilizzando std::find

std::vector<std::string> name; 

.... 
if (std::find(name.begin(), name.end(), someName) == name.end()) { 
    // someName not in name, add it 
    name.push_back(someName); 
} 

Ma qui si sta eseguendo una ricerca ogni volta che si desidera inserire un elemento, e questo (per sé) è fino alla complessità O(N), fornendo O(N*N) per l'intero algoritmo. Quindi puoi ottimizzare utilizzando un contenitore intermedio con una rapida ricerca, come ad esempio un std::set come suggerito da @Chad e che ha la complessità O(logN) per la ricerca, fornendo O(N*logN) in generale, o un contenitore hash come C++ 11 std::unordered_set, che ha una visualizzazione del tempo costante, fornendo una complessità complessiva di ~ O (N).

std::unordered_set name_set; 
.... 

// still need to search, since you want to keep 
// the first instance of each name, and not the last. 
// But unordered_set performs the look-up at insertion, 
// only inserting if someName not already in the set 
name_set.insert(someName); 

e poi, seguendo l'esempio di @ Chad,

std::vector<std::string> name(names_set.begin(), name_set.end()); 

Se non si dispone di C++ 11, hash mappa alternative sono boost::hash_map e tr1::hash_map.

Answer 2

Nel caso in cui non ti importa quale istanza si vuole inserire nella vostra struttura di dati, std::set sarebbe Server vostro scopo

Answer 3

Forse dovresti usare un'altra mappa di un vettore per avere nomi univoci.

std :: map < std :: string, double> name;

Answer 4

È richiesto il codice di esempio, ecco come ho avrei fatto:

std::set<std::string> unique_names; 

// ... 
while (it1 !=end1) 
{ 
    // ... 
    // **name.push_back(it2->first);** 
    unique_names.insert(it2->first); 
} 

std::vector<std::string> name(unique_names.begin(), unique_names.end()); 

Answer 5

lista ha la capacità di .Sort() e poi .unique(), che vi fornirà.

è possibile scorrere su di esso con un iteratore e inizializzarlo con initializer_list.

che i dati sembra in realtà più simile a una struct per me:

#include <iterator> 
#include <list> 
#include <string> 
#include <fstream> 

typedef struct NODE_S { 
    string name1, name2; 
    int n; 
} NODE_S NODE; 

bool compare_NODE (NODE first, NODE second) 
{ 
    unsigned int i=0; 
    if (first.name1 < second.name1) { 
     return true; 
    } else if (first.name2 < second.name2) { 
     return true; 
    } else if (first.n < second.n) { 
     return true; 
    } else { return false;} 
} 


bool readfile(list<NODE>& ln, string filepath) { 
    std::ifstream filein; 
    NODE n; 
    filein.open(filepath.c_str(), std::iofstream::in); 
    if (!filein.good()) { 
     filein.close(); 
     std::cerr << "ERROR: unable to open file \"" << filepath << "\" or file is zero-length." << std::endl; 
     return false; 
    } 
    do { 
     filein >> n.name1 >> n.name2 >> n.name3 >> std::skipws; 
     ln.push_back(n); 
     ln.sort(compare_NODE); 
     ln.unique(); 
     //add node to list 

    } while (!filein.good()); //can use .eof here, but if bad disk blocks... 
    filein.close(); 
    return true; 
} 


int main(int argc, char * argv[], char * envp[]) { 
    string filepath="somefile.txt"; 
    if (!readfile(filepath)) { 
     return 1; 
    } 
    list<NODE>::iterator lni; 
    for (lni = ln.begin(); lni != ln.end(); lni++) { 
     std::cout<<lni->name1<<' '<<lni->name2<<' '<<lni->n<<std::endl; 
    } 
    return 0; 
} 

http://www.cplusplus.com/reference/stl/list/sort/

http://www.cplusplus.com/reference/stl/list/unique/

Answer 6

Nel caso in cui si desidera utilizzare std :: vector e non si cura di complessità di esecuzione (questo è O (n^2), questo è un modo più idiomatico:

void add_once(std::vector<std::string>& vec, const std::string& element) { 
    std::remove(vec.begin(), vec.end(), element); 
    vec.push_back(element); 
}