C++ unordered_map mit char* als Schlüssel
Ich fühle mich erschöpft, wenn man versucht, die container unordered_map
mit char*
als Schlüssel (auf Windows, ich benutze VS 2010). Ich weiß, dass ich definieren muss, meine eigene compare-Funktion für char*
, die erbt von binary_function
. Das folgende ist ein Beispiel-Programm.
#include<unordered_map>
#include <iostream>
#include <string>
using namespace std;
template <class _Tp>
struct my_equal_to : public binary_function<_Tp, _Tp, bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const
{ return strcmp( __x, __y ) == 0; }
};
typedef unordered_map<char*, unsigned int, ::std::tr1::hash<char*>, my_equal_to<char*> > my_unordered_map;
//typedef unordered_map<string, unsigned int > my_unordered_map;
my_unordered_map location_map;
int main(){
char a[10] = "ab";
location_map.insert(my_unordered_map::value_type(a, 10));
char b[10] = "abc";
location_map.insert(my_unordered_map::value_type(b, 20));
char c[10] = "abc";
location_map.insert(my_unordered_map::value_type(c, 20));
printf("map size: %d\n", location_map.size());
my_unordered_map::iterator it;
if ((it = location_map.find("abc")) != location_map.end())
{
printf("found!\n");
}
return 0;
}
Füge ich den gleichen C-string abc
zweimal und nachschlagen. Die zweite Einfügung fehl und es wird nur einen abc
im unordered_map. Jedoch, die Ausgabe-Größe ist 3. Es scheint, dass die compare-Funktion funktioniert nicht richtig hier.
Darüber hinaus erhalte ich ein komisches Ergebnis über die find
- Funktion, durch die Ausführung des Programms für viele Male, die finden Ergebnis noch ändert! Manchmal wird die Zeichenfolge abc
gefunden wird, während die anderen Zeiten abc
wird nicht gefunden!!!
Könnte mir jemand helfen zu diesem? Ihre Hilfe ist sehr geschätzt!
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Edit: Nach der Definition einer hash-Funktion für char*
durch meine eigenen, das Programm ordnungsgemäß funktioniert. Das volle Programm-code ist unten aufgeführt. Danke an Euch alle.
#include<unordered_map>
#include <iostream>
using namespace std;
template <class _Tp>
struct my_equal_to : public binary_function<_Tp, _Tp, bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const
{ return strcmp( __x, __y ) == 0; }
};
struct Hash_Func{
//BKDR hash algorithm
int operator()(char * str)const
{
int seed = 131;//31 131 1313 13131131313 etc//
int hash = 0;
while(*str)
{
hash = (hash * seed) + (*str);
str ++;
}
return hash & (0x7FFFFFFF);
}
};
typedef unordered_map<char*, unsigned int, Hash_Func, my_equal_to<char*> > my_unordered_map;
int main(){
my_unordered_map location_map;
char a[10] = "ab";
location_map.insert(my_unordered_map::value_type(a, 10));
char b[10] = "abc";
location_map.insert(my_unordered_map::value_type(b, 20));
char c[10] = "abc";
location_map.insert(my_unordered_map::value_type(c, 20));
printf("map size: %d\n", location_map.size());
my_unordered_map::iterator it;
if ((it = location_map.find("abc")) != location_map.end())
{
printf("found!\n");
}
return 0;
}
Hinweis: die Verwendung char
* als Schlüssel-Art für eine unordered_map oder anderen STL-Containern kann gefährlich sein, einen sicheren Weg (scheint die einzige Möglichkeit zu sein) ist: in der main-Funktion new
oder malloc
einen block (z.B. ein array von c-strings) auf dem heap und füllen Sie es mit c-strings. Legen Sie diese c-strings in unordered_map. Die zugewiesenen Speicherblock freigegeben wird, am Ende der main-Funktion (durch delete
oder free
).
- Sie brauchen nicht zu Erben aus
binary_function
. Es könnte sogar sein, veraltet; ich kann nicht sehen es gerade jetzt. - Das ist nicht das problem, aber Namen, die zwei aufeinander folgende Unterstriche (
__x
,__y
) und Namen, die beginnen mit einem Unterstrich gefolgt von einem Großbuchstaben (_Tp
) sind reserviert für die Umsetzung (der compiler und seine Bibliothek). Verwenden Sie Sie nicht. - Meinst du den den Schlüssel-string zeigte
char*
verändert werden könnte? Denn das, Was ich denke, ist, dass Sie wollen, der Schlüssel zu konstanter string zeigteconst char *
. Machen Sie jedes vorkommenchar *
zuconst char *
um dies zu unterstützen - Gibt es tiefere Fragen, pls nehmen einen Blick auf die Antworten und die Kommentare darunter.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ihnen Komparator ist in Ordnung (auch wenn die übergabe eines nullptr ist nicht definiert und muss wohl behandelt werden)
Hash
::std::tr1::hash<char*>
ist hashing-off-Zeigern, so dass jeder "abc" geht (in der Regel) in einem anderen EimerMüssen Sie schreiben Sie Ihre eigenen hash-Funktion, die garantiert, dass hash("abc") gibt immer die gleiche Antwort
Vorerst - Leistung wird schrecklich sein, aber ein hash ist, gibt 0 zurück - und Sie sollten sehen, die zweite "abc" - match der ersten
Als pro-Kommentare - mit
std::string
vereinfacht die Speicherverwaltung und stellt eine Bibliothek unterstützte hash-und Komparator, also nurstd::unordered_map<std::string, X>
arbeiten. Dies bedeutet auch, dass mit der Löschung desunordered map
alle Zeichenketten werden aufgehoben für Sie. Sie können auch instanziieren derstd::strings
von char-arrays auf dem stack sicher.Wenn Sie noch verwenden möchten
char *
dann müssen Sie noch Ihre eigenen Komparator und hash, aber Sie könnenstd::shared_ptr
verwalten die Speicher für Sie (verwenden Sie keine stack-Instanzen - haben einnew char[]
)Sie haben dann eine
std::unordered_map<shared_ptr<char *>, X>
haben aber keine Komplikationen später von memory leaks.Wenn Sie noch verwenden möchten
char *
Sie sind auf dem richtigen Weg, aber es ist wichtig, dass Sie ein memory leak tool wie purify oder valgrind, um sicherzustellen, dass Sie wirklich haben Sie alle Speicher-management unter Kontrolle. (Dies ist in der Regel eine gute Idee für jedes Projekt)Schließlich, die Globale Variablen sollten vermieden werden.
char *
imstd::unordered_map
nicht, wie Sie zu vermeiden, mitchar *
mit Hilfe von string-wie bereits erwähnt - "Das folgende ist ein Beispiel für ein Programm" - meine Antwort befasst sich mit der Frage - Ihr Kommentar ist ein berechtigtes Anliegen - aber keine Lösung.unordered_map
variable hier ein Risiko sein?std::string
zu arbeiten, aber Ihre Antwort muss wirklich betonen, dass die ganze Idee ist ein hack, die Nutzung Einschränkungen gut über das STL-container, die Benutzer erwarten. Auch seine triviales Beispiel kann fehlschlagen, wenn ein compiler jemals versucht zu reklamieren, die Ihren Platz nach der insertion. Seine Aussage, dass "Manchmal die Zeichenfolge abc gefunden wird, während das andere mal" abc " nicht gefunden!" sollte eine starke Vermutung, dass dies bereits geschieht.unordered map
im gleichen Bereich wie diechar *
alle Einträge in der Karte werden sollten, ausdrücklich zugewiesen (nicht nur char[])Mit einem char-Zeiger als Schlüssel, wie Sie sind, oben ist fast sicher nicht das, was Sie tun möchten.
STL-Container-deal mit gespeicherten Werten, bei der
std::unordered_map<char *, unsigned int, ...>
Sie sind den Umgang mit Zeigern auf c-strings, die kann gar nicht sein, um auf die anschließende insertion/removal überprüft.Beachten Sie, dass Ihre
my_unordered_map
ist eine Globale variable, aber Sie versuchen, einfügen von lokalen char-arrays a, b, und c. Was erwarten Sie von Ihrem Vergleich-Funktionmy_equal_to()
zustrcmp()
wenn der eingefügte c-strings fallen aus dem Rahmen? (Sie haben plötzlich die Schlüssel verweisen auf zufällige Zeichen, die verglichen werden können, um neu eingefügte zukünftige Werte.)Ist es wichtig, dass die STL-map keys werden kopierbaren Werte, die nicht haben Ihre Bedeutung geändert durch externe Verhalten des Programms. Sollten Sie fast sicher
std::string
oder ähnliches für Ihre wichtigsten Werte, auch wenn Ihre Konstruktion scheint verschwenderisch, um Sie auf den ersten Blick.Werden die folgenden arbeiten genau, wie Sie beabsichtigen, die Dinge zu arbeiten, und ist wesentlich sicherer:
char*
eher alsstd::string
ist die Leistung des Programms. Ein anonymes Objekt derstd::string
erstellt werden jedes mal, wenn ich legen Sie eine Zeichenkette an. Und ich verstehe nicht, warum ein globalunordered_map
variable ein problem sein wird. Eigentlich ist der Zeiger übergebenmy_equal_to()
alle virtuellen Adressen in diesem Programm, und ich verstehe nicht, wie der eingefügte c-strings fallen aus dem Rahmen. Könnten Sie das bitte etwas näher erläutern?main
Funktionnew
einen block (z.B. ein array von c-strings) auf dem heap und füllen Sie es mit c-strings. Legen Sie diese c-strings in unordered_map. Diese Einschübe können gemischt werden, durch einige Anfragen. Die zugewiesenen Speicherblock freigegeben wird, am Ende dermain
Funktion (seidelete
). Wird diese Nutzung sicher?new
/malloc
einen block von Zeichen (char block[xxx], -nicht - char *foo[xx]), in die Sie die Kopie der c-string-Zeichen.the Answer
.Wenn du etwas definierst, wie "abc" es zugewiesen bekommt einen const char*. Jedes mal, wenn Sie schreiben "abc" in Ihrem Programm, es geht um eine neue Speicherkarte alocated. Also:
Wird immer false zurückgeben, da der neue Speicher ist alocated jedes mal "abc" ist wrriten (sorry, wenn ich Klinge ein bisschen eintönig).
my_equal_to
sagt. Scheint, dass es nicht funktioniert?