Pointeurs : destruction / concaténation

Version imprimable

08/06/2014, 20h29
StingerBell

Pointeurs : destruction / concaténation

Bonjour,

j'ai un vecteur qui contient des pointeurs pointant sur des objets d'une class "truc" que j'ai créé.

Ma première question est concernant la concaténation. Est-il possible d'une manière rapide et efficace de concaténer deux vecteurs de telle façon que les pointeurs qui pointent sur le même objet ne se retrouvent pas en "double" ? Est-ce que cela existe déjà ou je dois créer une fonction moi-même ? En gros si vecteur A et vecteur B tous les deux contient un pointeur sur le même objet, il n'y aura pas deux pointeurs dans le vecteur concaténé.

Deuxième question concerne la destruction. Je voudrais pouvoir fusionner deux objets de ma class "truc". Pour cela je voudrais mettre les attributs du second objet dans le premier (pas de problème) et supprimer le second objet. Pour supprimer le second objet je pense qu'il faut que j'utilise le destructeur de copie. Mais dans ce cas la, qu'adviendra-t-il de mes pointeurs sur les objets détruits ? Seront-ils toujours dans mon vecteur de pointeur ? Est-ce qu'il y a moyen de détruire automatiquement les pointeurs qui pointent sur des objets "détruits" ?

Merci !
08/06/2014, 23h33
dragonjoker59

Pour ton premier problème, tu peux envisager plusieurs méthodes :
- Utilisation de std::set => Eléments uniques triés
- Utilisation de std::unordered_set => Eléments uniques non triés (plus adapté aux pointeurs)
- Utilisation de std::vector/list + std::unique + std::remove => Solution par défaut, qui marche mais pas la plus adaptée.

Pour ton cas je partirais sur un std::unordered_set.

Pour ton second problème, les std::shared_ptr résoudront ton soucis.
Par contre je te conseille de faire attention à la responsabilité (qui crée le pointeur, qui le détruit) pour savoir exactement quel est ton besoin.
09/06/2014, 10h28
StingerBell

Salut, merci beaucoup pour ta réponse,

concernant les shared_ptr j'ai regardé la documentation et je ne suis pas persuadé que cela résolve mon problême (ou problablement j'ai mal compris le truc...). De ce que j'ai compris les shared_ptr permettent de créer plusieurs pointeurs qui partagent la propriété de l'objet avec un compteur du nombre de pointeurs pointant sur l'objet et donc l'objet ne sera détruit que lorsque tous les pointeurs seront détruit.

Moi ce que je veux faire c'est détruire "manuellement" l'objet et automatiquement détruire tous les pointeurs qui pointaient sur l'objet. En fait pour expliquer vraiment, j'ai une classe "Zone" avec des attributs ainsi qu'un vecteur de pointeurs pointant sur des autres objets de classe "Zone" qui sont les voisins d'une zone donnée. En gros chaque zone a un vecteur d'une dizaine de pointeurs pointant sur ses voisins. Je voudrais pouvoir détruire un objet de class zone et automatiquement tous les pointeurs qui sont dans les vecteurs de ses voisins soient détruit (de telle façon qu'il ne reste pas de vecteur avec des pointeurs qui ne pointent sur rien du tout).

Est-ce que shared_ptr permet cela ? (désolé si c'est le cas et j'ai mal compris le principe ...)

Aussi, serait-il possible / plus performant / plus logique de procéder par référence plutot que par pointeur pour l'example ci-dessus ? J'ai du mal a voir la différence entre les deux.

Merci beaucoup pour ton aide.
09/06/2014, 11h05
foetus

Tu as eu la moitié de l'histoire :mouarf:

Il y a les shared_ptr et les weak_ptr.
Plus l'usine: make_shared

C'est pour cela que dragonjoker59 te dit de "faire attention à la responsabilité (qui crée le pointeur, qui le détruit) pour savoir exactement quel est ton besoin"
09/06/2014, 16h20
jblecanard

Salut

Citation:

Envoyé par dragonjoker59

Pour ton premier problème, tu peux envisager plusieurs méthodes :
- Utilisation de std::set => Eléments uniques triés
- Utilisation de std::unordered_set => Eléments uniques non triés (plus adapté aux pointeurs)
- Utilisation de std::vector/list + std::unique + std::remove => Solution par défaut, qui marche mais pas la plus adaptée.

Pour ton cas je partirais sur un std::unordered_set.

Ces méthodes sont toutes valides. Cependant, je n'irais pas jusqu'à me prononcer sur le choix à faire, car on n'a pas assez d'informations sur ton utilisation pour savoir ce qui est le plus adapté. Par exemple, std::set et std::unordered_set sont mauvais pour l'accès aléatoire (accès par l'indicie de l'élément, et par extension, accès par parcours de tous les éléments). Du coup, si ton algo a plus tendance à parcourir tes collections et que les insertions/fusions sont moins fréquentes que les lectures, il vaut peut-être mieux garder std::vector qui est imbattable sur l'accès aléatoire. Un "sorted vector" (un vecteur que tu maintiens trié en l'encapsulant dans un objet supérieur) peut aussi être une alternative très intéressante si tu as besoin à la fois d'un accès aléatoire et d'un accès par la clé (la clé ici étant le pointeur de l'objet).

Si tu as un doute, la meilleure manière d'arbitrer reste d'implémenter les deux techniques entre lesquelles tu hésites et de faire un test de performances.

Citation:

Envoyé par StingerBell

Je voudrais pouvoir détruire un objet de class zone et automatiquement tous les pointeurs qui sont dans les vecteurs de ses voisins soient détruit (de telle façon qu'il ne reste pas de vecteur avec des pointeurs qui ne pointent sur rien du tout).

Est-ce que shared_ptr permet cela ? (désolé si c'est le cas et j'ai mal compris le principe ...)

En effet, en utilisant shared_ptr::reset() et weak_ptr, tu peux obtenir cette fonctionnalité. Mais j'attire ton attention sur plusieurs choses:
- shared_ptr est coûteux, car il est fait pour que l'accès concurrent à un objet via plusieurs threads (et un shared_ptr par thread, ou plus) soit safe. De fait, si tu n'as qu'un thread, tu vas payer pour quelque chose que tu n'utilises pas.
- Cette technique impose de stocker au moins un shared_ptr quelque part et des weak_ptr ailleurs. Peut-être que ton algo n'est pas pensé comme ça et va mal s'adapter à cet état de fait.
- Si tu invalides une série que weak_ptr en détruisant le shared_ptr "maître", les weak_ptr restants seront toujours dans les collections (vector ou autre, selon le choix fait dans la première partie). Ca peut être intéressant si tu fais un nettoyage "différé", c'est à dire
si tu profites d'un parcours de la collection qui a un autre but pour trouver les références invalides et les nettoyer, ok. Mais peut-être que tu voudras nettoyer les collections des pointeurs invalides dès la destruction effectuée, dans lequel cas, shared_ptr ne te rendra pas un bien grand service.

Sinon à propos des références, je t'avoue que j'ai un peu la flemme de coucher l'explication classique ici (Koala01, tu veux pas :mrgreen: ?), la FAQ devrait te renseigner assez sur le sujet. Des collections de références, ça ne se fait pas trop. A la limite, des collections de reference_wrapper, oui, pourquoi pas, j'ai déjà fait ça.
09/06/2014, 17h21
Bousk

vector est généralement le moins mauvais choix par défaut. Commencer par vector puis voir si on peut faire mieux est préférable que l'inverse.

Par contre,

Citation:

Envoyé par jblecanard

Par exemple, std::set et std::unordered_set sont mauvais pour l'accès aléatoire (accès par l'indicie de l'élément, et par extension, accès par parcours de tous les éléments).

Qu'entends-tu par accès par parcours ?
Dans tous les cas, parcourir n'importe quelle collection par un itérateur de begin à end est (quasi) gratos. Et c'est le mieux à faire dans ce cas, pour pouvoir changer de collection sans modifier le parcours.
Les itérateurs sont très doués pour leur operator++

Citation:

Envoyé par jblecanard

Du coup, si ton algo a plus tendance à parcourir tes collections et que les insertions/fusions sont moins fréquentes que les lectures, il vaut peut-être mieux garder std::vector qui est imbattable sur l'accès aléatoire.

Idem, ça dépend de la façon de parcourir.
Si les parcours se font toujours du début à la fin, ou à partir d'un élément gardé en mémoire, et que les ajouts sont fréquents, la list est un excellent compromis. A la concession de l'accès aléatoire.

C'est l'esprit de ma réponse : ça dépend ;). Quand je parle de parcours, je parle bien d'un parcours du début à la fin avec les itérateurs.

Citation:

Envoyé par Bousk

Dans tous les cas, parcourir n'importe quelle collection par un itérateur de begin à end est (quasi) gratos.

Par contre, non, c'est pas gratos ! La preuve :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <list>
#include <unordered_set>
 
using namespace std;
using namespace chrono;
 
size_t get_ms(time_point<high_resolution_clock> const& start, time_point<high_resolution_clock> const& end) {
  return duration_cast<milliseconds>(end-start).count();
}
 
int main() {
  size_t constexpr size = 1e7;
  vector<int> c1;
  list<int> c2;
  set<int> c3;
  unordered_set<int> c4;
 
  c1.reserve(size);
  c4.reserve(size);
 
  for(int value = 0; value < size; ++value) {
    c1.push_back(value);
    c2.push_back(value);
    c3.insert(value);
    c4.insert(value);
  }
 
  int accumulator = 0;
  time_point<high_resolution_clock> t0 = chrono::high_resolution_clock::now();
 
  for(int v : c1) accumulator += v;
  time_point<high_resolution_clock> t1 = high_resolution_clock::now();
 
  accumulator = 0;
  for(int v : c2) accumulator += v;
  time_point<high_resolution_clock> t2 = high_resolution_clock::now();
 
  accumulator = 0;
  for(int v : c3) accumulator += v;
  time_point<high_resolution_clock> t3 = high_resolution_clock::now();
 
  accumulator = 0;
  for(int v : c4) accumulator += v;
  time_point<high_resolution_clock> t4 = high_resolution_clock::now();
 
  std::cout << "vector        : " << get_ms(t0,t1) << "ms" << std::endl;
  std::cout << "list          : " << get_ms(t1,t2) << "ms" << std::endl;
  std::cout << "set           : " << get_ms(t2,t3) << "ms" << std::endl;
  std::cout << "unordered_set : " << get_ms(t3,t4) << "ms" << std::endl;
}

Citation:

Envoyé par gcc en O2

vector : 0ms
list : 143ms
set : 359ms
unordered_set : 152ms

Citation:

Envoyé par clang en O2

vector : 0ms
list : 139ms
set : 320ms
unordered_set : 139ms

09/06/2014, 21h45
Ehonn

Parcourir des éléments, c'est parcourir de la mémoire. Si les données ne sont pas parcourues "dans le bon sens", on a des défauts de cache dans tous les sens et donc des performances moins bonnes.
09/06/2014, 22h11
Iradrille

Intéressant comme résultats, un unordered_set garde une list en interne pour traquer les objets stocker ?
10/06/2014, 00h29
Bousk

Citation:

Envoyé par jblecanard

Par contre, non, c'est pas gratos ! La preuve :

Désolé de te dire que ton test est à côté du sens de ma phrase.
Bien sur que non c'est jamais gratos... la moindre opération a un cout :weird:, parfois minime.
Mais dans ton post tu ne cesses de parler d'accès aléatoire, alors qu'un accès séquentiel à une collection doit se faire avec un itérateur qui s'incrémente.
Et, oui, l'opérateur++ sur un itérateur est gratos, il est en temps constant.

Citation:

draft C++11 standard N3337 the answer can be found in § 24.2.1 paragraph 8

Citation:

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).

La seule chose que montre ton test c'est que oui vector est un tableau de mémoire contigue alors il ne souffre d'aucun cache-miss etc..
10/06/2014, 01h21
Iradrille

Citation:

Envoyé par Bousk

Mais dans ton post tu ne cesses de parler d'accès aléatoire, alors qu'un accès séquentiel à une collection doit se faire avec un itérateur qui s'incrémente.
Et, oui, l'opérateur++ sur un itérateur est gratos, il est en temps constant.

Temps constant != gratuit. ;)
Un opération en O(1) peut être "rapide" (std::vector) ou "lente" (std::set).

Mais on joue sur les mots plus qu'autre chose, au final on dit tous la même chose.
10/06/2014, 08h31
JolyLoic

Citation:

Envoyé par Bousk

Et, oui, l'opérateur++ sur un itérateur est gratos, il est en temps constant.

http://stackoverflow.com/questions/1...-stdset-stdmap

Pas vraiment : C'est en temps constant amorti. Ça signifie en particulier sur un set qu'un it++ n'est pas en O(1) (le cas où on est tout en bas d'une branche de l'arbre, et qu'on doit remonter tout en haut de l'autre branche), mais qu'itérer du début à la fin de la collection est en O(N) (ce qui ne doit pas être trivial à démontrer).

Mais en effet, pour ce genre d'opérations rapides que l'on fait souvent, les facteurs constants négligés par l'étude de la complexité peuvent avoir leur importance !
10/06/2014, 09h56
jblecanard

Citation:

Envoyé par Bousk

La seule chose que montre ton test c'est que oui vector est un tableau de mémoire contigue alors il ne souffre d'aucun cache-miss etc..

Ca tombe bien, c'est précisément ce que je voulais montrer :aie:. Je parcours bien du début à la fin avec un itérateur, et on voit que le coût diffère selon la collection utilisée. On est d'accord tous les deux là dessus n'est ce pas ? La complexité en temps constant amorti ne donne aucune info sur la performance réalisée en situation. D'ailleurs la liste est rarement un bon compromis, voir la conf de Bjarne à ce sujet.

https://www.youtube.com/watch?v=YQs6...?v=YQs6IC-vgmo

Désolé, j'arrive pas à mettre le lien vers la vidéo sans que le BBCode du forum ne l'interprète en "embedded", si un modo peut arranger ça, merci d'avance.

Citation:

Envoyé par Iradrille

Intéressant comme résultats, un unordered_set garde une list en interne pour traquer les objets stocker ?

Ceci est un effet de bord du fait que l'on stocke des entiers, triés de surcroît. Si on stocke des chaînes de caractères, unordered_set fait tout de suite beaucoup moins le malin :mrgreen:.

Le code.

Citation:

Envoyé par gcc en O2

generation took : 66459ms
list size : 9999973
unordered_set size : 9999973
list : 467ms
unordered_set : 1183ms
set : 1599ms

Citation:

Envoyé par clang en OZ

generation took : 61362ms
list size : 9999962
unordered_set size : 9999962
list : 467ms
unordered_set : 1177ms
set : 1656ms
10/06/2014, 10h41
StingerBell

Merci a tous pour vos reponses :),

quelques questions encore :

Citation:

Pour ton premier problème, tu peux envisager plusieurs méthodes :
- Utilisation de std::set => Eléments uniques triés
- Utilisation de std::unordered_set => Eléments uniques non triés (plus adapté aux pointeurs)
- Utilisation de std::vector/list + std::unique + std::remove => Solution par défaut, qui marche mais pas la plus adaptée.

Pour ton cas je partirais sur un std::unordered_set.

Le fait que mon vecteur soit un vecteur de pointeur ne rends pas impossible cette methode ? Ce que je veux dire, c'est que j'ai l'impression qu'avec ca, le programme ne va pas supprimer deux pointeur differents qui pointent vers le meme objet non ? La solution qui a ete propose d'utiliser un std::vecteur et de l'encapsuler dans une autre class qui gererait les ajout / suppression / concatenation reglereait ce probleme ? Il va donc falloir coder a la main les differentes methodes pour l'ajout et la suppression de doublons ?

Citation:

En effet, en utilisant shared_ptr::reset() et weak_ptr, tu peux obtenir cette fonctionnalité. Mais j'attire ton attention sur plusieurs choses:
- shared_ptr est coûteux, car il est fait pour que l'accès concurrent à un objet via plusieurs threads (et un shared_ptr par thread, ou plus) soit safe. De fait, si tu n'as qu'un thread, tu vas payer pour quelque chose que tu n'utilises pas.
- Cette technique impose de stocker au moins un shared_ptr quelque part et des weak_ptr ailleurs. Peut-être que ton algo n'est pas pensé comme ça et va mal s'adapter à cet état de fait.
- Si tu invalides une série que weak_ptr en détruisant le shared_ptr "maître", les weak_ptr restants seront toujours dans les collections (vector ou autre, selon le choix fait dans la première partie). Ca peut être intéressant si tu fais un nettoyage "différé", c'est à dire
si tu profites d'un parcours de la collection qui a un autre but pour trouver les références invalides et les nettoyer, ok. Mais peut-être que tu voudras nettoyer les collections des pointeurs invalides dès la destruction effectuée, dans lequel cas, shared_ptr ne te rendra pas un bien grand service.

ok donc si j'ai bien compris il faudrait que pour chaque objet, je cre a la fois un shared_ptr et des weak_ptr. Lorsque je veux detruire l'objet je devrai detruire le shared_ptr et alors tous les weak_ptr seront alors invalide. Et une fois qu'ils sont invalide il va falloir que je parcours la liste pour les "nettoyer" ?

Je crois que je comprends le principe mais je ne vois pas vraiment comment cela m'aide. Dans le sens que je pourrai faire la meme chose avec des pointeurs normaux nan ? Je pointe plusieurs pointeurs sur le meme objet, je detruit l'objet puis apres je parcours la liste pour detruire tous les pointeurs qui ne pointent plus sur rien ? Dans l'ideal en fait je voudrai pouvoir eviter d'avoir a reparcourir le vecteur pour detruire tous les pointeurs "morts" et que cela soit fait automatiquement ?

Merci beaucoup pour votre aide !
10/06/2014, 11h05
jblecanard

Tu as bien compris.

Tu peux utiliser un std::unordered_set sur des pointeurs, cela fonctionnera, un pointeur n'étant qu'un nombre entier au final. Il faut juste être conscient des compromis : moins bonnes perfs en parcours itératif, perte de l'ordre d'insertion. Mais comme l'on dit : early optimisation is the root of all evil. Je pense que tu peux suivre le conseil de Bousk et partir sur un unordered_set, et si les performances deviennent un problème pour toi, le flat_set de boost te fournira une alternative intéressante, en changeant très peu ton code.

Avec ce choix, tu devras quand même supprimer de chaque collection le pointeur vers l'objet supprimé, mais tu n'as pas besoin de la parcourir pour ce faire. Une solution "complètement automatique" qui mettrait à jour les collections à la suppression sans que tu ne fasses rien et sans y laisser des pointeurs invalides risque d'être un peu casse-gueule niveau design.
10/06/2014, 14h36
StingerBell
Une question concernant std::unordered_set car j'ai quelques difficultes et j'ai du mal a trouver des examples sur cette classe sur internet :

le code suivant ne compile pas :
Code:

1 2 3 4 std::unordered_set<Objet*> a; std::unordered_set<Objet*> b; a.insert(a.end(),b.begin(),b.end())
il ne trouve pas la fonction insert, alors qu'il n'y avait pas de probleme avec des vecteurs normaux.

Merci

Salut

Il faut lire la doc :)

Code:

1
2
3
std::unordered_set<Object*> a, b;
using std::begin;
b.insert(begin(a), end(a));