Discussion :

[ncheboi]

Bonjour. Je cherche à convertir un char* en référence sur un string. En gros faire quelque chose comme ça...

Code :

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

1
2
3
 
char* c = "church";
string &s = c;

Mais le compilateur veux pas. Existe-t-il un autre moyen?

Le but de l'opération est le suivant:

• je reçois une base de données sous la forme d'un char*
• une entrée correspond à une clé de 16 charactères plus 32 charactères de données.
• du coup la base est un char* vers des entrées de 48 chars qui se suivent

J'ai un algo qui trie ma base sur la clé. Sauf que j'ai écrit l'algo avec des clés qui sont des string...
Du coup, je veux crée des string à partir des clé... Pour être plus précis, je veux des références vers des string.
La base va contenir un million d'entrée du coup, je veux pas tout recopié... Existe-t-il une solution pour mon problème?

[koala01]

Salut,

Là, tu essaye en fait de créer une référence sur une std::sting qui devrait faire référence à un pointeur sur char...

Or, une référence doit faire référence à un objet (du type adéquat) existant, et un char* n'est pas un std::string

Par contre, tu peux créer une std::string (non référence ) au départ d'un char*, soit en utilisant l'une des surcharges du constructeur, soit en utilisant l'opérateur = :

Code :

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

1
2
3
char * c="coucou";
std::string ok1(c);
std::string ok2=c;

A partir de là, rien ne t'empêche de créer une référence sur ta std::string, si tu le souhaites:

Code :

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

1
2
3
 
std::string & ref1 =ok1;
std::string & ref2 =ok2;

Ceci dit: lorsqu'il s'agit de déclarer une variable en vue de l'utiliser dans la fonction, il ne sert pas à grand chose d'en créer une référence par la suite, pour la simple raison que l'on risque d'appliquer des modifications à la référence sans se rendre compte que l'on modifie en réalité la chaine originale (ou inversément), et que, la distraction aidant, on peut facilement en arriver à se demander pourquoi l'une a été modifiée alors que l'on modifiait l'autre

Il est généralement "de bon ton" de réserver l'usage des références (constantes ou non) au passage d'arguments, à quelques exceptions près

[ncheboi]

Hmmm. Merci pour la réponse mais je crois pas que ça ne résoud pas mon problème. Le truc c'est que je vais recevoir un char* pointant sur plus de 48 000 000 de chars... Ca fait dans les 90mega...

Je dois trier tout ça. Grosso modo, la chaine comporte des entrées les unes à la suite de l'autre, les 16 premiers chars sont une clé pour le tri, les 32 une adresse web...

Mais j'ai écrit mon algo pour traiter les clés comme stockées dans un
objet: std::vector <string> &s...
Du coup, j'ai pensé utiliser mon vector pour contenir des références vers les strings qui sont contenu dans 1 grand char... j'espere que tu me suis...

Est-ce que c'est possible?
Mon autre alternative est de modifié mon algo pour trier sur des char* au lieu de string mais bon....

[Arzar]

Bonjour,


Si et seulement si tes clés sont immutables (pas de modification sur les clés) alors il existe une solution très pratique qui consiste à créer une classe représentant un wrapper extrêmement léger sur une chaine en mémoire (un char* + une taille) mais qui propose l'interface familière de std::string

Sauf qu'il n'y a pas besoin de le coder soit-même, vu que des gros projets C++ open-source l'ont déjà fait (mais bizarrement pas boost. Pourtant ce genre de classe extrêmement utile me semble pile-poil dans le scope de boost mais bon...)

Par exemple :

StringPiece du projet google Chrome :
http://code.google.com/p/re2/source/.../stringpiece.h

ou StringRef du projet LLVM :
http://llvm.org/svn/llvm-project/llv...DT/StringRef.h
http://llvm.org/svn/llvm-project/llv.../StringRef.cpp

Très pratique car :
- License BSD
- Pas de dépendance (pour StringRef il faut quand même virer deux trois fonctions qui induisent des dépendances vers d'autres parties de LLVM)

Donc si tout se passe bien, dans ton cas, il devrait suffire de rajouter un constructeur StringPiece(char*, size_t) pour limiter aux 16 premiers char de la clé, puis dans ton algo de tri faire un chercher/remplacer de std::string par StringPiece/StringRef, et ça devrait suffire.

[JolyLoic]

puis dans ton algo de tri faire un chercher/remplacer de std::string par StringPiece/StringRef, et ça devrait suffire.

Voire de templatiser l'algorithme de tri pour qu'il marche avec des std::string, des StringPiece, des StringRef...

[gb_68]

Voire de templatiser l'algorithme de tri pour qu'il marche avec des std::string, des StringPiece, des StringRef...

Voire même aller jusqu'à prendre une paire d'itérateurs en paramètres (pour pouvoir prendre char *, std::string, des StringPiece, des StringRef ... ).


Mais l'intérêt de ces classes (StringPiece, StringRef) semble justement être d'encapsuler cette paire d'itérateurs (en conservant la taille en plutôt qu'un iterateur "past to end") pour une utilisation plus intuitive.

Toutes ces solutions supposent néanmoins d'avoir accès à la taille / fin de la chaîne. Si tu ne la possèdes pas, cela peut aussi avoir un coup de la calculer.

[ncheboi]

Bonjour,


Si et seulement si tes clés sont immutables (pas de modification sur les clés) alors il existe une solution très pratique qui consiste à créer une classe représentant un wrapper extrêmement léger sur une chaine en mémoire (un char* + une taille) mais qui propose l'interface familière de std::string

Sauf qu'il n'y a pas besoin de le coder soit-même, vu que des gros projets C++ open-source l'ont déjà fait (mais bizarrement pas boost. Pourtant ce genre de classe extrêmement utile me semble pile-poil dans le scope de boost mais bon...)

Par exemple :

StringPiece du projet google Chrome :
http://code.google.com/p/re2/source/.../stringpiece.h

ou StringRef du projet LLVM :
http://llvm.org/svn/llvm-project/llv...DT/StringRef.h
http://llvm.org/svn/llvm-project/llv.../StringRef.cpp

Très pratique car :
- License BSD
- Pas de dépendance (pour StringRef il faut quand même virer deux trois fonctions qui induisent des dépendances vers d'autres parties de LLVM)

Donc si tout se passe bien, dans ton cas, il devrait suffire de rajouter un constructeur StringPiece(char*, size_t) pour limiter aux 16 premiers char de la clé, puis dans ton algo de tri faire un chercher/remplacer de std::string par StringPiece/StringRef, et ça devrait suffire.

Merci, je jette un coup d'oeil à tout ça et je vous tiens rapidement au courant. Par contre, je sais pas trop si je vais pouvoir me servir, mon prof est assez chiant là dessus et il voulait qu'on utilise uniquement les librairies "classiques"... Le problème c'est qu'à la base, le devoir était prévu pour du C mais il a autorisé à ce qu'on utilise C++. Du coup, j'ai écrit mon algo en utilisant des strings... bref, je vais voir tout ça et au pire des cas, ben je changerai mes strings en char*...

[ncheboi]

Dans tous les cas, si j'utilise un wrapper, je vais quand même créer des objets en plus? Si je manipule les char* directement je prends moins de place non? Bien sur c'est plus galère à gérer que les string mais bon...

Mon objectif avec les références c'était de ne rien créer en plus....

[jblecanard]

Mon objectif avec les références c'était de ne rien créer en plus....

Si tu utilises un wrapper, que ce soint un std::string ou autre, tu auras effectivement de la création d'objets. On n'a rien sans rien en échange ! Par contre, création d'objet ne veut pas dire copie du stream de char. Un wrapper peut utiliser un pointeur sur une zone du tableau pour éviter la recopie comme tu le désires, ce qui limitera l'utilisation supplémentaire de mémoire. A priori, si tu en es déjà à 90 Mo, tu n'es plus à quelques Mo près non ?

[JolyLoic]

Dans tous les cas, si j'utilise un wrapper, je vais quand même créer des objets en plus?

En plus que si tu ne fais rien, oui.

Si je manipule les char* directement je prends moins de place non?

Pas forcément. Si tu manipules des char*, tu crées aussi des objets, de type char*. Et il y a aussi des chances que tu crées des objets soit de type size_t, soit de type char* pour repérer la fin de la chaîne.

L'idée du wrapper est justement qu'il est composé uniquement de ces deux informations, et ne prend pas plus de place que si tu faisais le boulot à la main.

[Arzar]

Si je manipule les char* directement je prends moins de place non? Bien sur c'est plus galère à gérer que les string mais bon...

Peut être que j'ai mal compris le problème, mais a priori le code qui trie les clés devrait être très proche que ce soit avec std::string ou char*, non ?
Avec StringPiece je suppose que ça ressemblerait à peu près à ça :

Code :

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

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
 
#include "StringPiece.h"
#include <vector>
#include <iostream>
#include <algorithm>
 
char* data = "abcdef1234567890www.yahoo.fr                    1234567890abcdefwww.google.fr                   ";
int data_size = 64;
 
int main()
{
   std::vector<StringPiece> keys;
   for(int i = 0 ; i < data_size ; i+= 48)
   {
      keys.push_back(StringPiece(data + i, 16));
   }
   std::sort(keys.begin(), keys.end());
   for(unsigned int i = 0 ; i < keys.size() ; i++)
   {
      StringPiece key = keys[i];
      StringPiece url(key.end(), 32);
      std::cout << "key : " << key << "\n";
      std::cout << "url : " << url << "\n";
   }
}

Dans ce cas on peut en effet gagner quelques mégas en manipulant un std::vector<char*>. Il n'y a pas beaucoup de changement à faire, le plus gros étant de passer à std::sort la fonction qui fait la comparaison des clés...

[ncheboi]

Ok. Merci pour l'exemple d'implémentation.
Sinon une question concernant les namespace. Je peux avoir

Code :

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

1
2
3
 
using namespace std;
using namespace re2;

sans avoir de conflit?

Sinon, quand je tente de compilé il me dit qu'il y a un problème de symbole externe non résolu.
J'ai vu que c'était du au fait que dans StringPiece.h, la redéfinition de l'opérateur << est:

Code :

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

1
2
 
extern std::ostream& operator<<(std::ostream& o, const re2::StringPiece& piece);

Que-faut il que je rajoute pour que ça fonctionne?
Merci encore

[Arzar]

Bonjour,
Je pense que le mieux soit que tu utilises uniquement des char* si c'est pour un devoir un C avec C++ toléré mais limité à la biblio standard.
Avec le bout de code montré plus haut les changements sont minimes. Il suffit de :
- Remplir un std::vector de char* avec des pointeurs se décalant de 48 octets en 48.
- Passer à la fonction std::sort une fonction binaire de comparaison (un prédicat voir la faq) qui prend en paramètre deux char* et renvoie un booléen si une clé est inférieure à une autre. (voir la fonction de la biblio C "memcmp").

Car j'imagine que le but de l’exercice est de manipuler des pointeurs quand même. Donc au boulot

[ncheboi]

Bonjour,
- Passer à la fonction std::sort une fonction binaire de comparaison (un prédicat voir la faq) qui prend en paramètre deux char* et renvoie un booléen si une clé est inférieure à une autre. (voir la fonction de la biblio C "memcmp").

Car j'imagine que le but de l’exercice est de manipuler des pointeurs quand même. Donc au boulot

Non non le but c'est pas de manipuler les pointeurs. Au fait, je dois implémenter le tri radix en parallèle avec OpenMP... Le truc c'est que je suis parti sur des vector de string alors que je reçois un char* en paramètre...
L'algo marche bien (après plusieurs journées de reflexion, débogage(merci VS), et pertes de cheveux)... La je dois juste prendre le char*, le découper et remplir un vector sur lequel je fais mon tri... Du coup la class StringPiece est bien utile . Par contre, toujours pas possible de gérer mon problème avec

Code :

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

1
2
 
extern std::ostream& operator<<(std::ostream& o, const re2::StringPiece& piece);

[Arzar]

Au fait, je dois implémenter le tri radix en parallèle avec OpenMP...

Chouette exo !

Par contre, toujours pas possible de gérer mon problème avec :

Code :

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

extern std::ostream& operator<<(std::ostream& o, const re2::StringPiece& piece);

et bien en fait, je ne savais même pas qu'on pouvait déclarer une fonction extern (une variable oui, mais une fonction !?) Je ne comprends pas trop l'utilité d'ailleurs, qu'en pense les autres participants ?

Bon sinon le but de cette fonction est simplement de pouvoir afficher une StringPiece grâce à un flux (voir faq)
Remplace par une fonction classique ça devrait suffire :
Dans le .h

Code :

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

std::ostream& operator<<(std::ostream& o, const re2::StringPiece& piece);

Et dans un .cpp

Code :

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

1
2
3
4
5
std::ostream& operator<<(std::ostream& o, const re2::StringPiece& piece)
{
   o << piece.as_string();
   return o;
}

[ncheboi]

Bon finalement je me suis rendu compte que partir avec un vector de char* changeait pas beaucoup à mon algo...

Par contre, un nouveau problème...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void pRadix_sort2(char *database)
{
	vector <char*> keys;
	int db_length = strlen(database);
	//after his for loop, the keys vector will contain pointers to the beginning of each key
	for(int i = 0 ; i < db_length ; i+=48)
	{
		keys.push_back(database + i);
	}
 
	//we sort the keys array starting from the end of the keys
	for(int i = KEY_LENGTH - 1; i >=0 ; i--)
		pCounting_sort2(keys,i);
 
/*	for(std::vector<char*>::iterator i = keys.begin(); i != keys.end(); ++i)
	{
		database 
	}*/
}

J'ai donc pris mon char* en entrée, créer un vector <char*> contenant les pointeurs vers le début de chaque clé... Après le tri, je me retrouve avec un vector <char*> contenant les pointeurs vers les clé dans l'ordre trié.
Maintenant je dois reconstruire mon char* dans l'ordre.
Grosso modo, il s'agit de parcourir mon tableau et de faire un truc du genre:

Code :

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

1
2
3
4
5
 
//pseudocode
char* sortedDB = null;
for i= keys.begin to keys.end
      sortedDB += (48 chars starting from keys[i])

J'ai vu que la fonction strcat() pouvait m'aider à concaténer des char* mais j'ai besoin qu'elle concatène juste un bout... Si je fait
strcat(sortedDB,keys[i]);
il rajoute la chaine situé après la clé, si c'est la première clé, il rajoutera toute la database et non pas les 48 premiers char....

[Matthieu Brucher]

(mais bizarrement pas boost. Pourtant ce genre de classe extrêmement utile me semble pile-poil dans le scope de boost mais bon...)

Si, si, ça existe, ce sont les iterator_range qui font bien plus que les strings. Aucun intérêt d'avoir plus que ces bêtes-là

il rajoute la chaine situé après la clé, si c'est la première clé, il rajoutera toute la database et non pas les 48 premiers char....

strncat ?

[ncheboi]

strncat ?

Nikel. Voila ce que j'ai fait:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
char* temp_db = (char*)malloc(sizeof(database));
*temp_db = '\0'; //initialiser à chaine vide, si je fais pas ça, la chaine contient des trucs bizarre avant
cout << "length: " << strlen(temp_db) << endl;
cout << "size of keys: " << keys.size() << endl;
for(std::vector<char*>::iterator pKey = keys.begin(); pKey != keys.end(); ++pKey)
{
	strncat(temp_db, *pKey, 48);
}
database = strdup(temp_db);
cout << "after sort: " << endl << temp_db << endl;
cout << "size of temp_db" << strlen(temp_db) << endl;
free(temp_db);

J'execute en pas à pas sous VS et je vois que ça m'a mit les entrées dans l'ordre voulu. Par contre, quand j'arrive à la fin de la fonction, VS me lance une belle erreur:

Windows a déclenché un point d'arret dans abc.exe.
Cela peut etre due à une défaillance du tas qui indique un bogue dans abc.exe ou l'une des DLL chargées.
Cela peut également être du à l'appui sur F12...

Bref, un truc qui me dit pas grand chose sur d'où vient l'erreur...
Si j'execute sans débogage (Ctrl+F5 sous VS), j'ai une autre erreur(en anglais cette fois):
HEAP CORRUPTION DETECTED: after Normal block (#356) at 0x002B78B8.
CRT detected that application wrote to memory after end of heap buffer.

Bon du coup, je me doute que j'ai un problème avec la mémoire... Le truc c'est que je sais pas lequel...
La fonction strncat écrit les charactères voulus, plus '\0' (selon la doc)... Du coup, est-ce que c'est pas lié à ça? C'est bizarre parce que juste avant de faire le free j'arrive à imprimer database avec un

Code :

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

1
2
 
cout << database << endl;

[ncheboi]

bon en révisant un peu l'allocation dynamique, j'ai vu qu'en c++, on devait plutot utilisé new et delete...
bref, mon problème est donc résolue:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
char* temp_db = new char;
*temp_db = '\0';
cout << "length: " << strlen(temp_db) << endl;
cout << "size of keys: " << keys.size() << endl;
 
for(std::vector<char*>::iterator pKey = keys.begin(); pKey != keys.end(); ++pKey)
{
	strncat(temp_db, *pKey, 48);
}
database = strdup(temp_db);
cout << "after sort: " << endl << database << endl;
cout << "size of temp_db: " << strlen(temp_db) << endl;
//delete temp_db; <- plante si je décommente ça...

par contre, quand je veux faire delete à la fin( ligne en commentaire), il me relance l'erreur de HEAP MEMORY etc...

[r0d]

Bonjour,

Je ne suis pas sûr (je n'utilise jamais de char*), mais qu'est-ce que ça donne si tu fais:

Code :

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

delete [] temp_db;