Discussion :

[aperdemak]

Bonjour, je voudrais savoir comment garder une trace d'un élément dans un vector, un peu comme l'on garderait un pointeur d'une struct que l'on aurait ajoutée dans un array en c.
Merci d'avance.

[dalfab]

Bonjour,

Si le vector<> est constant en taille, il suffit de faire comme pour un tableau en utilisant un pointeur ou une référence sur l'élément. int* px = &vecteur[i];.
Si le vector<> peut être modifié, les données bougeront il est impossible de pointer dessus. S'il s'agit d'un vector de pointeur (brut ou unique), on peut aussi pointer sur l'élément pointé. S'il s'agit d'un vector de shared_ptr, on peut garder la valeur du shared_ptr sous la forme d'un shared_ptr ou d'une weak_ptr.

[aperdemak]

donc si mes éléments ne sont pas des pointeurs je suis obligé d'implémenter un système avec des identifiants et de parcourir tout le vecteur à chaque fois que j'ai besoin d'un élément ?

[dalfab]

Si le vector<> n'évolue que par ajout/suppression à le fin, on peut aussi conserver l'index de la position dans le vector<>. Sinon on devra rechercher l'élément par son identifiant, mais dans ce cas peut-être que le vector<> n'est pas la collection la plus adaptée. On peut utiliser :

• list<> qui garanti une position fixe de ses éléments mais qui n'a plus d'accès direct et qui consomme de la place.
• set<> qui gère des éléments triés
• map<> qui permet d'associer une clef à un contenu
• un vector<> ou deque<> trié pour une recherche plus rapide
• ou les autres (multi_set<>, multi_map<>, unordered_set<>, forward_list<>, ...)

[Pyramidev]

Bonjour,

Si les éléments du std::vector ne sont pas des pointeurs :

• Si la taille du vecteur ne bouge plus, on peut garder des pointeurs ou des références vers les éléments du vecteur. Ils resteront valides.
• Si la taille du vecteur varie peu souvent et qu'on a un système d'identifiants, après chaque variation (ajout ou suppression), on peut appeler std::sort pour trier le vecteur. Alors, pour trouver un élément avec une complexité en O(log n), on peut utiliser std::binary_search ou std::partition_point.
• Si la taille du vecteur varie souvent mais qu'on veut souvent y chercher un élément, alors ça veut dire que le choix de std::vector n'est vraisemblablement pas adapté.

Il existe std::set et std::map qui permettent d'ajouter et de rechercher des éléments en O(log n). Ils sont généralement implémentés sous la forme d'un arbre binaire de recherche. Les pointeurs et les références vers les éléments restent valides tant que l'élément existe dans le conteneur.

Il y a aussi std::unordered_set et std::unordered_map qui permettent d'ajouter et de rechercher des éléments avec une complexité constante. Ils sont implémentés sous la forme d'une table de hachage. Les pointeurs et les références vers les éléments peuvent être invalidés par l'ajout d'élément dans le conteneur.

Tu as aussi std::deque qui ressemble un peu à std::vector. Cependant, quand tu ajoutes un élément au début ou à la fin, tous les pointeurs déjà existants vers tes éléments restent valides. C'est uniquement quand tu insères un élément ailleurs que tu invalides les pointeurs vers les autres éléments. Sous le capot, c'est un ensemble de petits tableaux de taille fixe qui restent au même endroit en mémoire. Quand on ajoute un élément à la fin, s'il n'y a pas assez de place dans le dernier petit tableau, un nouveau petit tableau est alloué sans que l'on touche aux autres petits tableaux.

Remarque : Une partie de mon message fait un peu doublon avec le dernier message de dalfab, car je l'avais commencé avant qu'il ne publie le sien.