Thread: strange std::map behavior

Originally Posted by manav

thanks laser!
that utility function deserves to be in my toolbox!

Yes, but beware that if you then use either find or [], you _WILL_ perform another search for the key - which is a waste of useful processing power.

--
Mats

Originally Posted by laserlight

But you see, if you want to do what manav wants to do (print the element corresponding to a key, as per the Python example), has_key() is a complete waste of time. You would just write something along these lines:

Code:

std::map<K,V>::iterator iter = map.find(key);
if (iter != map.end())
{
    std::cout << iter->second << std::endl;
}
else
{
    std::cout << "No such key: " << key << std::endl;
}

If you write:

Code:

if (map.has_key(key))
{
    std::cout << map[key] << std::endl;
}
else
{
    std::cout << "No such key: " << key << std::endl;
}

... you would be finding the key twice, assuming the key exists.


There is nothing wrong with extending std::map by providing free functions that extend its interface, or by wrapping it in another class. However, you should not inherit from std::map since it was not designed to be a base class and thus its destructor is non-virtual.


A working example would be:

Code:

template<typename K, typename V>
bool has_key(const std::map<K,V>& map, const K& key)
{
    return map.find(key) != map.end();
}

Yes, unfortunately, the usability ends there. But as the name suggests, it looks if the key exists, but does not return it.
If you wanted it returned, I would find it easier to check like

Code:

std::map<K,V>::iterator iter = map.find(key);
if (iter)
{
    std::cout << iter->second << std::endl;
}
else
{
    std::cout << "No such key: " << key << std::endl;
}

Just like a pointer.

Originally Posted by matsp

Stupid typo (copy'n'paste, actually):

Code:

bool has_key(std::map<...> m, KEYTYPE key)
{
   return m.find(key) != m.end();
}

--
Mats

I'm dead against this kind of encapsulation. has_key is supposed to be a member function of std::map instead, not broken into bits outside.

Actually, I think there's a limitation: suppose you have a std::map<std::string, std::size_t>, as per my word count example. If you try a has_key(map, "word"), the code will not compile since the string literal's type does not match the map's key type.

One solution is to change the call to has_key(map, std::string("word")). A possibly better solution is to change the function template to:

Code:

template<typename T>
bool has_key(const T& map, const typename T::key_type& key)
{
    return map.find(key) != map.end();
}

EDIT:

I'm dead against this kind of encapsulation. has_key is supposed to be a member function of std::map instead, not broken into bits outside.

This is the same thing as discussed in the "std::string is a monolithic type" article by Sutter. has_key() can be implemented as a non-member non-friend.

Originally Posted by Elysia

Just like a pointer.

Are you sure that there is no need to compare the iterator to map.end(), i.e., the one past the end iterator is guaranteed to evaluate to false?

Originally Posted by manav

I think it would not be that case if the has_key() was a member function working with internals directly! Alas!

No, turning it into a member function would make no difference in terms of efficiency. The problem is simply that the iterator to the element is discarded.

Originally Posted by manav

Really Mats?
Offo! That just increases my pain over lack of implementations in std stuff!
I think it would not be that case if the has_key() was a member function working with internals directly! Alas!

No, whether you implement has_key as a direct function in the class implementation or you do it as a external function, it will have to search for that key. [] or find will ALSO have to search for that key - the only way to avoid that would be to cache the searches inside the class, which would only help if you often do things like the above example of

Code:

if(m.has_key(key)) ... m[key] ...

The point being that if you use find() correctly, then you do NOT need to search twice, because you use the original find result to determine if the data is there or not.

I may not be a template (or map) demon, but I do understand that the key would have to be searched for each of those cases.

--
Mats

Originally Posted by laserlight

This is the same thing as discussed in the "std::string is a monolithic type" article by Sutter. has_key() can be implemented as a non-member non-friend.

Well, as I said, I don't like it. It may be good, it may have advantages, but I'm not forced to like it. My philosophy is that if it's part of the object, then it's a member function, end of story. Other views differ, of course, this is just my own view.

Originally Posted by laserlight

Are you sure that there is no need to compare the iterator to map.end(), i.e., the one past the end iterator is guaranteed to evaluate to false?

I don't know, but the optimal implementation in my eyes, is that if operator bool returns true, it guarantees that the iterator is valid and if false, then invalid.

I don't see why you think std classes so lacking.

In Python you might write something like this:

Code:

try:
    print map[key]
except KeyError:
    print "No such key"

In C++ that would be:

Code:

map<A, B>::iterator it = map.find(key);
if (it != map.end())
     cout << it->second << '\n';
else
     cout << "No such key\n";

The main difference is that in C++ you normally check before jumping, and in Python it is OK to jump first and then handle the consequences (you could check first but that would mean the dictionary is searched twice).
The C++ code also requires a bit more typing (the iterator declarator could be shortened with a typedef - and the auto keyword in the next standard would make it more convenient), but the basic structure is still quite the same.

speak about has_key() efficiency, even java has the function, and also another one:

containsKey(Object key), containsValue(Object value)

C++ people are sick with efficiency concerns, no doubt, since they are from the older days of scarce resources!
modern technologies, alas, when will C++ people awake!
the standard itself is 10 years old now!

anon: not too much trouble, if, c++ people could just think about it like this:

Code:

put(key, val);
get(key,defval=...);

even java has the function

Apples to oranges. Java doesn't have free functions, so they're not an alternative.

modern technologies, alas, when will C++ people awake!

Bla, bla, bla.

the standard itself is 10 years old now!

That's why a new one is in development.

Originally Posted by manav

speak about has_key() efficiency, even java has the function, and also another one:

C++ people are sick with efficiency concerns, no doubt, since they are from the older days of scarce resources!
modern technologies, alas, when will C++ people awake!

I personally am not forcing you to use C++. I presume that if you work for a company for example that they may take an interest in what language you use.

But strictly speaking, efficiency is one reason to use C++ - if you don't care about it, that's another matter. Providing functions that promote efficient use of the underlaying data structures make sense, however.

Yes, modern hardware has lots of memory and lots of clockcycles per second (at least in a PC), which allows the use of "slower" coding practices when that's suitable. Fine - that doesn't mean that C++ should be changed to be slow always, does it?

--
Mats

Originally Posted by manav

i am already *forced* to use C++ by my project!


that's not what i meant. don't make the stuff slower deliberately. i just meant that java, by design, is slow language.
hashing, by principle, i think, needs a lot of processor time. if interpreted (by design, there are improvements, but C++ is still more close to processor) java can bear a little in-efficiency, then why can't this be done in super fast (actually fastest possible OO language) language C++.

Hashing a string shouldn't be terribly inefficient - obviously if the string is VERY LONG, then it will be, but in essence it's (most often) just a combination of 32-bit shift and xor operations, and then a truncation to the size of the hash-table.

Java is inefficient because it's an interpreted (through the byte-code form) language, more than because the classes that are implemented in it are inefficient. Properly compiled (to native machine language) Java should be only marginally slower than C++ (commonly because of language structure/implementation differences - e.g. Java has only virtual functions, C++ allows for non-virtual when the programmer so desires, which helps the speed of function calls).

--
Mats