Quelle est la plus belle façon de trouver une chaîne spécifique dans le vecteur?

Par exemple. J'ai une certaine structure:

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

Et d'un vecteur:

std::vector<s_Some> mSome;

Puis-je remplir ce vecteur avec beaucoup de s_Somes.

J'ai besoin de trouver un itérateur sur un seul s_Some dans ce vecteur, qui a une étiquette. Jusqu'à présent, je viens de parcourir l'ensemble de cette ordure et correspondre à tous les lable avec le voulait. Cela ressemble un peu stupide pour moi. Est-il un meilleur moyen pour le faire?

stackoverflow.com/questions/6277646/...

OriginalL'auteur akalenuk | 2009-02-03

  1. 10

    Option 1)
    Si vous êtes obligé d'utiliser les std::vector, mais une fois que le vecteur est rempli, il reste inchangé, alors vous pouvez trier le vecteur et utiliser le binaire de recherche. Le seul coût serait le tri ensuite et il n'y aura pas de surcharge supplémentaire. Temps de recherche est logarithmique O(logN).

    Option 2)
    Si vous avez la liberté et pouvez choisir différents types de structure de données, alors envisager l'utilisation de la carte (logarithmique) ou unordered_map ( attendus O(1), le pire O(n) ).

    J'ai juste remarqué que tu as dit que tu voulais pour correspondre à chaque étiquette avec celui qui est recherché. J'en conclus que vous pouvez avoir des étiquettes en double. Alors pour le point 2 utilisation correspondant multi_map conteneurs, tandis que pour le point 1, les choses deviennent un peu messier.

    OriginalL'auteur Anonymous

  2. 5

    Si vous êtes à la recherche seulement quelques fois ou si le 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 aurez à parcourir l'ensemble du vecteur.

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

    1. Trier le vecteur dans l'ordre croissant de chaînes de caractères (la façon dont elles se situent dans le dictionnaire, qui est).
    2. Une fois donc trié, utilisez binaire de l'algorithme de recherche pour toutes les recherches.

    Ce sera beaucoup plus rapide.

    OriginalL'auteur Frederick The Fool

  3. 3

    Utiliser un 

    std::multimap< string, s_Some > mSome;

    et 

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

    Trouver la première occurrence de la valeur de l'étiquette que vous voulez par

    mSome.find( lable_you_want );

    L'instance suivante sera trouvé par incrémentation de l'itérateur.

    cf. http://www.cppreference.com/wiki/stl/multimap/start

    Qui est, sauf si vous êtes obligé d'utiliser un std::vector.

    OriginalL'auteur Rob K

  4. 1

    Vous pouvez également utiliser un Carte de Listes

    OriginalL'auteur Tom Ritter

  5. 1

    Vous pouvez find_if algorithme pour ce faire. 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 lors de la recherche vous pouvez utiliser

    std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(),
                                                  mSome.end(),
                                                  isEqual(std::string("AAAA"));
    Mais c'est juste une plus belle façon d'écrire la boucle for. La complexité sera toujours linéaire, pas d'amélioration. STL find_if sera juste traverser le vecteur à partir du début jusqu'match/fin.
    Oui, j'ai pensé (à partir de la question de l'en-tête), il veut éviter d'écrire de la boucle de lui même..sans doute que je ne comprenais pas correctement à la question, je pensais que nous devons utiliser le vecteur
    Droite, les deux interprétations semblent plausibles 😉
    Maintenant, quand je l'ai lu à nouveau avec le point de vue des performances, je vois la phrase "il a l'air un peu stupide pour moi. Est-il un meilleur moyen de le faire?" de façon totalement différente..

    OriginalL'auteur Naveen