J'ai ce vecteurObtenir le nombre de chaînes dans le vecteur C++
vector <string> data
data = ["this is", "data that", "is in", "this is", "vector", "vector", "vector"]
comment puis-je obtenir un vecteur (ou un tableau 2D) qui supprime les doublons et la place a des comptes pour chaque ième entrée?
-à-dire
results = [("this is", 2), ("data that", 1), ("is in", 1), ("vector", 3)]
La solution simple serait d'accumuler les valeurs uniques et leurs comptes en une carte:
std::map<std::string, std::size_t> results;
std::for_each(begin(data), end(data), [&](std::string const& s)
{
++results[s];
});
Cela a linearithmic (nlogn) la complexité du temps, mais parce qu'il doit faire une copie de chaque valeur de chaîne distincte, il peut être plutôt coûteux. Vous pouvez également trier la liste sur place, puis compter le nombre de chaque valeur, ce qui serait probablement plus efficace si vous disposez d'une implémentation de std::string sensible au déplacement.
Vous pouvez également utiliser un 'std :: reference_wrapper
que diriez-vous d'une table de hachage? http://en.wikipedia.org/wiki/Hash_table (complexité O (n)) –
@MihaiTodor: Il suffit de changer 'std :: map' en' std :: unordered_map' – Blastfurnace
Xeo, j'ai essayé BEAUCOUP d'approches. c'est-à-dire pour chaque chaîne de données, regardez le reste des éléments dans les données, et incrémentez le nombre pour chaque correspondance de s. on dirait que c'est O (n^2) mais je cherche quelque chose d'un peu plus efficace – CyberShot
Vous pourriez vouloir essayer un 'std :: map' ... vous pouvez indexer par la chaîne, et augmenter le compteur comme nécessaire. 'map's sont triés par clé (chaîne ici), et ne peuvent pas avoir de doublons. Prendre une liste/un vecteur non triés de chaînes et peupler une carte est une opération O (N x log2N). –
Cela ressemble à une table de collision (hachage) pour moi. Essayez de le chercher. –