/ Forside / Teknologi / Udvikling / C/C++ / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
C/C++
#NavnPoint
BertelBra.. 2425
pmbruun 695
Master_of.. 501
Bech_bb 500
kyllekylle 500
jdjespers.. 500
gibson 300
scootergr.. 300
molokyle 287
10  strarup 270
C++ hashtable hjælp
Fra : Martin M. Pedersen


Dato : 07-04-07 16:42

Hejsa,

Jeg programmerer i C++ og bruger g++ (GCC) 4.1.2.


class Traxboard {
public:
bool operator==(const Traxboard& another) const;
bool operator<(const Traxboard& another) const;
int getHash() const;
}

Jeg ønsker at gemme en masse objekter af typen Traxboard i en hashtable
og bruge værdien fra getHash() som hash-funktionen for hashtablen.

Indtil videre har jeg har fundet ud af at det ikke findes i STL (endnu),
men at der er på vej[1]. Ifølge gcc-dokumentationen kan man bruge
unordered_set til mit formål, men hvordan ? Jeg har kigget i
dokumentionen, men forstår den ikke rigtigt[2].

Hvad definerer jeg en unordered_set korrekt i dette tilfælde ?

/Martin

[1]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
[2]:
http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/classstd_1_1tr1_1_1unordered__set.html

 
 
Mogens Hansen (07-04-2007)
Kommentar
Fra : Mogens Hansen


Dato : 07-04-07 17:16


"Martin M. Pedersen" <traxplayer@gmail.com> wrote in message
news:4617bc26$0$52176$edfadb0f@dread11.news.tele.dk...

[8<8<8<]
> Hvad definerer jeg en unordered_set korrekt i dette tilfælde ?

Jeg har ikke prøvet at bruge unordered_set, men du burde kunne skrive noget
i retningen af:

struct TraxboardHash
{
std::size_t operator()(const Traxboard& val)
{ return val.getHash(); }
};

unordered_set<Traxboard, TraxboardHash> traxboards;

--
Venlig hilsen

Mogens Hansen



Martin M. Pedersen (07-04-2007)
Kommentar
Fra : Martin M. Pedersen


Dato : 07-04-07 19:57

Mogens Hansen wrote:
> "Martin M. Pedersen" <traxplayer@gmail.com> wrote in message
> news:4617bc26$0$52176$edfadb0f@dread11.news.tele.dk...
>
> [8<8<8<]
>> Hvad definerer jeg en unordered_set korrekt i dette tilfælde ?
>
> Jeg har ikke prøvet at bruge unordered_set, men du burde kunne skrive noget
> i retningen af:
>
> struct TraxboardHash
> {
> std::size_t operator()(const Traxboard& val)
> { return val.getHash(); }
> };
>
> unordered_set<Traxboard, TraxboardHash> traxboards;
>

Mange tak. Det hjalp mig lidt videre. Jeg får dog nu en kæmpe
fejl-besked, som jeg har pastet i bunden. Hvordan skal flg. forståes ?

namespace std {
namespace tr1 {
template <class Value,
class Hash = hash<Value>,
class Pred = std::equal_to<Value>,
class Alloc = std::allocator<Value> >
class unordered_set;
}
}

=====================================================

g++ -O3 -DDEBUG -Wall -Wunused -Wcast-qual -Wconversion
-Woverloaded-virtual -Werror -c openingbook.cpp
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/hashtable:
In member function ‘void std::tr1::hashtable<Key, Value, Allocator,
ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code,
constant_iterators, unique_keys>::m_deallocate_node(Internal::hash_node
<Value, cache_hash_code>*) [with Key = Traxboard, Value = Traxboard,
Allocator = std::allocator<Traxboard>, ExtractKey =
Internal::identity<Traxboard>, Equal = std::equal_to<Traxboard>,
H1 = TraxboardHash, H2 = Internal::mod_range_hashing, H =
Internal::default_ranged_hash, RehashPolicy =
Internal::prime_rehash_policy, bool cache_hash_code = false, bool
constant_iterators = true, bool unique_keys = true]’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/hashtable:1341:
instantiated from ‘void std::tr1::hashtable<Key, Value, Allocator,
ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code,
constant_iterators, unique_keys>::m_deallocate_nodes(Internal::ha
sh_node<Value, cache_hash_code>**, typename Allocator::size_type) [with
Key = Traxboard, Value = Traxboard, Allocator =
std::allocator<Traxboard>, ExtractKey = Internal::identity<Traxboa
rd>, Equal = std::equal_to<Traxboard>, H1 = TraxboardHash, H2 =
Internal::mod_range_hashing,
H = Internal::default_ranged_hash, RehashPolicy =
Internal::prime_rehash_policy, bool cache_h
ash_code = false, bool constant_iterators = true, bool unique_keys =
true]’/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/hashtable:1896:
instantiated from ‘void std::tr1::hashtable<Key, Value, Allocator,
ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code,
constant_iterators, unique_keys>::clear() [with Key = Traxboard,
Value = Traxboard, Allocator = std::allocator<Traxboard>, ExtractKey =
Internal::identity<Traxboard>, Equal = std::equal_to<Traxboard>, H1 =
TraxboardHash, H2 = Internal::mod_range_hashing, H =
Internal::default_ranged_hash, RehashPolicy =
Internal::prime_rehash_policy, bool cache_hash_code = false, bool
constant_iterators = true, bool unique_keys = true]’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/hashtable:1494:
instantiated from ‘std::tr1::hashtable<Key, Value, Allocator,
ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code,
constant_iterators, unique_keys>:hashtable() [with Key = Traxboard,
Value = Traxboard, Allocator = std::allocator<Traxboard>, ExtractKey =
Internal::identity<Traxboard>, Equal = std::equal_to<Traxboard>, H1 =
TraxboardHash, H2 = Internal::mod_range_hashing, H =
Internal::default_ranged_hash, RehashPolicy =
Internal::prime_rehash_policy, bool cache_hash_code = false, bool
constant_iterators = true, bool unique_keys = true]’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/unordered_set:61:
instantiated from here
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/tr1/hashtable:1322:
error: invalid use of void expression
make: *** [openingbook.o] Error 1






Mogens Hansen (07-04-2007)
Kommentar
Fra : Mogens Hansen


Dato : 07-04-07 20:30


"Martin M. Pedersen" <traxplayer@gmail.com> wrote in message
news:4617e9bb$0$52084$edfadb0f@dread11.news.tele.dk...

[8<8<8<]
> Mange tak. Det hjalp mig lidt videre. Jeg får dog nu en kæmpe fejl-besked,
> som jeg har pastet i bunden.

Tak for kaffe
Den er nok værd at lære udenad

Umiddelbart giver den mig ikke skyggen af hint til hvad der er galt, men jeg
ville kigge på template parameteren Pred.

struct TraxboardHash
{
std::size_t operator()(const Traxboard& val)
{ return val.getHash(); }
};

struct TraxboardEqual
{
bool operator(const Traxboard& lhs, const Traxboard& rhs)
{ return lhs == rhs; }
};

unordered_set<Traxboard, TraxboardHash, TraxboardEqual> traxboards;

> Hvordan skal flg. forståes ?
>
> namespace std {
> namespace tr1 {
> template <class Value,
> class Hash = hash<Value>,
> class Pred = std::equal_to<Value>,
> class Alloc = std::allocator<Value> >
> class unordered_set;
> }
> }

Det er en template klasse "unordered_set" som ligger i namespacet
"std::tr1", og har 4 template parametre, hvoraf de 3 sidste har en default
type.
Den første angiver hvordan man beregner hash-værdien, den anden hvordan man
finder ud af om 2 objekter har samme værdi og den sidste styrer hvordan
containeren allokerer sin hukommelse.

--
Venlig hilsen

Mogens Hansen



Martin M. Pedersen (08-04-2007)
Kommentar
Fra : Martin M. Pedersen


Dato : 08-04-07 22:21

Martin M. Pedersen wrote:
> Jeg ønsker at gemme en masse objekter af typen Traxboard i en hashtable
> og bruge værdien fra getHash() som hash-funktionen for hashtablen.
>

Jeg har nu fået lavet mig et simplet og lille eksempel. Jeg ved godt at
hash funktionen m.m. ikke er ok, men det burde ikke være grunden til en
compiler fejl.


=======

#include <tr1/unordered_set>

class Traxboard {
public:
Traxboard();
bool operator==(const Traxboard& another) const;
bool operator!=(const Traxboard& another) const;
bool operator<(const Traxboard& another) const;
int getHash() const;
private:
int hashvalue;
};


Traxboard::Traxboard()
{
hashvalue=42;
}


bool Traxboard:erator!=(const Traxboard& another) const
{
if (getHash()!=another.getHash()) return true;
return false;
}


bool Traxboard:erator==(const Traxboard& another) const
{
if (getHash()!=another.getHash()) return false;
return true;
}


bool Traxboard:erator<(const Traxboard& another) const
{
return (getHash()<another.getHash());
}


int Traxboard::getHash() const
{
return hashvalue;
}


struct TraxboardHash
{
std::size_t operator()(const Traxboard& t)
{
return t.getHash();
}
};



int main()
{
std::tr1::unordered_set <Traxboard, TraxboardHash> traxboards;

return 1;
}

=======
   
tusk@skarbinika/programming/jiga/jiga/stl$ gcc -o trax trax.cpp -lm
/tmp/ccdH2hod.o: In function
`__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false>*>::allocate(unsigned int, void const*)':
trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE8allocateEjPKv[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false>*>::allocate(unsigned int, void const*)]+0x24): undefined
reference to `std::__throw_bad_alloc()'
trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE8allocateEjPKv[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false>*>::allocate(unsigned int, void const*)]+0x32): undefined
reference to `operator new(unsigned int)'
/tmp/ccdH2hod.o: In function
`__gnu_cxx::new_allocator<Internal::hash_node<Traxboard, false>
>::deallocate(Internal::hash_node<Traxboard, false>*, unsigned int)':
trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIN8Internal9hash_nodeI9TraxboardLb0EEEE10deallocateEPS4_j[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false> >::deallocate(Internal::hash_node<Traxboard, false>*, unsigned
int)]+0xd): undefined reference to `operator delete(void*)'
/tmp/ccdH2hod.o: In function
`__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false>*>::deallocate(Internal::hash_node<Traxboard, false>**, unsigned
int)':
trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE10deallocateEPS5_j[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
false>*>::deallocate(Internal::hash_node<Traxboard, false>**, unsigned
int)]+0xd): undefined reference to `operator delete(void*)'
/tmp/ccdH2hod.o:(.eh_frame+0x12): undefined reference to
`__gxx_personality_v0'
collect2: ld returned 1 exit status

Arne Vajhøj (08-04-2007)
Kommentar
Fra : Arne Vajhøj


Dato : 08-04-07 22:44

Martin M. Pedersen wrote:
> Martin M. Pedersen wrote:
>> Jeg ønsker at gemme en masse objekter af typen Traxboard i en
>> hashtable og bruge værdien fra getHash() som hash-funktionen for
>> hashtablen.
>
> Jeg har nu fået lavet mig et simplet og lille eksempel. Jeg ved godt at
> hash funktionen m.m. ikke er ok, men det burde ikke være grunden til en
> compiler fejl.

> tusk@skarbinika/programming/jiga/jiga/stl$ gcc -o trax trax.cpp -lm

Start lige med at prøve:

g++ -o trax trax.cpp -lm

> /tmp/ccdH2hod.o: In function
> `__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false>*>::allocate(unsigned int, void const*)':
> trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE8allocateEjPKv[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false>*>::allocate(unsigned int, void const*)]+0x24): undefined
> reference to `std::__throw_bad_alloc()'
> trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE8allocateEjPKv[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false>*>::allocate(unsigned int, void const*)]+0x32): undefined
> reference to `operator new(unsigned int)'
> /tmp/ccdH2hod.o: In function
> `__gnu_cxx::new_allocator<Internal::hash_node<Traxboard, false>
> >::deallocate(Internal::hash_node<Traxboard, false>*, unsigned int)':
> trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIN8Internal9hash_nodeI9TraxboardLb0EEEE10deallocateEPS4_j[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false> >::deallocate(Internal::hash_node<Traxboard, false>*, unsigned
> int)]+0xd): undefined reference to `operator delete(void*)'
> /tmp/ccdH2hod.o: In function
> `__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false>*>::deallocate(Internal::hash_node<Traxboard, false>**, unsigned
> int)':
> trax.cpp:(.text._ZN9__gnu_cxx13new_allocatorIPN8Internal9hash_nodeI9TraxboardLb0EEEE10deallocateEPS5_j[__gnu_cxx::new_allocator<Internal::hash_node<Traxboard,
> false>*>::deallocate(Internal::hash_node<Traxboard, false>**, unsigned
> int)]+0xd): undefined reference to `operator delete(void*)'
> /tmp/ccdH2hod.o:(.eh_frame+0x12): undefined reference to
> `__gxx_personality_v0'
> collect2: ld returned 1 exit status

Arne

Martin M. Pedersen (08-04-2007)
Kommentar
Fra : Martin M. Pedersen


Dato : 08-04-07 22:55

Arne Vajhøj wrote:
> Martin M. Pedersen wrote:
>> Martin M. Pedersen wrote:
>>> Jeg ønsker at gemme en masse objekter af typen Traxboard i en
>>> hashtable og bruge værdien fra getHash() som hash-funktionen for
>>> hashtablen.
>>
>> Jeg har nu fået lavet mig et simplet og lille eksempel. Jeg ved godt at
>> hash funktionen m.m. ikke er ok, men det burde ikke være grunden til
>> en compiler fejl.
>
>> tusk@skarbinika/programming/jiga/jiga/stl$ gcc -o trax trax.cpp -lm
>
> Start lige med at prøve:
>
> g++ -o trax trax.cpp -lm

Oh. Dumme mig. Tak for hjælpen.

/Martin

Søg
Reklame
Statistik
Spørgsmål : 177416
Tips : 31962
Nyheder : 719565
Indlæg : 6407858
Brugere : 218876

Månedens bedste
Årets bedste
Sidste års bedste