insertion d'élements dans un vector

Version imprimable

Bonjour,

Je souhaite insérer des élements après un iterateur "k" (dans mon code ci-dessous)
cependant lorsque j'excécute mon programme cela segfault.

J'ai une map (pour l'exemple) : map<truc *, vector<truc *> > test;
quand un des élements de chacun des "vectors" contient chose_un
le code est sensé insérer plusieur valeurs.

voici le code de test :

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
 
class truc
{
        public :
 
        int a;
        int b;
};
 
using namespace std;
 
int main(void)
{
        truc *chose_un = new truc();
        truc *chose_deux = new truc();
        truc *chose_trois = new truc();
 
        map<truc *, vector<truc *> > test;
 
        test[chose_un].push_back(chose_un);
        test[chose_un].push_back(chose_trois);
 
        test[chose_deux].push_back(chose_un);
        test[chose_deux].push_back(chose_deux);
        test[chose_deux].push_back(chose_un);
 
        test[chose_trois].push_back(chose_trois);
        test[chose_trois].push_back(chose_trois);
 
        std::cout << "chose_un : " << chose_un << std::endl;
        std::cout << "chose_deux : " << chose_deux << std::endl;
        std::cout << "chose_trois : " << chose_trois << std::endl;
 
        for(map<truc *, vector<truc *> >::iterator it = test.begin() ; it != test.end() ; it ++)
        {
                for(vector<truc *>::iterator k = it->second.begin() ; k != it->second.end() ; k++)
                {
                        if(*k == chose_un)
                        {
                                test[chose_un].insert(k, test[chose_deux].begin(), test[chose_deux].end());
                        }
                }
        }
 
return 0;
 
}

Voici ce que j'obtiens en sortie dans mon gdb :

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
 
Program received signal SIGSEGV, Segmentation fault.
__memmove_ia32 () at ../sysdeps/i386/i686/multiarch/../memmove.S:111
111	../sysdeps/i386/i686/multiarch/../memmove.S: No such file or directory.
	in ../sysdeps/i386/i686/multiarch/../memmove.S
(gdb) b
Breakpoint 1 at 0x2dd91d: file ../sysdeps/i386/i686/multiarch/../memmove.S, line 111.
(gdb) back 
#0  __memmove_ia32 () at ../sysdeps/i386/i686/multiarch/../memmove.S:111
#1  0x0804b3de in std::__copy_move<false, true, std::random_access_iterator_tag>::__copy_m<truc*> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_algobase.h:378
#2  0x0804b2af in std::__copy_move_a<false, truc**, truc**> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_algobase.h:397
#3  0x0804b4db in std::__copy_move_a2<false, truc**, truc**> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_algobase.h:436
#4  0x0804b3aa in std::copy<truc**, truc**> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_algobase.h:468
#5  0x0804b275 in std::__uninitialized_copy<true>::uninitialized_copy<truc**, truc**> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_uninitialized.h:93
#6  0x0804b03d in std::uninitialized_copy<truc**, truc**> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_uninitialized.h:117
#7  0x0804ad0f in std::__uninitialized_copy_a<truc**, truc**, truc*> (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110) at /usr/include/c++/4.4/bits/stl_uninitialized.h:257
#8  0x0804a24d in std::__uninitialized_move_a<truc**, truc**, std::allocator<truc*> > (__first=0x804f0f8, __last=0x804f0b8, __result=0x804f110, __alloc=...)
    at /usr/include/c++/4.4/bits/stl_uninitialized.h:267
#9  0x0804a50a in std::vector<truc*, std::allocator<truc*> >::_M_range_insert<__gnu_cxx::__normal_iterator<truc**, std::vector<truc*, std::allocator<truc*> > > > (this=0x804f04c, __position=..., __first=..., 
    __last=...) at /usr/include/c++/4.4/bits/vector.tcc:525
#10 0x08049a70 in std::vector<truc*, std::allocator<truc*> >::_M_insert_dispatch<__gnu_cxx::__normal_iterator<truc**, std::vector<truc*, std::allocator<truc*> > > > (this=0x804f04c, __pos=..., __first=..., 
    __last=...) at /usr/include/c++/4.4/bits/stl_vector.h:1102
#11 0x0804951c in std::vector<truc*, std::allocator<truc*> >::insert<__gnu_cxx::__normal_iterator<truc**, std::vector<truc*, std::allocator<truc*> > > > (this=0x804f04c, __position=..., __first=..., 
    __last=...) at /usr/include/c++/4.4/bits/stl_vector.h:874
#12 0x08048e57 in main () at ./main.cpp:43
(gdb)

cela me semble très louche ...

Ai-je manqué quelque chose dans mon code ?
Pouvez-vous m'éclairer ?

merci,

Bonjour,

L'insertion dans un vector invalide tous les itérateurs pointant sur ce vector. (Car lorsqu'un vecteur atteint sa capacité, il alloue un nouveau bloc de mémoire de taille ~2x supérieur à l'ancien, copie tous les éléments de l'ancien bloc au nouveau, puis détruit l'ancien)

Donc dès le premier tour de la boucle for, l'insert dans le vector invalide l'itérateur k.

Il est quand même possible de mettre à jour un vecteur dans une boucle for, mais il faut être très prudent et se baser sur les indices - qui sont stables - plutôt que sur les itérateurs.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 std::vector<truc*>& v2 = test[chose_deux]; for(map<truc *, vector<truc *> >::iterator it = test.begin() ; it != test.end() ; it++) { std::vector<truc*>& v = it->second; for(vector<truc *>::iterator k = v.begin() ; k != v.end() ; k++) { if(*k == chose_un) { int position_it = k - v.begin(); int range_size = v2.end() - v2.begin(); int offset = position_it + range_size; v.insert(k, v2.begin(), v2.end()); k = v.begin() + offset; } } }
C'est tout de suite un peu plus complexe, d'ailleurs je ne suis pas certain à 100% d'avoir correctement calculé l'offset, il y a peut être un +1 ou -1 à glisser quelque part :lol:

10/09/2010, 09h15
azmodai

Merci beaucoup pour la réponse !
en effet je n'avais pas vu venir le problème ...

ps: merci pour le bout de code !
10/09/2010, 10h32
koala01
Salut,

Ceci dit, je me demande bien pourquoi:
1. utiliser un pointeur comme clé de ta map
2. utiliser un pointeur comme élément de ton tableau
3. utiliser le même type pour représenter chaque tableau de ta map et la clé qui le représente
Truc ne serait-il pas, par hasard, une chaine "C style" (tableau de caractères terminés par un '\0'):question:

Si oui, tu devrais réellement réfléchir à manipuler plutôt des std:: (w)string, car la comparaison de chaines "C stye" au moment où tu effectue une recherche dans ta map se fera... selon l'adresse vers laquelle pointe le pointeur et non sur la valeur de la chaine (la nécessité d'utiliser strcmp en C pour comparer deux chaines de caractères ;))

De même, il n'y a que peu de raison pour manipuler des collections de pointeurs, de manière générale.

Ce devrait être réservé à la manipulation d'objet polymorphes et, en tout état de cause, un objet polymorphe se marie très mal avec la sémantique de valeur qui est nécessaire pour les clés d'une map ;)

Maintenant, je pars peut-être sur des bases bien fausses, et c'est donc à toi de voir ;)