Use of CString key in CMap

[Kjell Arne Johansen]

Hi

I have a question about the use of CString as a key in a CMap. Is that okay?
I want to get an object using a string name. Is that okay or will I
sometime get the wrong object because the haskey could be the same for two
different strings?

CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;

This hash key I found in CodeGuru, but I am not able to see if it is a good
has key.

template<>
inline UINT AFXAPI HashKey<CString&> (CString& strKey)
{
LPCSTR key = strKey;
UINT nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return nHash;
}

Does anyone have knowledge about this?

Regards Kjell Arne Johansen

[David Ching]

Post by Kjell Arne Johansen
Hi
I have a question about the use of CString as a key in a CMap. Is that okay?
I want to get an object using a string name. Is that okay or will I
sometime get the wrong object because the haskey could be the same for two
different strings?
CMap<CString, CString &, csomecobject, csomecobject &> m_map
csomecobject;
This hash key I found in CodeGuru, but I am not able to see if it is a good
has key.

I would use CMapStringToObj as-is, without worrying about the hash function.
WIth maps, it is assumed there are unique keys for each object. The map can
contain only one instance of each key, so if you were to:

CMapStringToOb map;
map["geneva"] = switzerlandObject;
map["geneva"] = alpsObject;

then switzerlandObject would no longer be in the map, having been replaced
with alpsObject.

The hash function is an internal implementation to the map, it enables using
a fixed size container such as an array of linked lists to put the objects
into. The hash function then would determine which element of the array
would hold each object (the object would in that element's linked list).

But the hash function does not allow multiple instances of the same key to
be put into the map.

-- David

[Giovanni Dicanio]

Post by David Ching
CMapStringToOb map;
map["geneva"] = switzerlandObject;
map["geneva"] = alpsObject;

I'm sure that David meant map[ _T("geneva") ] here.

It is important to put the _T() "decorator" (but I would define it a kind of
"uglyfier"...) so in Unicode builds the string literal is actually converted
to Unicode UTF-16 string literal L"geneva".

G

[Giovanni Dicanio]

Post by David Ching
CMapStringToOb map;
map["geneva"] =

Moreover, I was just realizing that that code could also compile in Unicode
builds, because CString has *implicit* (conversion) constructors from char*
to wchar_t*... However, I would prefer a L"geneva" string literal (using
_T() preprocessor expansion), instead of run-time penalty to convert from
char* to wchar_t*.

Giovanni

[Kjell Arne Johansen]

Hi

Thank you for your answer.
As I understand it a good haskey will make lookup very fast, maybe dependent
of the string keys?

If they string keys are very much the same e.g. _T("abc1"), _T("abc2"),
_T("abc3") lookup will take longer time than if the string keys were totaly
different?

Another question regading string keys and mfc supported maps:
What if I want to map string to int?
E.g.
CMap<CString, CString &, int, int&> m_map;

I also have a case where I need to lookup an int number using a string key.
I have tried it using the current haskey.
Is that okay?
I could not find any mfc mapstringtoint.

Regards Kjell Arne Johansen

Post by David Ching

Post by Kjell Arne Johansen
Hi
I have a question about the use of CString as a key in a CMap. Is that okay?
I want to get an object using a string name. Is that okay or will I
sometime get the wrong object because the haskey could be the same for two
different strings?
CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;
This hash key I found in CodeGuru, but I am not able to see if it is a good
has key.

I would use CMapStringToObj as-is, without worrying about the hash function.
WIth maps, it is assumed there are unique keys for each object. The map can
CMapStringToOb map;
map["geneva"] = switzerlandObject;
map["geneva"] = alpsObject;
then switzerlandObject would no longer be in the map, having been replaced
with alpsObject.
The hash function is an internal implementation to the map, it enables using
a fixed size container such as an array of linked lists to put the objects
into. The hash function then would determine which element of the array
would hold each object (the object would in that element's linked list).
But the hash function does not allow multiple instances of the same key to
be put into the map.
-- David

[David Ching]

Post by Kjell Arne Johansen
Hi
Thank you for your answer.
As I understand it a good haskey will make lookup very fast, maybe dependent
of the string keys?
If they string keys are very much the same e.g. _T("abc1"), _T("abc2"),
_T("abc3") lookup will take longer time than if the string keys were totaly
different?

Yes, the hash function is responsible for selecting e.g. which element of
the array to store the object into. Ideally for the set of keys you are
storing, the hash function will pick each element the same number of times
so that each element has the same number of objects saved in it. This
minimizes the average lookup time since the number of items to check in any
element is as small as possible.

Generally, the hash function does well about distributing similar strings as
per your example, e.g. "abc1" and "abc2" and "abc3" will probably all go to
different elements and be ideal. But I'm not sure if any of the MFC maps
will let you optimize the hash function.

Post by Kjell Arne Johansen
What if I want to map string to int?
E.g.
CMap<CString, CString &, int, int&> m_map;
I also have a case where I need to lookup an int number using a string key.
I have tried it using the current haskey.
Is that okay?
I could not find any mfc mapstringtoint.

No, there is no pre-built specialized class mapping a string to an int.
You'd use templates as you have done. But again, don't worry about the hash
function. You're optimizing something that you can assume does not need
optimizing unless you have concrete proof it is causing visible performance
impact. I've never had this be the case.

-- David

[Giovanni Dicanio]

Post by Kjell Arne Johansen
I have a question about the use of CString as a key in a CMap. Is that okay?

To add to David's correct answer of using CMapStringToOb, I would also
suggest to use std::map.

One of the reasons I like std::map better than CMap is that you don't need
to provide a custom hash-key generator for std::map (or, at least, I never
had to do that). Instead, it seems that you must provide that with CMap (at
least for CString key...).

Moreover, with std::map you can have type-safety (because you can specify
the exact template value type T), instead with CMapStringToOb the "value"
type (in "key -> value" association) is a CObject *, so you kind of loose
type safety (or at least, it is not as robust and strict as in std::map).

Moreover, if you compare std::map and CMap definitions, you can note how
std::map is simpler (you just need to specify two template types: the key
type and value type - you can specify also other details, like compare
function and allocator, but default ones are also provided):

// std::map< Key, Value >
// (default compare function and allocator used)
std::map< CString, CSomeObject > m_map;

// CMap
// (You must specify 4 types...)
CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;

Giovanni

[Kjell Arne Johansen]

Thank you very much for your answer.

I have always used the mfc stuff. Maybe it is time to try something else.
I also need look up a in number from string key.
E.g.
CMap<CString, CString &, int, int&> m_map.

I assume that can be done with std::map?


Regards Kjell Arne Johansen

Post by Giovanni Dicanio

Post by Kjell Arne Johansen
I have a question about the use of CString as a key in a CMap. Is that okay?

To add to David's correct answer of using CMapStringToOb, I would also
suggest to use std::map.
One of the reasons I like std::map better than CMap is that you don't need
to provide a custom hash-key generator for std::map (or, at least, I never
had to do that). Instead, it seems that you must provide that with CMap (at
least for CString key...).
Moreover, with std::map you can have type-safety (because you can specify
the exact template value type T), instead with CMapStringToOb the "value"
type (in "key -> value" association) is a CObject *, so you kind of loose
type safety (or at least, it is not as robust and strict as in std::map).
Moreover, if you compare std::map and CMap definitions, you can note how
std::map is simpler (you just need to specify two template types: the key
type and value type - you can specify also other details, like compare
// std::map< Key, Value >
// (default compare function and allocator used)
std::map< CString, CSomeObject > m_map;
// CMap
// (You must specify 4 types...)
CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;
Giovanni

[Giovanni Dicanio]

Post by Kjell Arne Johansen
Thank you very much for your answer.

You're welcome.

Post by Kjell Arne Johansen
I have always used the mfc stuff. Maybe it is time to try something else.

IMHO, STL containers like std::vector and std::map are better designed than
MFC ones.
The very good thing is that STL containers play very well with MFC classes
(for example, I prefer MFC CString instead of std::string/wstring, and you
can put MFC CString into STL containers).

Post by Kjell Arne Johansen
I also need look up a in number from string key.
E.g.
CMap<CString, CString &, int, int&> m_map.
I assume that can be done with std::map?

Of course.
e.g.:

<code>

typedef std::map< CString, int > MapStringToInt;

MapStringToInt map;

map[ _T("Bob") ] = 10;
map[ _T("Sue") ] = 22;

</code>

Giovanni

[Kjell Arne Johansen]

Thank you very much, I will give it a try.

Regards Kjell Arne Johansen

Post by Giovanni Dicanio

Post by Kjell Arne Johansen
Thank you very much for your answer.

You're welcome.

Post by Kjell Arne Johansen
I have always used the mfc stuff. Maybe it is time to try something else.

IMHO, STL containers like std::vector and std::map are better designed than
MFC ones.
The very good thing is that STL containers play very well with MFC classes
(for example, I prefer MFC CString instead of std::string/wstring, and you
can put MFC CString into STL containers).

Post by Kjell Arne Johansen
I also need look up a in number from string key.
E.g.
CMap<CString, CString &, int, int&> m_map.
I assume that can be done with std::map?

Of course.
<code>
typedef std::map< CString, int > MapStringToInt;
MapStringToInt map;
map[ _T("Bob") ] = 10;
map[ _T("Sue") ] = 22;
</code>
Giovanni

[David Wilkinson]

Post by Kjell Arne Johansen
Thank you very much for your answer.
I have always used the mfc stuff. Maybe it is time to try something else.
I also need look up a in number from string key.
E.g.
CMap<CString, CString &, int, int&> m_map.
I assume that can be done with std::map?

Kjell:

std::map<CString, int> m_map;

corresponds to

CMap<CString, const CString &, int, const int&> m_map;

Note that in recent MFC versions, CArray and CList have use a defaulted second
template parameter, but it is not possible to default the second and fourth
template parameters in CMap.

No hash function is needed for std::map, because it relies on ordering of the
keys, not hashing. I think hash_map may be in future versions of the C++
standard, but the original STL did not have it.

[Kjell Arne Johansen]

Thank you very much for your kind help.

Regards Kjell Arne Johansen

Post by David Wilkinson

Post by Kjell Arne Johansen
Thank you very much for your answer.
I have always used the mfc stuff. Maybe it is time to try something else.
I also need look up a in number from string key.
E.g.
CMap<CString, CString &, int, int&> m_map.
I assume that can be done with std::map?

std::map<CString, int> m_map;
corresponds to
CMap<CString, const CString &, int, const int&> m_map;
Note that in recent MFC versions, CArray and CList have use a defaulted second
template parameter, but it is not possible to default the second and fourth
template parameters in CMap.
No hash function is needed for std::map, because it relies on ordering of the
keys, not hashing. I think hash_map may be in future versions of the C++
standard, but the original STL did not have it.
--
David Wilkinson
Visual C++ MVP

[David Ching]

Post by Giovanni Dicanio
One of the reasons I like std::map better than CMap is that you don't need
to provide a custom hash-key generator for std::map (or, at least, I never
had to do that). Instead, it seems that you must provide that with CMap
(at least for CString key...).

I'm not sure what you mean. You don't have to provide a "custom hash-key
generator" for CMap, and I'm not sure how to do that if it is even possible.

Post by Giovanni Dicanio
Moreover, with std::map you can have type-safety (because you can specify
the exact template value type T), instead with CMapStringToOb the "value"
type (in "key -> value" association) is a CObject *, so you kind of loose
type safety (or at least, it is not as robust and strict as in std::map).

This is true, however, using templates you could just as well say:

CMap<CString, CString &, CMyClass, CMyClass &> m_map;

and this has the additional advantage that CMyClass does not need to derive
from CObject.

Post by Giovanni Dicanio
Moreover, if you compare std::map and CMap definitions, you can note how
std::map is simpler (you just need to specify two template types: the key
type and value type - you can specify also other details, like compare
// std::map< Key, Value >
// (default compare function and allocator used)
std::map< CString, CSomeObject > m_map;
// CMap
// (You must specify 4 types...)
CMap<CString, CString &, csomecobject, csomecobject &> m_map
csomecobject;

This is true, but siince the 2nd and 4th parameters are simply reference
types of the 1st and 3rd parameters, it's not as if it causes much brain
power to figure these out. OTOH, making sense out of STL causes significant
brain power....

-- David

[Giovanni Dicanio]

Post by David Ching
I'm not sure what you mean.

Hi David,

I'm sorry if I wrote my ideas badly.

I would like to give you a C++ sample code:

<code>

// CMap
CMap< CString, const CString &, CString, const CString & > map1;
map1[ _T("Seattle") ] = _T("Washington");
map1[ _T("Napoli") ] = _T("Campania");

// std::map
std::map< CString, CString > map2;
map2[ _T("Seattle") ] = _T("Washington");
map2[ _T("Napoli") ] = _T("Campania");

</code>

This code does not compile under Visual C++ 9 (VS2008).

I get the following error:

error C2440: 'type cast' :
cannot convert from 'const CString' to 'DWORD_PTR'
j:\programmi\microsoft visual studio 9.0\vc\atlmfc\include\afxtempl.h 163

The error points in this template function in afxtempl.h:

<code>

template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
// default identity hash - works for most primitive values
return (DWORD)(((DWORD_PTR)key)>>4);
}

</code>

If I comment out the CMap version (where the problem is), the STL std::map
version compiles fine.

What should I do to use CMap *generic template* with CString?
Why doesn't it work simply, just like std::map?

Post by David Ching
CMap<CString, CString &, CMyClass, CMyClass &> m_map;
and this has the additional advantage that CMyClass does not need to
derive from CObject.

You are right about using CMap generic template.
But my problem is that it seems that it does not compile with CString key...

Or am I missing something?

Post by David Ching

Post by Giovanni Dicanio
// CMap
// (You must specify 4 types...)
CMap<CString, CString &, csomecobject, csomecobject &> m_map
csomecobject;

This is true, but siince the 2nd and 4th parameters are simply reference
types of the 1st and 3rd parameters, it's not as if it causes much brain
power to figure these out. OTOH, making sense out of STL causes
significant brain power....

You are right that 2nd and 4th parameters are simply reference types, so no
big brain power is required, but I don't like that: I mean: why add this
complexity of 2nd and 4th parameter types? It seems to me useless
complexity...

For STL, I believe that you can master that library better than me!
Moreover, you don't need to master *all* STL (I don't master all of it, of
course), you can just use some useful containers like vector or map...

However, I'm not in a position to "teach" anything to anyone :)
Mine are just simple advices, just IMHO.

I think that every programmer should use what he/she is familiar with and
likes.

G

[David Ching]

Post by Giovanni Dicanio
Hi David,
I'm sorry if I wrote my ideas badly.
<code>
// CMap
CMap< CString, const CString &, CString, const CString & > map1;
map1[ _T("Seattle") ] = _T("Washington");
map1[ _T("Napoli") ] = _T("Campania");
// std::map
std::map< CString, CString > map2;
map2[ _T("Seattle") ] = _T("Washington");
map2[ _T("Napoli") ] = _T("Campania");
</code>
This code does not compile under Visual C++ 9 (VS2008).
cannot convert from 'const CString' to 'DWORD_PTR'
j:\programmi\microsoft visual studio 9.0\vc\atlmfc\include\afxtempl.h 163
<code>
template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
// default identity hash - works for most primitive values
return (DWORD)(((DWORD_PTR)key)>>4);
}
</code>
If I comment out the CMap version (where the problem is), the STL std::map
version compiles fine.
What should I do to use CMap *generic template* with CString?
Why doesn't it work simply, just like std::map?

I think you've exposed a limitation of the MFC maps. Apparently the key
type must be a type that can be converted to a DWORD_PTR (which is a 32-bit
DWORD on 32-bit Windows and a 64-bit value on 64-). So unless the type has
a conversion operator producing the DWORD_PTR, it can't be a key. CString
can't convert to a DWORD_PTR.

I did workaround this problem by declaring

CMap<LPCTSTR, LPCTSTR, CString, CString&> map1;


It's interesting that trying to follow the pattern of making the 2nd
parameter a reference, i.e..

CMap<LPCTSTR, LPCTSTR&, CString, CString&> map1;

resulted in a compiler error. I'm not sure what we give up by not making
the 2nd parameter a reference.

MFC does have a built in class CMapStringToString, but if you look at the
source code, it doesn't rely on templates at all, and both the key and value
are of type LPCTSTR and not CString!

This excellent CodeProject article offers a lot more detail:
http://www.codeproject.com/KB/architecture/cmap_howto.aspx


Cheers,
David

[Giovanni Dicanio]

Post by David Ching
http://www.codeproject.com/KB/architecture/cmap_howto.aspx

Thanks for your detailed post and for the article link.

Cheers,
G

[David Wilkinson]

Post by David Ching
I think you've exposed a limitation of the MFC maps. Apparently the key
type must be a type that can be converted to a DWORD_PTR (which is a 32-bit
DWORD on 32-bit Windows and a 64-bit value on 64-). So unless the type has
a conversion operator producing the DWORD_PTR, it can't be a key. CString
can't convert to a DWORD_PTR.
I did workaround this problem by declaring
CMap<LPCTSTR, LPCTSTR, CString, CString&> map1;
It's interesting that trying to follow the pattern of making the 2nd
parameter a reference, i.e..
CMap<LPCTSTR, LPCTSTR&, CString, CString&> map1;
resulted in a compiler error. I'm not sure what we give up by not making
the 2nd parameter a reference.
MFC does have a built in class CMapStringToString, but if you look at the
source code, it doesn't rely on templates at all, and both the key and value
are of type LPCTSTR and not CString!
http://www.codeproject.com/KB/architecture/cmap_howto.aspx

David:

This may be a good article, but for me it simply illustrates how much easier
std::map is to use than CMap. And I still don't understand the purpose of the
duplicated template arguments.

std::map<CString, int> just works. No muss, no fuss. With an MFC class as the
key, even.

Actually, I think the "correct" type for the second and fourth template
parameter in CMap is "const reference" (this is the default type of the second
parameter in recent versions of CArray and CList). It seems that

CMap<LPCTSTR, const LPCTSTR&, CString, const CString&> stringMap;

is allowed. [I didn't test it, but it compiles.]

CMap<CString, const CString&, CString, const CString&> stringMap;

will also work, but you have to provide your own hash function. You would think
that if MFC had provided a hash specializations for LPCTSTR, they would have
done it for CString also...

[David Ching]

Post by David Wilkinson
This may be a good article, but for me it simply illustrates how much
easier std::map is to use than CMap. And I still don't understand the
purpose of the duplicated template arguments.
std::map<CString, int> just works. No muss, no fuss. With an MFC class as
the key, even.

For me, It just seems the MFC classes follow the spirit of how these
collections are supposed to work... I mean, a map is another name for a
dictionary. CMap::Lookup() tells you whether your query is successful or
not instead of stupidly manufacturing a default object if you reference one
that is not there. What Webster's dictionary do you know that if you look
up a word that isn't in there, it creates an empty one on the fly,
corrupting your nice dictionary?

I think STL also has some API's specifically like Lookup() but for me I
could not even figure out how to use them when I first looked at the public
functions. You had to tell me! :-O Not to mention that STL code is truly
ugly and not very readable. Oh well, what's intuitve to someone is not for
others. I will say that thankfully the .NET collections share the same
spirt of the MFC collections, and these are truly easy to use and seem to
have the benefit of STL (things like nesting, etc.).

Post by David Wilkinson
Actually, I think the "correct" type for the second and fourth template
parameter in CMap is "const reference" (this is the default type of the
second parameter in recent versions of CArray and CList). It seems that
CMap<LPCTSTR, const LPCTSTR&, CString, const CString&> stringMap;
is allowed. [I didn't test it, but it compiles.]
CMap<CString, const CString&, CString, const CString&> stringMap;
will also work, but you have to provide your own hash function. You would
think that if MFC had provided a hash specializations for LPCTSTR, they
would have done it for CString also...

The CodeProject article said the 2nd and 4th arguments were used throughout
the implementation, but really the true arguments were the 1st and 3rd ones.
I'm not sure the history of this. Perhaps the reason why MFC has pre-made
CStringTo<many things> classes is due to there is no easy way to generate a
HashKey from the object.

Thanks,
David

[Giovanni Dicanio]

I will say that thankfully the .NET collections share the same spirt of
the MFC collections, and these are truly easy to use and seem to have the
benefit of STL (things like nesting, etc.).

The .NET collections are the best ones.
They take the good things of both worlds (MFC and STL): e.g. they take the
high-readability of MFC collections with high-composibility of STL
collections.

Moreover, it seems that in a .NET collection you can put everything, instead
e.g. in a STL collection you can't put COM objects (pointers), instead you
must use CAdapt as an intermediate adapter...

Giovanni

[David Wilkinson]

Post by David Ching

Post by David Wilkinson
This may be a good article, but for me it simply illustrates how much
easier std::map is to use than CMap. And I still don't understand the
purpose of the duplicated template arguments.
std::map<CString, int> just works. No muss, no fuss. With an MFC class as
the key, even.

For me, It just seems the MFC classes follow the spirit of how these
collections are supposed to work... I mean, a map is another name for a
dictionary. CMap::Lookup() tells you whether your query is successful or
not instead of stupidly manufacturing a default object if you reference one
that is not there. What Webster's dictionary do you know that if you look
up a word that isn't in there, it creates an empty one on the fly,
corrupting your nice dictionary?

David:

AFAICT, operator [] has the same behavior in std::map and CMap.

The CMap documentation says that it "cannot" be used as an r-value, which is
nonsense. What they mean is, it "should not" be used as an r-value if you do not
want a default value inserted if the key is not found.

std::map::find() is like CMap::Plookup(). The former returns an iterator, while
the latter returns a pointer. Same thing, conceptually. Dereferencing either
gives an element of the map, which is a pair in both cases.

There is no analog of CMap::Lookup() in std::map; you have to test the result of
find(). No big deal.

[David Ching]

Post by David Wilkinson
AFAICT, operator [] has the same behavior in std::map and CMap.
The CMap documentation says that it "cannot" be used as an r-value, which
is nonsense. What they mean is, it "should not" be used as an r-value if
you do not want a default value inserted if the key is not found.

It's not nonsense. Instead of e.g.

if ( m_map[_T("geneva")] ) // inserts default "geneva" object

just do:

CString strGeneva;
if ( m_map.Lookup(_T("geneva"), strGeneva) ) // returns true if it
exists


I don't know of any uses when I desire a default value to be manufactured.
Ever. Like I said, a standard $1 dictionary doesn't do it, and I don't want
something supposedly modelling a dictionary to do it.

Post by David Wilkinson
std::map::find() is like CMap::Plookup(). The former returns an iterator,
while the latter returns a pointer. Same thing, conceptually.
Dereferencing either gives an element of the map, which is a pair in both
cases.
There is no analog of CMap::Lookup() in std::map; you have to test the
result of find(). No big deal.

Well, perhaps that's why I don't like STL. Iterators are especially
unreadable, and I don't want to deal with them just to lookup something in
my map.

Thanks,
David

[David Wilkinson]

Post by David Ching

Post by David Wilkinson
The CMap documentation says that it "cannot" be used as an r-value, which
is nonsense. What they mean is, it "should not" be used as an r-value if
you do not want a default value inserted if the key is not found.

It's not nonsense. Instead of e.g.
if ( m_map[_T("geneva")] ) // inserts default "geneva" object
CString strGeneva;
if ( m_map.Lookup(_T("geneva"), strGeneva) ) // returns true if it
exists
I don't know of any uses when I desire a default value to be manufactured.
Ever. Like I said, a standard $1 dictionary doesn't do it, and I don't want
something supposedly modelling a dictionary to do it.

David:

But CMap and std::map are no different in this regard. They both add a default
object. The code

if ( m_map[_T("geneva")] )
{
}

is not the right way to test if "geneva" is in the map in either CMap or
std::map. In std::map you should use the find() method (which is similar to
PLookup()).

[David Ching]

Post by David Wilkinson
But CMap and std::map are no different in this regard. They both add a
default object. The code
if ( m_map[_T("geneva")] )
{
}
is not the right way to test if "geneva" is in the map in either CMap or
std::map. In std::map you should use the find() method (which is similar
to PLookup()).

Right, so we agree it's not nonsense? I object to std::map::find()
returning an iterator; it's not as clean as a simple bool.

STL does the job, but really, the only people that seem to like it are cross
platform people. Dedicated Windows programmers think differently, in
general. Or maybe that's just me.

-- David

[Giovanni Dicanio]

I object to std::map::find() returning an iterator; it's not as clean as a
simple bool.

I agree with you about std::map::find.

I would prefer code like:

if ( ! myMap.find( key ) )
...

instead of :

if ( myMap.find( key ) == myMap::end )
...
... iterator == map::end
... means: "no element found"

The find-returning-boolean is more intuitive and clearer to read.

I recall that I wrote a simple custom template "map" class (calling it
Dictionary) just wrapping std::map, and using coding conventions like
PascalCasing (that I prefer to underscore_casing ) and I added some methods
like a substitute for "find", returning a bool (I called it ContainsKey).
The implementation is trivial, of course (just kind of a little wrapper to
some of std::map methods), but it helped me building code of a quality I
prefer.

STL does the job, but really, the only people that seem to like it are
cross platform people. Dedicated Windows programmers think differently,
in general. Or maybe that's just me.

For me, the very good point of STL is its container composibility. e.g. you
can build maps storing string-arrays or other objects, and it all works well
in STL. And STL containers work well also with "external" classes like
CString (which is not part of STL). From this particular point of view, STL
seems to me very well designed, IMHO.

Moreoever, the iterators help you to strongly decouple the containers and
the algorithms, i.e. thanks to the iterators, you can implement (or use)
some generic algorithms, without knowing the details of the container type
storing the data. It's kind of programming towards an "interface" instead of
a "concrete" class.

However, some STL things could be made better, like your good point about
std::map::find (...and frankly speaking I don't like the
stl_naming_convention with underscores... but it's just my personal coding
"tastes" :)

Cheers,
G

[David Wilkinson]

Post by David Ching
Right, so we agree it's not nonsense? I object to std::map::find()
returning an iterator; it's not as clean as a simple bool.
STL does the job, but really, the only people that seem to like it are cross
platform people. Dedicated Windows programmers think differently, in
general. Or maybe that's just me.

David:

What I think is nonsense is the CMap documentation on operator []:

"Thus it can be used only on the left side of an assignment statement (an
l-value). If there is no map element with the specified key, then a new element
is created.

There is no "right side" (r-value) equivalent to this operator because there is
a possibility that a key may not be found in the map. Use the Lookup member
function for element retrieval."

This implies to me that using operator [] as an r-value would give a compiler
error, which of course it does not (and can not). Rather, if the key is not
found, it adds an entry to the map (just like std::map does).

[David Ching]

Post by David Wilkinson
"Thus it can be used only on the left side of an assignment statement (an
l-value). If there is no map element with the specified key, then a new
element is created.
There is no "right side" (r-value) equivalent to this operator because
there is a possibility that a key may not be found in the map. Use the
Lookup member function for element retrieval."
This implies to me that using operator [] as an r-value would give a
compiler error, which of course it does not (and can not). Rather, if the
key is not found, it adds an entry to the map (just like std::map does).

Well, we've already agreed the behavior of CMap and std::map are the same
when used as an r-value. The difference is Microsoft wisely understood that
most people consider adding a default value to the map is an abomination and
tells you up front and center how to avoid this unwanted behavior. So it
seems like we're disagreeing on documentation.

-- David

[David Wilkinson]

Post by David Ching

Post by David Wilkinson
"Thus it can be used only on the left side of an assignment statement (an
l-value). If there is no map element with the specified key, then a new
element is created.
There is no "right side" (r-value) equivalent to this operator because
there is a possibility that a key may not be found in the map. Use the
Lookup member function for element retrieval."
This implies to me that using operator [] as an r-value would give a
compiler error, which of course it does not (and can not). Rather, if the
key is not found, it adds an entry to the map (just like std::map does).

Well, we've already agreed the behavior of CMap and std::map are the same
when used as an r-value. The difference is Microsoft wisely understood that
most people consider adding a default value to the map is an abomination and
tells you up front and center how to avoid this unwanted behavior. So it
seems like we're disagreeing on documentation.

David:

My problem with the documentation is that it says that you *cannot* use operator
[] as an r-value.

In fact, if you *know* that the key is in the map (as is often the case), then
operator [] is a fine way to retrieve values.

That's all.

[The things that I *really" dislike about the MFC collection classes are that
they are non-copyable, and the unnecessary confusion caused by the doubling of
the template arguments...]

[David Ching]

Post by David Wilkinson
My problem with the documentation is that it says that you *cannot* use
operator [] as an r-value.
In fact, if you *know* that the key is in the map (as is often the case),
then operator [] is a fine way to retrieve values.
That's all.
[The things that I *really" dislike about the MFC collection classes are
that they are non-copyable, and the unnecessary confusion caused by the
doubling of the template arguments...]

Fair enough. Everyone has different "hot buttons". :-) For example, I
have never had to copy a collection, and typing in 2 extra parameters don't
bother me much.

Cheers,
David

[Wenwei Peng]

在 2008年4月4日星期五 UTC+8下午2:31:00，Kjell Arne Johansen写道：

Post by Kjell Arne Johansen
Hi
I have a question about the use of CString as a key in a CMap. Is that okay?
I want to get an object using a string name. Is that okay or will I
sometime get the wrong object because the haskey could be the same for two
different strings?
CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;
This hash key I found in CodeGuru, but I am not able to see if it is a good
has key.
template<>
inline UINT AFXAPI HashKey<CString&> (CString& strKey)
{
LPCSTR key = strKey;
UINT nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return nHash;
}
Does anyone have knowledge about this?
Regards Kjell Arne Johansen

Title: The core of the core of the big data solutions -- Map
Author: pengwenwei
Email: wenwei19710430
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

[Wenwei Peng]

在 2008年4月4日星期五 UTC+8下午2:31:00，Kjell Arne Johansen写道：

Post by Kjell Arne Johansen
Hi
I have a question about the use of CString as a key in a CMap. Is that okay?
I want to get an object using a string name. Is that okay or will I
sometime get the wrong object because the haskey could be the same for two
different strings?
CMap<CString, CString &, csomecobject, csomecobject &> m_map csomecobject;
This hash key I found in CodeGuru, but I am not able to see if it is a good
has key.
template<>
inline UINT AFXAPI HashKey<CString&> (CString& strKey)
{
LPCSTR key = strKey;
UINT nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return nHash;
}
Does anyone have knowledge about this?
Regards Kjell Arne Johansen

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