Thread: Is it possible to swap the key values and the mapped values around in a map?

  1. #91
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    Ideally, a map should allow efficient access by sequential index of the the current key value, i.e. so that you increment the index iterator to access the next key value of the map, and hence, also the mapped value.
    (...)
    The way I see it, it doesn't need to be arranged sequentially in memory, to have such functionality in the std::map or std::multimap classes. The elements could be arranged in the map in the same order that they were inserted, and you could retrieve them in the same manner.
    You are right to say that such functionality can be provided, but there is a cost to it. For example, a vector (or deque) of map iterators could be used to provide efficient access by sequential index. It does not make sense to add this along with std::map and std::multimap because not every use of maps and multimaps needs such functionality and hence should not automatically incur such a cost (and this would also change the time complexity of operations such as removing elements), but there is nothing stopping you from building on these containers for a container that meets your exact requirements, within what is computationally possible.
    Last edited by laserlight; 06-20-2010 at 05:39 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #92
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    You are right to say that such functionality can be provided, but there is a cost to it. For example, a vector (or deque) of map iterators could be used to provide efficient access by sequential index. It does not make sense to add this along with std::map and std::multimap because not every use of maps and multimaps needs such functionality and hence should not automatically incur such a cost (and this would also change the time complexity of operations such as removing elements), but there is nothing stopping you from building on these containers for a container that meets your exact requirements, within what is computationally possible.
    I don't get what you would use a vector (or deque) of map iterators for? I think if I was going to build on some existing containers, I would just build on the std::map and std::multimap types, and write a templated class that contains a map of the type specified in the template (so you probably pass a map into the constructor of the class). Then I would have a single iterator of the map type to iterate through the map in a function with a declaration type like this:

    Code:
    const MapMappedValueType& at(unsigned int index);
    which would return the mapped value found at the specified index of the map.
    Last edited by Programmer_P; 06-20-2010 at 06:44 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  3. #93
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I think there is a valuable lesson to be learned here beyond the code at hand. First you will learn quickly through this board and through the real world that code is not personal. It is extremely hard to separate code from emotions but in the end: code is code. And in the end regardless of the intention, the person who wrote it, or what a great person they may be: bad code is bad code and will cause problems later.

    That being said you must understand that normally people are not given as much attention here as you have been given in many of your threads. I think it is because many of us see your passion and desire to learn and we sort of see some of ourselves in you. Understand that in the real world you will never be able to present a design to anyone and have it approved straight away with no questions asked. Most of the time you are working on code bases that you do not own and no one in their right mind is just going to trust 1 person to make all the design decisions. When you work on a team of developers you get the kind of bantering you see here in this thread. It is very important that when you present a design or present code to another person that you take their comments as open mindedly as possible. If you take offense to their accusations then you may need to step back from your code for a bit and look at why you are getting so angry or feel as if you are being attacked.

    Almost every one of us in this thread has presented something to the board or said something on the board that just does not fly with other people. I think the key difference here is we know when to compromise and quite honestly be quiet and learn a bit. It is an acquired skill to know when to defend your design and have good sound reasons for doing so and realizing that perhaps your design is actually a bit flawed. No one can teach you this balancing act but what you see here in this thread is a good indication that something in your design, based on the bits of information you have provided about your program here, is amiss. Experienced developers here can see immediately based on your statements and what it is you want to do that something at the very core of your program is incorrectly designed. Most experienced developers will be able to shoot down a design or a block of code with ease and have very good reasons for doing so. Less experienced devs should take this as a learning experience and learn from what the experienced developer is saying. Now, in some cases, standing your ground shows maturity and confidence in your design and that is necessary but you had better make sure your design is sound and you haven't made a serious oversight somewhere. Because this is hard to do usually the best road to take is one of compromise, open-mindedness, and willingness to learn from others who may have a different viewpoint on the matter.

    Discussions like the one in this thread are the kind of discussions that produce superior software in my opinion b/c they force the designers and implementors to take a long hard look at what it is they are doing and the ramifications of said actions.

    So don't take it personal. Code attacks are not personal. Also if you read some of your later posts I think you will find that it is you who started finger pointing and attacking long before any of us resorted to this. I'm not attacking you when I say you have a poor attitude when it comes to learning new things. That is evidenced by your responses here.

    So chill out, step back a bit, emotionally detach yourself from the code you have written (it's just text), and listen to the advice being given. When someone asks you why you need to do something you should be able to logically explain it and if you cannot or you attempt to cover obvious holes in your logic then you should be questioning it as well.

    And trust me when I say that if this many people have responded it isn't to attack you it is because we see potential along with plenty of effort which is indeed rare. If we have paid this much attention to you it is because we are genuinely trying to help you become a better programmer. If you present material to us and you have not thought about the disadvantages or pitfalls of your design and have not readily acknowledged them....red flags start to fly everywhere in our minds. You should be mindful that no design is perfect and all have their disadvantages - even yours.

    We are after all software engineers, therefore we question everything.
    Last edited by VirtualAce; 06-20-2010 at 06:47 PM.

  4. #94
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    I don't get what you would use a vector of map iterators for?
    Suppose you want to access the mapped value at index n. You first access the nth element of this vector to obtain the map iterator, then you dereference this map iterator to get the second member, which is the mapped value that you want.

    Quote Originally Posted by Programmer_P
    Then I would have a single iterator of the map type to iterate through the map in a function with a declaration type like this:
    That will not work: the elements in a map are effectively sorted by key, not by the order in which they were inserted into the map. Since you have no way to re-construct that order given just the map, you have no way to access the nth element.

    But suppose that you mean nth element as in nth element based on the order of the keys. Then you can indeed access the nth element, but it will be relatively slow (linear time). You can still use a vector or deque to speed up access to constant time in this case, except that again the performance characteristic of other operations will be affected, e.g., if you want to insert a new element, you have to do it in linear time instead of O(log n) time, since you may need to insert into somewhere in the middle of the corresponding vector or deque.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #95
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    Suppose you want to access the mapped value at index n. You first access the nth element of this vector to obtain the map iterator, then you dereference this map iterator to get the second member, which is the mapped value that you want.
    Yeah...but that's still a single iterator needed, not a vector of iterators.

    That will not work: the elements in a map are effectively sorted by key, not by the order in which they were inserted into the map. Since you have no way to re-construct that order given just the map, you have no way to access the nth element.
    I was thinking along the lines of accessing the mapped value of the current element by returning iteratorName->second once the iterator has reached the index passed into the function (I'll increment an int or unsigned int in a loop to keep track of the index).
    But suppose that you mean nth element as in nth element based on the order of the keys.
    Yeah, that's what I mean.
    Then you can indeed access the nth element, but it will be relatively slow (linear time). You can still use a vector or deque to speed up access to constant time in this case, except that again the performance characteristic of other operations will be affected, e.g., if you want to insert a new element, you have to do it in linear time instead of O(log n) time, since you may need to insert into somewhere in the middle of the corresponding vector or deque.
    Still don't see the point of using a vector or deque here, since a vector is basically a resizable array of a specific type. Why would I be storing map iterators in either one of those types, when I'm only interested in one iterator in the at() function, so that I can access the mapped element at the index passed?
    Last edited by Programmer_P; 06-20-2010 at 06:59 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  6. #96
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Programmer_P View Post
    I don't get what you would use a vector of map iterators for?
    It's about efficiency, and it relates to what I said earlier about how a map is actually laid out in memory (it's a tree, not a sequential array). There is already a begin() and end() for map, so you can iterate through a map the same way you would iterate through a vector. While C++ iterator syntax is kind of "clunky" (which is a consequence of other design choices in the language), it is not so rough, methinks, once you get used to it. Adding an [] operation is either a question of style -- I think that is your issue here -- or else one of efficiency.

    I think the style issue is something you should just get used to, since iterators are pretty fundamental anyway and not something to be avoided. You cannot realistically set out to redefine basic C++ syntax without just making it more cumbersome, performance wise. And C++ is about performance. Speed. Fast. Otherwise no one would bother with the clunky syntax.

    WRT to efficiency, what laserlight means is you could get an iterator to every element in a map, in order, and assign them to a vector. Then you could use [] AND (more significantly) this would be more efficient than using the map iterator.

    Why? First, to clarify: "trees" and "arrays" are language independent concepts that relate to the physical nature of computer memory. The difference between a map and a vector is the difference between a tree and an array. With an array, all the computer needs to do is move to the next sequential memory address to find the next element. Very simple. A straight line.

    Trees (as the name implies) are not straight lines. The next "in order" element is not right next door. It needs to be found. Iterators facilitate this. I am sure it will be more or less impossible to understand why without doing some reading on how trees work, but you don't have to do that right now. Anyway: maps require more storage space because they must maintain pointers from element to element, and to find the "next" in order element, the computer must "traverse the tree". This is much more expensive than just advancing to the next memory address.

    So what laserlight means is that if you want to keep such an index, it should be in some kind of sequential container, such as a vector. My advice is to not worry about it and get comfortable with iterators!!
    Last edited by MK27; 06-20-2010 at 07:09 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #97
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    Yeah...but that's still a single iterator needed, not a vector of iterators.
    You need a vector of iterators in order to get that single iterator in constant time.

    Quote Originally Posted by Programmer_P
    Still don't see the point of using a vector or deque here, since a vector is basically a resizable array of a specific type. Why would I be storing map iterators in either one of those types, when I'm only interested in one iterator in the at() function, so that I can access the mapped element at the index passed?
    So that you can access the nth element in constant time. If you are willing to settle for accessing the nth element in linear time, then that is fine: all you need is a function template (you can make use of the std::advance function template from <iterator> to do the job). The time complexity of all other operations will remain the same.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #98
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    So what laserlight means is that if you want to keep such an index, it should be in some kind of sequential container, such as a vector.
    And to add...that if you do use a vector and store off the index be careful when you remove something from the vector b/c this invalidates all iterators (and this indices) beyond the point of removal. This could wreak havoc in your system depending on how you are using the vector.

    As an example I used a vector for a texture system. Everything worked great until I removed one texture. After that my game was totally messed up b/c every texture ID was now 1 off and was not indexing the correct texture anymore. Because I hadn't thought about this issue with vector and chose the wrong container I was forced to do some major re-factoring to use a different data structure, namely, a std::map.

    Also keep in mind that it is almost 4x as fast to iterate a vector as a map. Find on a map should be O(n log n) but I've found through personal tests that iterating a map is quite slow. Now this performance stuff probably doesn't apply to a small program such as this but if it were going to be a component in a much larger pogram then it might become an issue. Don't quote me on the 4x as slow - I'm sure this is dependent on a lot of factors.

    The lesson here is use the right container for the job. You can only choose the right container when you understand how each one works. There are some containers I rarely use and am not all that familiar with. Then I turn to my STL book(s) for assistance.
    Last edited by VirtualAce; 06-20-2010 at 07:08 PM.

  9. #99
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Bubba
    Also keep in mind that it is almost 4x as fast to iterate a vector as a map. Find on a map should be O(n log n) but I've found through personal tests that iterating a map is quite slow.
    Actually, find on a map is in O(log n). Iterating through a map is in O(n), but this is definitely going to be slower than iterating through a vector in the long run, even though both operations are in O(n).

    By the way, here is a quick stab at the function template that I was talking about:
    Code:
    #include <iterator>
    #include <stdexcept>
    
    template<typename Map>
    typename Map::mapped_type& at(Map& container, typename Map::size_type n)
    {
        if (n < container.size())
        {
            typename Map::iterator iter(container.begin());
            std::advance(iter, static_cast<typename Map::difference_type>(n));
            return iter->second;
        }
        else
        {
            throw std::out_of_range("Error: invalid map index.");
        }
    }
    Note that you should const-overload it for a const Map& and corresponding const typename Map::mapped_type& return type. But before you gleefully use this, consider the impact this at function template can have on code that uses it indiscriminately; it has the potential to result in innocuous code that runs slower than it should.
    Last edited by laserlight; 06-20-2010 at 07:27 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #100
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Is it O(log n)? Hmm. I thought that initially but some time ago someone told me it was O(n log n). Whatever, that will teach me to take people at their word eh?

    Iterating through a map is in O(n), but this is definitely going to be slower than iterating through a vector in the long run, even though both operations are in O(n).
    Yep. Both are O(n) to iterate but map is certainly slower.

  11. #101
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Bubba View Post
    Is it O(log n)? Hmm. I thought that initially but some time ago someone told me it was O(n log n). Whatever, that will teach me to take people at their word eh?


    Yep. Both are O(n) to iterate but map is certainly slower.
    n log n would be the case for performing a find on every item.
    For a single find, there are log n links to follow in the binary tree.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed