Utilisation de insert() sur un std::vector vide lors d'un tri

Question

Je sais idéalement ce qu'il faut ajouter à un std::vector sans s'inquiéter, je devrais utiliser push_back() . Cependant, mon problème est que j'ai besoin d'un code propre pour vérifier si la valeur que je saisis se trouve déjà dans le fichier std::vector et si ce n'est pas le cas, je dois les classer par ordre séquentiel et croissant. Pour ce faire, je fais :

vector<Book>::iterator it;
it = std::find(books.begin(), books.end(), b);
if (it != books.end()) {
    *it = b; // if b exists in books, overwrite the iterator
}
else {
    vector<Book>::iterator _it;
    _it = lower_bound(books.begin(), books.end(), b);
    books.insert(_it, b); // here on an empty vector, _it has no values
}

En else ne s'exécutera que si la valeur b n'existe pas encore dans le std::vector . S'il s'agit de la première valeur vérifiée, l'élément else s'exécute (puisqu'il est vide) et le std::iterator est à books[0] ( ?).

Ce qui me rend prudent quant à l'utilisation de cette méthode, c'est que lors du débogage, sur la page insert() la valeur de _it indique "Error Reading...." pour chacun des membres pour lesquels le std::iterator pointe vers. Le programme fonctionne maintenant et produit les résultats escomptés, mais est-ce par erreur ?

Answer 1

Ce que vous faites fonctionne bien. Toutefois, ce n'est pas la méthode la plus efficace. L'utilisation de std::find ne tire pas profit du fait que les données du vecteur sont trié Il visite chaque élément jusqu'à ce qu'il trouve le bon.

Au lieu de std::find vous pouvez utiliser std::lower_bound depuis le début, car il trouvera votre élément s'il existe et, s'il n'existe pas, il trouvera le bon endroit pour en insérer un nouveau.

De plus, il utilisera une recherche binaire, ce qui le rendra beaucoup plus rapide que le système std::find . De plus, vous ne trouverez pas deux fois le point d'insertion/remplacement.

Quelque chose comme ceci devrait faire l'affaire :

void insert_or_replace(std::vector<Book>& books, Book const& b)
{
    std::vector<Book>::iterator it;

    it = std::lower_bound(books.begin(), books.end(), b);

    if(it != books.end() && *it == b)
        *it = b;
    else
        books.insert(it, b);
}

Answer 2

Le code est assez bon. Pour un vecteur vide lower_bound(books.begin(), books.end(), b) renverra end() itérateur. En le passant à std::vector::insert fonctionnera parfaitement.

pos - itérateur devant lequel le contenu sera inséré. pos peut être le end() itérateur

et de votre inquiétude :

Ce qui me rend prudent quant à l'utilisation de cette méthode, c'est que lors du débogage, sur la page insert() la valeur de _it indique "Error Reading...." pour chacun des membres pour lesquels le std::iterator pointe vers.

En effet, la end() pointe sur la position suivant le dernier élément, il n'est donc pas valide de déférer sur lui (pour obtenir un élément inexistant).

Answer 3

Il s'agit d'un comportement bien défini.

lower_bound renverra l'itérateur de fin ( books.end() dans votre cas) pour une plage vide ou si b doit venir après le dernier élément. insert ajoutera le nouvel élément avant l'itérateur qui lui a été transmis, ce qui fait que ce sera avant end . Dans un vecteur vide, cela aura pour effet d'ajouter l'élément au vecteur.