Discussion:
Using GUID as the key for std::map
(too old to reply)
Faisal
2009-11-19 13:27:17 UTC
Permalink
Raw Message
I've a map which uses GUID as the key.

#include <map>
#include <string>
#include <unknwn.h>

void main()
{
std::map<GUID, std::string> map;

GUID d1;
std::string szName = "test";

map[d1] = szName;
}

But when compiling this code in VS2008 shows following errors

c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not
deduce template argument for 'const
std::basic_string<_Elem,_Traits,_Alloc> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(150) : see declaration of 'std::operator <'
1> c:\program files\microsoft visual studio 9.0\vc\include
\functional(142) : while compiling class template member function
'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const _Elem *,const
std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce
template argument for 'const _Elem *' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(140) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::basic_string<_Elem,_Traits,_Alloc> &,const
std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce
template argument for 'const std::basic_string<_Elem,_Traits,_Alloc>
&' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(130) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const std::_Tree<_Traits>
&,const std::_Tree<_Traits> &)' : could not deduce template argument
for 'const std::_Tree<_Traits> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include\xtree
(1466) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2>
&)' : could not deduce template argument for 'const
std::reverse_iterator<_RanIt> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\xutility(2262) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2>
&)' : could not deduce template argument for 'const
std::_Revranit<_RanIt,_Base> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\xutility(2072) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2>
&,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument
for 'const std::pair<_Ty1,_Ty2> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\utility(99) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2676: binary '<' : 'const GUID' does not define this
operator or a conversion to a type acceptable to the predefined
operator
1


How can i solve this?
Giovanni Dicanio
2009-11-19 13:43:37 UTC
Permalink
Raw Message
Post by Faisal
I've a map which uses GUID as the key.
[...]
Post by Faisal
But when compiling this code in VS2008 shows following errors
I would suggest you to define an operator< for GUID's, e.g.

<code>

inline bool operator<( const GUID & lhs, const GUID & rhs )
{
return ( memcmp( &lhs, &rhs, sizeof(GUID) ) > 0 ? true : false );
}

</code>


Giovanni
Giovanni Dicanio
2009-11-19 13:54:46 UTC
Permalink
Raw Message
Post by Giovanni Dicanio
inline bool operator<( const GUID & lhs, const GUID & rhs )
{
return ( memcmp( &lhs, &rhs, sizeof(GUID) ) > 0 ? true : false );
Probably this should better be:

return ( memcmp( &lhs, &rhs, sizeof(GUID) ) < 0 ? true : false );

i.e. '<' instead of a '>' considering the semantics of memcmp and the fact
that we are overloading operator<.

Giovanni
Victor Bazarov
2009-11-19 14:04:33 UTC
Permalink
Raw Message
Post by Giovanni Dicanio
Post by Giovanni Dicanio
inline bool operator<( const GUID & lhs, const GUID & rhs )
{
return ( memcmp( &lhs, &rhs, sizeof(GUID) ) > 0 ? true : false );
return ( memcmp( &lhs, &rhs, sizeof(GUID) ) < 0 ? true : false );
i.e. '<' instead of a '>' considering the semantics of memcmp and the
fact that we are overloading operator<.
Say, what prevents *you* from writing

return memcmp(&lhs, &rhs, sizeof(GUID)) < 0;

? Why do you feel the need for the op ?: and 'true' and 'false'? And
what's with the parentheses? And why stop at just one? Keep going:

return ((((((memcmp(..)<0)?true:false)?true:false)?true:false)));

The compiler can take it.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Giovanni Dicanio
2009-11-20 09:48:50 UTC
Permalink
Raw Message
Post by Victor Bazarov
Say, what prevents *you* from writing
return memcmp(&lhs, &rhs, sizeof(GUID)) < 0;
? Why do you feel the need for the op ?: and 'true' and 'false'? And
what's with the parentheses?
Maybe just personal coding style :)

I could prefer:

return ( <some expression> );

instead of:

return <some expression>;

...Like there are people who love using Hungarian notation, people who
dislike it, people who use braces like this:

if (...) {
...
} else {
....
}

other who likes (like me):

if (...)
{
...
}
else
{
...
}

:)


Giovanni
Stephen Howe
2009-11-19 20:49:22 UTC
Permalink
Raw Message
inline bool operator<( const GUID & lhs, const GUID & rhs )
{
return memcmp(&lhs, &rhs, sizeof(GUID) < 0;
}

should do

S
Victor Bazarov
2009-11-19 21:42:14 UTC
Permalink
Raw Message
Post by Giovanni Dicanio
inline bool operator<( const GUID & lhs, const GUID & rhs )
{
return memcmp(&lhs, &rhs, sizeof(GUID) < 0;
}
should do
A closing paren is missing. :-)

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Wenwei Peng
2015-04-22 07:57:54 UTC
Permalink
Raw Message
在 2009年11月19日星期四 UTC+8下午9:27:17,Faisal写道:
Post by Faisal
I've a map which uses GUID as the key.
#include <map>
#include <string>
#include <unknwn.h>
void main()
{
std::map<GUID, std::string> map;
GUID d1;
std::string szName = "test";
map[d1] = szName;
}
But when compiling this code in VS2008 shows following errors
c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not
deduce template argument for 'const
std::basic_string<_Elem,_Traits,_Alloc> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(150) : see declaration of 'std::operator <'
1> c:\program files\microsoft visual studio 9.0\vc\include
\functional(142) : while compiling class template member function
'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const _Elem *,const
std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce
template argument for 'const _Elem *' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(140) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::basic_string<_Elem,_Traits,_Alloc> &,const
std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce
template argument for 'const std::basic_string<_Elem,_Traits,_Alloc>
&' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\string(130) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const std::_Tree<_Traits>
&,const std::_Tree<_Traits> &)' : could not deduce template argument
for 'const std::_Tree<_Traits> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include\xtree
(1466) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2>
&)' : could not deduce template argument for 'const
std::reverse_iterator<_RanIt> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\xutility(2262) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const
std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2>
&)' : could not deduce template argument for 'const
std::_Revranit<_RanIt,_Base> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\xutility(2072) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2>
&,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument
for 'const std::pair<_Ty1,_Ty2> &' from 'const GUID'
1> c:\program files\microsoft visual studio 9.0\vc\include
\utility(99) : see declaration of 'std::operator <'
1>c:\program files\microsoft visual studio 9.0\vc\include\functional
(143) : error C2676: binary '<' : 'const GUID' does not define this
operator or a conversion to a type acceptable to the predefined
operator
1
How can i solve this?
Title: The core of the core of the big data solutions -- Map
Author: pengwenwei
Email:
Language: c++
Platform: Windows, linux
Technology: Perfect hash algorithm
Level: Advanced
Description: Map algorithm with high performance
Section MFC c++ map stl
SubSection c++ algorithm
License: (GPLv3)

Download demo project - 1070 Kb
Download source - 1070 Kb

Introduction:
For the c++ program, map is used everywhere.And bottleneck of program performance is often the performance of map.Especially in the case of large data,and the business association closely and unable to realize the data distribution and parallel processing condition.So the performance of map becomes the key technology.

In the work experience with telecommunications industry and the information security industry, I was dealing with the big bottom data,especially the most complex information security industry data,all can’t do without map.

For example, IP table, MAC table, telephone number list, domain name resolution table, ID number table query, the Trojan horse virus characteristic code of cloud killing etc..

The map of STL library using binary chop, its has the worst performance.Google Hash map has the optimal performance and memory at present, but it has repeated collision probability.Now the big data rarely use a collision probability map,especially relating to fees, can’t be wrong.

Now I put my algorithms out here,there are three kinds of map,after the build is Hash map.We can test the comparison,my algorithm has the zero probability of collision,but its performance is also better than the hash algorithm, even its ordinary performance has no much difference with Google.

My algorithm is perfect hash algorithm,its key index and the principle of compression algorithm is out of the ordinary,the most important is a completely different structure,so the key index compression is fundamentally different.The most direct benefit for program is that for the original map need ten servers for solutions but now I only need one server.
Declare: the code can not be used for commercial purposes, if for commercial applications,you can contact me with QQ 75293192.
Download:
https://sourceforge.net/projects/pwwhashmap/files

Applications:
First,modern warfare can’t be without the mass of information query, if the query of enemy target information slows down a second, it could lead to the delaying fighter, leading to failure of the entire war. Information retrieval is inseparable from the map, if military products use pwwhashMap instead of the traditional map,you must be the winner.

Scond,the performance of the router determines the surfing speed, just replace open source router code map for pwwHashMap, its speed can increase ten times.
There are many tables to query and set in the router DHCP ptotocol,such as IP,Mac ,and all these are completed by map.But until now,all map are using STL liabrary,its performance is very low,and using the Hash map has error probability,so it can only use multi router packet dispersion treatment.If using pwwHashMap, you can save at least ten sets of equipment.

Third,Hadoop is recognized as the big data solutions at present,and its most fundamental thing is super heavy use of the map,instead of SQL and table.Hadoop assumes the huge amounts of data so that the data is completely unable to move, people must carry on the data analysis in the local.But as long as the open source Hadoop code of the map changes into pwwHashMap, the performance will increase hundredfold without any problems.


Background to this article that may be useful such as an introduction to the basic ideas presented:
http://blog.csdn.net/chixinmuzi/article/details/1727195

Loading...