strange std::map behavior

This is a discussion on strange std::map behavior within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by manav thanks laser! that utility function deserves to be in my toolbox! Yes, but beware that if ...

  1. #46
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manav View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #47
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,548
    Quote Originally Posted by laserlight View Post
    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.

    Quote Originally Posted by matsp View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #48
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    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.
    Last edited by laserlight; 04-11-2008 at 05:52 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #49
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Quote Originally Posted by matsp View Post
    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.
    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!

  5. #50
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    Quote 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?

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #51
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manav View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #52
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Okay so now i got it! due to some strange reasons, i have to, and i will, avoid the more clear syntax of accessing map elements.
    and will be using find(), forever ... big alas!

  8. #53
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,548
    Quote Originally Posted by laserlight View Post
    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.

    Quote Originally Posted by laserlight View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #54
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #55
    Banned
    Join Date
    Nov 2007
    Posts
    678
    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=...);
    Last edited by manav; 04-11-2008 at 06:15 AM.

  11. #56
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #57
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Quote Originally Posted by CornedBee View Post
    Apples to oranges. Java doesn't have free functions, so they're not an alternative.
    there are namespace, classes, structs, unions, just to avoid free functions i guess

    Bla, bla, bla.


    That's why a new one is in development.
    i just wish it does not take another ten years.

  13. #58
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manav View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #59
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Quote Originally Posted by matsp View Post
    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.
    i am already *forced* to use C++ by my project!

    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?
    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++.

  15. #60
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manav View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 4 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strange string behavior
    By jcafaro10 in forum C Programming
    Replies: 2
    Last Post: 04-07-2009, 07:38 PM
  2. C++ list Strange Behavior
    By yongzai in forum C++ Programming
    Replies: 19
    Last Post: 12-29-2006, 01:56 AM
  3. Strange behavior of Strings
    By shyam168 in forum C Programming
    Replies: 9
    Last Post: 03-27-2006, 06:41 AM
  4. strange behavior
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 10-17-2005, 12:03 PM
  5. Strange behavior with CDateTimeCtrl
    By DonFiasco in forum Windows Programming
    Replies: 2
    Last Post: 12-19-2004, 01:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21