Quel est le meilleur moyen de trouver une chaîne spécifique dans le vecteur?

Question

Par exemple. J'ai une certaine structure:

s_Some{ 
    std::string lable; 
    s_some_junk some_junk; 
}; 

Et un vecteur:

std::vector<s_Some> mSome; 

Et puis je remplis ce vecteur avec beaucoup de s_Somes.

J'ai besoin de trouver un itérateur pour un seul s_Some dans ce vecteur, qui a une étiquette spécifique. Jusqu'à présent, je viens de parcourir toute cette jonque et de faire correspondre chaque lable avec celui voulu. Cela me semble un peu stupide. Y a-t-il une meilleure façon de le faire?

Answer 1

Option 1) Si vous êtes obligé d'utiliser le std :: vecteur, mais une fois que le vecteur est rempli, il reste inchangé, alors vous pouvez trier le vecteur et l'utilisation la recherche binaire. Le seul coût serait le tri alors et il n'y aura pas de frais supplémentaires. Le temps de recherche est logarithmique O (logN). Si vous avez la liberté et pouvez choisir une structure de données différente, alors utilisez la carte (également logarithmique) ou unordered_map (O (1) attendu, O (n) pire).

Je viens de remarquer que vous avez dit que vous vouliez faire correspondre chaque étiquette à celle recherchée. Donc, je conclus que vous pouvez avoir des étiquettes en double. Ensuite, pour le point 2, utilisez les conteneurs multi_map correspondants, tandis que pour le point 1, les choses deviennent un peu plus compliquées.

Answer 2

Si vous ne cherchez que quelques fois ou si votre vecteur est susceptible d'avoir un contenu différent à chaque fois que vous effectuez une recherche, il n'y a malheureusement pas d'alternative; vous devrez parcourir tout le vecteur.

Si toutefois votre vecteur ne va pas changer une fois créé et vous devez exécuter un grand nombre de recherches, faites ceci:

1. Trier le vecteur dans l'ordre croissant des chaînes (la façon dont ils se trouvent dans le dictionnaire, c'est-à-dire). Une fois ainsi triés, utilisez binary search algorithm pour toutes les recherches.

Ce sera beaucoup plus rapide.

Answer 3

Vous pouvez également utiliser un Map de Lists

Answer 4

Vous pouvez trouver l'algorithme pour cela. Définir un prédicat quelque chose comme ceci:

struct isEqual 
{ 
    isEqual(const std::string& s): m_s(s) 
    {} 
    bool operator()(S_Some& l) 
    { 
     return l.lable == m_s; 
    } 

    std::string m_s; 
}; 

Et pendant que vous la recherche pouvez utiliser

std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(), 
                mSome.end(), 
                isEqual(std::string("AAAA")); 

Answer 5

Utilisez un

std::multimap< string, s_Some > mSome; 

et

mSome.insert(std::make_pair(aSome.lable, aSome)); 

Trouver la première instance de la valeur de lable que vous voulez par

mSome.find(lable_you_want); 

L'instance suivante sera trouvée en incrémentant l'itérateur.

cf. C'est-à-dire, sauf si vous devez utiliser un vecteur std :: vector.