std::vector et références

Version imprimable

09/12/2013, 11h22
fma38

std::vector et références

Bonjour,

J'essaye d'optimiser un programme C++ embarqué (Arduino).

Dans ce programme, je crée des objets que je range dans un vector. Je voudrais pouvoir les récupérer dans un autre ordre. Pour éviter de créer des copies, j'essaye d'utiliser les références, mais ça ne passe pas à la compile : j'ai l'impression qu'il est impossible de déclarer un vector de références... Me goure-je ?

Merci de vos lumières.

PS : je voudrais éviter les pointeurs autant que possible...
09/12/2013, 11h24
Bousk

Un tableau de références est impossible
Pour éviter les copies, de simples objets suffisent
Ce n'est pas les objets qui passent en références, mais le tableau lui-même
09/12/2013, 12h27
fma38

Pas sûr de comprendre... Peux-tu me dire comment tu fais sur un petit exemple ?
09/12/2013, 13h33
oodini

Si tu es en C++11, remplis ton vecteur avec la méthode emplace_back(), et quand tu veux exploiter les valeurs, extrait les vers des références constantes.
09/12/2013, 14h49
fma38

Non, pas de chance, pas de C++1 :(

La question est : si je fais :

Code:

vect2.push_back(vect1[i])

est-ce que je crée une copie de l'objet vect1[i] que j'ajoute ensuite à vect2, ou est-ce que c'est le même objet qui est inséré ?
09/12/2013, 15h06
JolyLoic

push_back crée une copie (ou un déplacement en C++11 si l'objet est temporaire).
09/12/2013, 16h00
koala01

Salut,

Citation:

Envoyé par fma38

Non, pas de chance, pas de C++1 :(

La question est : si je fais :

vect2.push_back(vect1[i])

est-ce que je crée une copie de l'objet vect1[i] que j'ajoute ensuite à vect2, ou est-ce que c'est le même objet qui est inséré ?

Non, ce sera d'office une copie.

l'opérateur [] renvoie une référence (éventuellement constante) sur l'objet qui est situé à l'indice indiqué entre les crochets, et une référence ne peut -- comme tu l'as si bien fait remarquer -- pas prendre place dans une collection.

La raison est simple : une référence n'est qu'un alias de l'objet référencé. Elle n'a donc pas d'existence réelle bien à elle (elle n'existe qu'au travers de l'objet référencé).

il y a donc, forcément, copie lorsque tu utilises le résultat de l'opérateur [] pour remplir un autre tableau.
09/12/2013, 16h10
white_tentacle

Si c’est pour les récupérer dans un autre ordre, une solution est d’avoir un vecteur de pointeurs qui sert d’index.

Attention toutefois à ce que ton vecteur initial ne change pas : sinon, ton index est invalidé et tu dois le reconstruire.
09/12/2013, 16h17
fma38

Ok, merci pour vos réponses.

En fait, je crois que je vais même aller plus loin, et faire ça plus propre, avec un itérateur spécialisé. C'est possible, non ? Il en faudrait plusieurs, en fait (différents ordres)...
09/12/2013, 17h42
oodini

Si tu voulais éviter la complexité des pointeurs, ne va pas te lancer dans la complexité d'implémentation d'un itérateur...
09/12/2013, 19h29
fma38

Euh, ce n'est pas la complexité qui me fait tenir loin des pointeurs ; c'est parce que c'est casse-gueule au possible.

Implémenter un itérateur, c'est quand même plus propre. Au moins, j'apprendrai quelque chose. Alors qu'avec les pointeurs, à part m'arracher les cheveux à trouver ce qui merde...

Personne n'a parlé de std::reference_wrapper (C++11) ou boost::reference_wrapper ?

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
struct data {
	int i;
	data(int i): i(i) { }
	data(const data& d) {
		assert(0);
	}
};
 
int main() {
 
	typedef std::vector<std::reference_wrapper<data>> vec_type;
 
	vec_type vec, vec2; 
 
	data d(0);
	vec.push_back(d);
	vec2.push_back(vec[0]);
 
	d.i = 1;
	assert(d.i == 1);
	assert(d.i == vec[0].get().i);
	assert(d.i == vec2[0].get().i);
 
	return 0;
}

10/12/2013, 07h54
fma38

Ça avait l'air bien, mais ce n'est malheureusement pas dispo dans l'implémentation de la libstdc++ que j'utilise sur Arduino...

Merci quand même !

Bon, côté iterateurs, c'est vrai que c'est un peu pédestre ! J'ai bêtement imaginé que ça pouvait se faire aussi simplement qu'en python :roll:

Tant pis, je vais y aller à coup de pointeurs. Tout en finesse !
10/12/2013, 09h40
Bousk

Un moyen simple d'éviter une copie c'est de commencer par le push_back (ou insert) puis de l'initialiser (les initialiser) avec back ou []
10/12/2013, 10h15
fma38

Initialiser l'objet qu'on vient de mettre dans le vector ? Mais comment le créer sans l'initialiser ? Un truc m'échappe...
10/12/2013, 10h48
white_tentacle

Un vector a forcément besoin de créer des objets (avec le constructeur par défaut) avant de pouvoir y stocker de véritables objets.

En fait, la bonne question, c’est :
- la copie de tes objets est-elle réellement coûteuse (s’ils font moins de 20 octets, ça se discute très sérieusement)
- es-tu bien sûr que c’est de vector que vient ton éventuel problème de perf.

En tout cas, je maintiens ce que j’ai dit initialement : s’il s’agit juste de présenter une collection de gros objets sous différents ordres, j’adopterai la structure suivante :
- un std::list<T> container, qui stocke les objets. Comme tu vas devoir reconstruire tes index à chaque modification, la std::list est probablement plus adaptée que le vector. Si ta collection ne change jamais, ça se discute plus.
- pour chaque « ordre », un std::vector<std::list<T>::iterator> qui donne accès aux éléments de ta liste dans l’ordre voulu.

Bien sûr, pour les classes clientes, pas d’accès direct à la liste initiale afin de s’assurer que les index restent en phase à chaque suppression / insertion.

L’autre solution, si jamais tu peux l’utiliser, est qu’il y a une multi_ordered_map (ou quelque chose de similaire) dans boost, si mes souvenirs sont bons.
10/12/2013, 11h13
fma38

Citation:

Envoyé par white_tentacle

Un vector a forcément besoin de créer des objets (avec le constructeur par défaut) avant de pouvoir y stocker de véritables objets.

Pigé.

Citation:

En fait, la bonne question, c’est :
- la copie de tes objets est-elle réellement coûteuse (s’ils font moins de 20 octets, ça se discute très sérieusement)
- es-tu bien sûr que c’est de vector que vient ton éventuel problème de perf.

Je suis en embarqué, avec 2ko de RAM ! 20 octets par objet, ça rempli vite le bastringue. Et oui, mon souci vient bien du fait que si je duplique le contenu du vector, je crash le bignou, faut de RAM (avec un quick hack pointeurs, il me reste 500 octet de libre).

Citation:

En tout cas, je maintiens ce que j’ai dit initialement : s’il s’agit juste de présenter une collection de gros objets sous différents ordres, j’adopterai la structure suivante :
- un std::list<T> container, qui stocke les objets. Comme tu vas devoir reconstruire tes index à chaque modification, la std::list est probablement plus adaptée que le vector. Si ta collection ne change jamais, ça se discute plus.
- pour chaque « ordre », un std::vector<std::list<T>::iterator> qui donne accès aux éléments de ta liste dans l’ordre voulu.

Ma collection ne change pas, donc le vector est moins gourmand, non ?

Je vais plancher sur cette solution, même si je ne vois pas encore bien comment implémenter ça... Comment utilises-tu un vector d'iterator ?

Citation:

Bien sûr, pour les classes clientes, pas d’accès direct à la liste initiale afin de s’assurer que les index restent en phase à chaque suppression / insertion.

Oeuf corse...

Citation:

L’autre solution, si jamais tu peux l’utiliser, est qu’il y a une multi_ordered_map (ou quelque chose de similaire) dans boost, si mes souvenirs sont bons.

Si le code n'est pas trop gros, je peux essayer d'intégrer cette partie à mon code (paraît que boost est très modulaire), mais je n'ai pas boost sur l'Arduino ;)

Merci !
10/12/2013, 11h21
oodini

Citation:

Envoyé par fma38

Ça avait l'air bien, mais ce n'est malheureusement pas dispo dans l'implémentation de la libstdc++ que j'utilise sur Arduino...

Dispo dans TR1, ou au pire dans Boost.
10/12/2013, 12h57
Bousk

Citation:

Envoyé par fma38

Initialiser l'objet qu'on vient de mettre dans le vector ? Mais comment le créer sans l'initialiser ? Un truc m'échappe...

Tout simplement en insérant des objets par défaut, avec le constructeur par défaut avant de les initialiser pour de bon, et non d'y copier des objets déjà initialisés
10/12/2013, 13h06
fma38

Ok, mais j'aurai bien 2 objets différents, un dans chaque vector, non ? Au final, ça prendra la même place en mémoire ?

Je veux bien un bout de code d'exemple, car là, je suis largué :cry:
10/12/2013, 13h12
JolyLoic

Citation:

Envoyé par white_tentacle

Un vector a forcément besoin de créer des objets (avec le constructeur par défaut) avant de pouvoir y stocker de véritables objets.

Je ne vois vraiment pas ce que tu veux dire par là... Un vector n'a aucunement besoin d'un constructeur par défaut (j'ai juste eu le soucis avec un vieux compilo qui en réclamait un, mais il était en tort). Il a besoin d'allouer de la mémoire non initialisée, avant d'y copier/déplacer des objets, mais ça n'a rien à voir avec la création d'objets vides.

Citation:

Envoyé par white_tentacle

En fait, la bonne question, c’est :
- la copie de tes objets est-elle réellement coûteuse (s’ils font moins de 20 octets, ça se discute très sérieusement)
- es-tu bien sûr que c’est de vector que vient ton éventuel problème de perf.

En tout cas, je maintiens ce que j’ai dit initialement : s’il s’agit juste de présenter une collection de gros objets sous différents ordres, j’adopterai la structure suivante :
- un std::list<T> container, qui stocke les objets. Comme tu vas devoir reconstruire tes index à chaque modification, la std::list est probablement plus adaptée que le vector. Si ta collection ne change jamais, ça se discute plus.

Si les perfs comptent vraiment, la list, qui n'est pas cache-friendly n'est peut-être pas une super idée. En plus, ça prend pas mal de mémoire. Le deque a aussi une certaine stabilité, mais dès que les objets font quelques octets, ils se transforment généralement en tableau de pointeurs, et donc fragmentent aussi la mémoire.

Citation:

Envoyé par white_tentacle

L’autre solution, si jamais tu peux l’utiliser, est qu’il y a une multi_ordered_map (ou quelque chose de similaire) dans boost, si mes souvenirs sont bons.

boost::multi_index, ou son wrapper simplifié boost::bimap. Mais je doute que ça marche bien sur le sous ensemble du C++ qu'a l'air d'être Arduino...
10/12/2013, 14h01
Davidbrcz
Citation:

Envoyé par fma38

Non, pas de chance, pas de C++1 :(

C'est faux.

Tu compiles pour arduino avec avr-g++, qui juste un compilateur g++ classique mais qui produit du code pour ... ARM

Il y a cependant quelques restrictions : IIRC pas de RTTI ni d'exceptions

Il suffit d'activer le flag pour utiliser C++11 (sans la STL) sans soucis.
Pour la STL, ya des portages, mais plus des portages de la STL de C++03.

Apres, ya des soucis lies au fait qu'on soit sur un microcontroleur.
On est vite limité en RAM, avr-g++ place les vtable en Flash ET en RAM,...

Pour info, jai passé un an a code sur une Arduino mega avec Emacs, Makefile & C++11 et j'ai pu utiliser des varuadic templates , du tag-dispatch et des std::vector

Sinon tu peux détailler ?
- ta carte: Uno/Mega/Due/...
- Ton problème exact avec un peu de code
- Tes contraintes: performance ou occupation de ram ?
Car un vecteur de unique_ptr que tu tries au besoin, ca peut s'envisager.
10/12/2013, 14h20
fma38

Aïe, pas taper !! Chuis développeur python, moi ;)

Je vais voir pour activer ces fameux flags...
10/12/2013, 14h29
fma38
Citation:
Envoyé par Davidbrcz

Sinon tu peux détailler ?

ta carte: Uno/Mega/Due/...
Ton problème exact avec un peu de code
Tes contraintes: performance ou occupation de ram ?

Car un vecteur de unique_ptr que tu tries au besoin, ca peut s'envisager.
Le projet est celui-ci :

https://www.logre.eu/wiki/JIXClock

Je suis en train de refaire le firmware du copain mais plus orienté objet. La cible est un Nano.

Côté perfs, je n'ai pas trop de souci : il s'agit de rafraichir les leds pour que visuellement ça rende bien ; 20ms est largement suffisant pour faire déjà des effets de transitions de couleurs sympas.

Par contre, côté mémoire, c'est vite plein !

En gros, j'ai un objet DisplayData, qui contient des DigitData, lesquels contiennent des LedData. L'objet DisplayData est mis à jour par le modèle, et utilisé par la vue pour rafraichir l'horloge (ou sortir sur la console quand je n'ai pas le hard complet sous la main, mais juste un petit Arduino).

Ce que je veux, c'est, dans DisplayData et DigitData, avoir des itérateurs qui me retournent des références sur les LedData, dans un ordre spécifique. Histoire de pouvoir facilement récupérer les LedData par colonne, par ligne, ou tout autre tri qui passera par la tête d'un designer fou ;)

L'idée est d'avoir une structure facile à utiliser pour ajouter des modes de couleurs, de patterns, etc.

Je vais pusher le code sur github d'ici peu, histoire que vous puissiez voir le code... À condition de me promettre de ne pas rire !
10/12/2013, 15h26
fma38

Voili :

https://github.com/fma38/JIXoo
10/12/2013, 15h55
white_tentacle
En gros, tu remplaces
Code:

1 2 T::T(int param1, std::string const& param2, int* param3)
par :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 T::T() : membre1(0), membre2(), membre3(NULL) { } void T::init(int param1, std::string const& param2, int* param3) { membre1 = param1; … }
et ensuite, tu fais au niveau de ton vecteur :
Code:

1 2 3 v.resize(v.size() +1); v.back().init(param1, param2, param3);
Ça t’évite de construire un objet localement.

Si tu connais à l’avance la taille de ton vecteur (ou un majorant raisonnable de celle-ci), tu as clairement intérêt à l’allouer au départ avec v.reserve() --> ton vecteur fera alors normalement exactement la bonne taille, sans « gâchis » de mémoire, alors que par allocations successives, il y a de bonnes chances qu’il alloue trop.
10/12/2013, 16h00
white_tentacle

Citation:

Envoyé par JolyLoic

Je ne vois vraiment pas ce que tu veux dire par là... Un vector n'a aucunement besoin d'un constructeur par défaut (j'ai juste eu le soucis avec un vieux compilo qui en réclamait un, mais il était en tort).

Effectivement, c’est nécessaire seulement si on utilise resize(). Merci pour la correction :ccool:
11/12/2013, 11h51
Arzar

Citation:

Envoyé par fma38

Pigé.

Je suis en embarqué, avec 2ko de RAM ! 20 octets par objet, ça rempli vite le bastringue. Et oui, mon souci vient bien du fait que si je duplique le contenu du vector, je crash le bignou, faut de RAM (avec un quick hack pointeurs, il me reste 500 octet de libre).

Si tu n'as vraiment que 2ko de ram tu peux probablement laisser tomber toutes les réponses qu'on t'as faite dans ce thread... :aie: Avec des contraintes aussi fortes, toute solution générale qu'on pourra te donner sera très probablement inappropriée.

Déjà rien que le fait d'utiliser std::vector me semble très surprenant. std::vector alloue avec new dans le tas, et possède son propre pattern d'allocation (il alloue souvent plus que nécessaire pour éviter d'avoir à réallouer lors d'ajout d'élément), donc est-ce que c'est vraiment sage d'utiliser un vector alors que la mémoire est aussi ric-rac ?

En plus tu dis qu'allouer un peu trop fait carrément crasher la machine ! J'ai tendance à penser qu'il faudrait que tu puisses gérer précisément le budget mémoire, par exemple en préallouant un tableau statique de taille fixe égale au nombre maximum d'objet autorisé et qui contiendra tes objets.

D'ailleurs avec aussi peu de mémoire ça veut dire que ton tableau ne contiendra que très peu d'objet au final, en fait vu qu'ils font chacun 20 octets et que tu n'as que 2k ça veut dire que ton nombre total d'objet ne dépassera jamais (2k)/20 = 102. Donc pour le tri le moins coûteux en mémoire serait probablement d'avoir un deuxième tableau de char (char == codé sur un seul octet) de la même taille que ton tableau principal. Chaque case contient alors un numéro (entre 1 et 255 vu que c'est un char) qui est en fait un index vers ton tableau principal. Avec cette technique cela veut dire qu'avec 102 octets maximum tu peux encoder un tri de ton tableau principal.
11/12/2013, 12h22
fma38

Yep, le tableau de uint8_t (qui est un bête alias sur unsigned char), c'est ce que j'ai finalement fait pour le moment, en attendant de trouver mieux.

J'aurais bien utilisé array, mais pas dispo (faut faire tout un tas de galipettes pour utiliser un compilo plus récent dans l'IDE Arduino, et comme je veux que ça se compile facilement par un non spécialiste...).

Par contre, j'alloue mes vector avec reserve(), comme indiqué. Et je monitor la mémoire lors des devs.
11/12/2013, 13h59
Arzar

vector::reserve() c'est typiquement le genre de fonction que le standard autorise à faire allouer plus que la taille passée en paramètre, mais heureusement il me semble qu'en pratique toutes les implémentations connues alloue pile la taille demandée. :mrgreen:

Ça m'épate toujours un peu qu'avec à peine 2ko de ram les std::vector soient disponibles (et donc les malloc/new le soient aussi)