Discussion :

[gelam]

Bonjour,
Je suis en train de faire quelques essais avec la STL. J'utilise VC6 et je constate qqch de bizarre...
Lorsque je compile le code suivant tout se passe bien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int main(){
  int tab[]={11,22,33,44,55} ;
  vector<int> conteneur(tab,tab+5) ;
}

alors qu'avec ce code j'ai une erreur de compilation

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int main(){
  int tab[]={11,22,33,44,55} ;
  deque<int> conteneur(tab,tab+5) ;
}

Dans la doc vector et deque offrent tous deux un constructeur paramétré avec deux itérateurs.
Que se passe-t-il ?
J'ai de la peine à croire qu'il y ait un bug dans la STL ???

Merci d'avance pour vos réponses

[Aurelien.Regat-Barrel]

J'ai de la peine à croire qu'il y ait un bug dans la STL ???

et pourtant...
http://c.developpez.com/faq/cpp/?pag...LEMES_stl_vcpp
tu as installé le dernier Service Pack ?
Le mieux est de passer à VC++ 7.1

[Jan Rendek]

un itérateur n'est pas un pointeur.

Il se trouve que dans le cas des vecteurs, les itérateurs sont en général par des pointeurs, ce qui n'est pas une obligation. Ce qui explique que ton premier appel soit accepté par le compilateur. Les paramêtres tab, et (tab + 5) sont implicitement convertis en itérateur sur un vecteur d'entier. Et le constructeur prenant en paramètre un intervalle défini par 2 itérateurs est correctement appelé.

En revanche, les itérateurs sur un deque ne sont jamais directement implanté par un simple pointeur, ce qui fait que l'appel échoue.

En conclusion, si le premier appel compile, c'est uniquement *par hasard*.

Pour initialiser un vecteur à partir d'un tableau, on s'y prend généralement de la manière suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main()
{
  int tab={11,22,33,44,55};
  vector<int> conteneur;
  conteneur.resize(5);
  memcpy(&conteneur[0], tab, 5*sizeof(int));
}

Pour initialiser un deque a partir d'un tableau, soit on insere les éléments un à un. Soit on charge le tableau dans un vecteur et on utilise l'algorithme copy() (spécial fainéant).

[jmv]

un itérateur n'est pas un pointeur.

Non mais un pointeur est un itérateur (ou peut s'utiliser comme tel)
Chez moi le code suivant passe trés bien avec DEV-C++

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main()
{
    int tab[] = { 1,2,3,4,5,6 };
    vector<int> ve(tab, tab+6);
    deque<int> de(tab, tab+6);
    list<int> li(tab, tab+6);
}

En conclusion, si le premier appel compile, c'est uniquement *par hasard*.

Non, c'est dans le cahier des charges de la STL, un pointeur doit pouvoir être utilisé comme itérateur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main()
{
  int tab={11,22,33,44,55};
  vector<int> conteneur;
  conteneur.resize(5);
  memcpy(&conteneur[0], tab, 5*sizeof(int));
}

ça c'est de la bidouille !!!
[EDIT]
c'est pas de la bidouille, ça marche, voir post suivant
[/EDIT]

Excuse moi VoidSeer mais tu ne doit pas être très bien réveillé

[Laurent Gomila]

Je confirme... Le constructeur prenant en paramètre 2 itérateurs est bien là (sauf sous VC6), et au pire il y a toujours assign ou copy avant d'en arriver là

[Luc Hermitte]

Un pointeur est même un itérateur à accès direct ("random access iterator"), et par conséquent un "input itérator". Il est donc parfaitement valide en paramètre de std::deque.
L'erreur est ici dans une vieille STL qui allait avec un vieux compilo.

[Jan Rendek]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main()
{
  int tab={11,22,33,44,55};
  vector<int> conteneur;
  conteneur.resize(5);
  memcpy(&conteneur[0], tab, 5*sizeof(int));
}

ça c'est de la bidouille !!!

Nan, c'est directement l'application de l'item 16 de "Effective STL", S. Meyer - Addison-Wesley.

Quant au reste, mea culpa, j'ignorais qu'un pointeur simple était un itérateur valide sur un deque.
Au deuxième coup d'oeil, ça paraît logique, vu l'interface requise pour un random access iterator. Effectivement, je ne devais pas être bien frais

[Aurelien.Regat-Barrel]

Y compris le memcpy ?
On préfèrera std::copy() en C++.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
std::copy( conteneur.begin(), conteneur.end(), tab );

[jmv]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main()
{
  int tab={11,22,33,44,55};
  vector<int> conteneur;
  conteneur.resize(5);
  memcpy(&conteneur[0], tab, 5*sizeof(int));
}

ça c'est de la bidouille !!!

Nan, c'est directement l'application de l'item 16 de "Effective STL", S. Meyer - Addison-Wesley.

le pb est que tu suppose que les éléments d'un vecteur sont contigus, c'est vrai dans 99,99% des implémentations de la STL (peut-être même 100%) mais ça n'est pas garanti par la norme.

[Jan Rendek]

Le memcpy est parfaitement licite, et pas bidouille car le standard impose que les vecteurs stockent leurs éléments de la même manière qu'un tableau.

EDIT: @jmv, c'est garanti par la norme

[jmv]

EDIT: @jmv, c'est garanti par la norme

ha... tu as peut-être raison mais alors Delannoy et Stroustrup se sont trompé dans leur bouquin.

Je croyais que seul l'accés aléatoire en O(1) était garanti.

[Jan Rendek]

Non, le stockage des données mémoire de manière contigüe est imposé. Bien sûr, ça n'a que peu d'importance sur un tableau à 5 éléments, mais le fait d'utiliser un 'memcpy' à la place d'un algorithme STL m'a fait gagner pas mal de temps dans des parties de code critiques.

[Luc Hermitte]

- La contiguité des éléments d'un vecteur est garantie par la norme.
Que le Delannoy se trompe ne m'étonne pas plus que ça (il fait parti de ces bouquins recommandés qui n'ont pas très bonne réputation chez les initiés), qu'il y ait une erreur dans le bouquin de Stroustrup c'est autre chose. Quelle version ? La dernière traduction révisée (techniquement) par Michel Michaud ? Une autre ? Que disent les errata associés à ta version ?

- Aurélien, tu a été étourdi , le memcpy (&vecteur[0], tab, size_tab) se traduit en std::copy(tab, tab+size_tab, &vecteur[0]);

- Le surcout de std::copy par rapport à memcpy est au pire une légende, et normalement un problème résolu avec les implémentations d'aujourd'hui de la STL avec les compilos qui savent inliner. Perso je garde memcpy que lorsque j'ai des tailles (et non des plages) et des données POD (très important le POD, memcpy n'est pas utilisable sinon). Typiquement en sortie de socket.

Et perso, j'aime assez écrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
std::copy(ll::begin(tab), ll::end(tab), std::back_inserter(vecteur));
// voire directement
ll::copy(tab, std::back_inserter(vecteur));

Les facilités qui permettent d'écrire ce genre de choses sont assez courantes et vite intégrées dans un projet.


Sinon, il y a un projet de boost qui permet d'initialiser des containers de façon "simple" sans passer par la case tableau statique.

[Aurelien.Regat-Barrel]

Pour std::copy, apparement je me suis mal exprimé. J'ai pas voulu dire que le memcpy était faux, juste que c'est plus C que C++, et que std::copy me parraît plus naturel avec un vector ou autre conteneur STL.
C'est quoi POD ?

[Luc Hermitte]

Sinon POD, c'est "plain old data". Cela correspond aux types composés à partir des types primitifs. En sont exclues de sûr les classes. J'ai un doute quant à savoir si on peut y mettre des fonctions membres simples.

[jmv]

Dans "le langage C++" de Stoustrup, édition spéciale revue et corrigée (c)2003, page 518 chapitre 17.1.3

La représentation:
Le standard n'impose pas de représentation particulière pour chaque conteneur. Il en spécifie simplement les interfaces et quelques conditions de complexité...
Pour un vector, la structure de donnée sera très certainement un tableau.

pour moi, "très certainement" ne veut pas dire "obligatoirement". Donc méfiance avec memcpy(). Par contre std::copy() fonctionne même si les éléments ne sont pas contigus à condition d'utiliser des vrais itérateurs (pas des pointeurs, qui sont des itérateurs de tableau).

Bon, maintenant, c'est vrai que "standard" != "norme". Où peut-on trouver cette norme ?

[Luc Hermitte]

La norme ISOIEC14882-1998 s'achète -- il doit y avoir des liens dans la FAQ, au pire ça y est dans la FAQ C++ lite.

Mais ce point particulier se trouvera dans la révision (acceptée, il va de soi) de celle ci dont le PDF est disponible librement sur le site de Bjarne Stroustrup.

[...]The elements of a vector are stored contiguously, meaning that if v is a vector<T,Allocator> where T is some type other than bool, then it obeys the identity: &v[n] == &v[0] + n for all 0 <= n < v.size().

Les implémenteurs sont libres de mettre en oeuvre les vecteurs comme ils le désirent, mais il est clair que cette contrainte forte rend impossible l'utilisation d'autre chose que d'un tableau pour stocker les éléments en interne.

(standard <~> norme ; la norme est le papier qui définit le C++ standard, je crois)

En conclusion, on peut utiliser memcpy comme std::copy sur les vecteurs -- au détail que memcpy n'est utilisable que pour les types POD, qu'il marche directement pour extraire des données des vecteurs, et qu'il nécessite un redimensionnement (resize != reserve) du vecteur avant écriture -- std::copy permet d'utiliser les back_inserter.

[jmv]

merci pour ces précisions
et mille excuses à VoidSeer: son code fonctionne et n'a rien de bidouille puisqu'il respecte la norme.

[gelam]

Un grand merci à tous. Je ne pensais pas lancer un discussion aussi passionée.
Concernant la discussion itérateur-pointeur : Mon point de vue est qu'un pointeur n'est pas un itérateur et un itérateur n'est pas un pointeur mais qu'ils partagent la même interface si le conteur fournit un random iterator.
Tous deux fournissent les opérateurs suivants :
r++ r--
r+=n r-=n
s=r+n
s=r-n
n=r-s
r<s, r<=s, r>s, r>=s
où r et s sont des itérateurs et n un entier
( tout ceci en plus de r==s, r!=s, *r )

bon WE à tous

[Luc Hermitte]

Un pointeur est une des formes d'itérateur. SGI le dit, et je pense que le commité de standardisation a gardé ce fait.
Et tous les itérateurs ne sont pas des itérateurs à accès direct (random access iterators) dont tu as donné une partie de la sémantique (http://www.sgi.com/tech/stl/RandomAccessIterator.html)