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

  1. #46
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Programmer_P View Post
    I just can't imagine a scenario where you would pass one map to a function, then pass a swapped map of that map to the same function...
    Fair enough -- as I said after years of using map-like data structures, in reality it's very rare that you would need a swapped map at all. However, if you see a need for it, then it is strange that you would think someone would not want to write a function to use it.

    I did create options:
    This misses the point of object oriented programming, but nevermind.
    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

  2. #47
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by MK27 View Post
    Fair enough -- as I said after years of using map-like data structures, in reality it's very rare that you would need a swapped map at all. However, if you see a need for it, then it is strange that you would think someone would not want to write a function to use it.
    I have already written a function: swap()

    This misses the point of object oriented programming, but nevermind.
    All those functions I mentioned (with the exception of swap(), which is global) are members of the generated enum's class.
    But admittedly, the generated class(es) are not OOP-oriented, since you would only need to create one object of each class. On the other hand though, I don't think OOP is the best answer for everything, nor was it the best answer for my generated file either.
    Last edited by Programmer_P; 06-19-2010 at 01:22 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  3. #48
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    And don't you think it would be more fail-proof if I write the function to pass in just a map, and return the multimap, instead of passing in both?
    You could, but then you either make some assumptions about the comparator type and allocator type of the multimap, or make life a little more difficult for the caller (or make life more difficult for yourself by having to provide overloads). When the multimap is an argument, you can deduce these automatically.
    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

  4. #49
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    You could, but then you either make some assumptions about the comparator type and allocator type of the multimap, or make life a little more difficult for the caller (or make life more difficult for yourself by having to provide overloads). When the multimap is an argument, you can deduce these automatically.
    See the code in this post, then tell me what you think.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  5. #50
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    See the code in this post, then tell me what you think.
    I think that you should try to actually use the function template. You will get compile errors that can be fixed, and in fixing them you will agree with me.
    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

  6. #51
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    I think that you should try to actually use the function template. You will get compile errors that can be fixed, and in fixing them you will agree with me.
    Oh yeah...my bad. I forgot to change "ResultCompare" to "SourceCompare" and "ResultAllocator" to "SourceAllocator" on the multimap line.

    I fixed that, but now a different problem cropped up:

    C++ code - 31 lines - codepad
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #52
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Right, but you cannot change "ResultCompare" to "SourceCompare" and "ResultAllocator" to "SourceAllocator" because they are not equivalent. For example, if you are mapping std::string to int, then the SourceCompare comparator would be used to compare std::string objects, so how can it be used to compare int objects?
    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. #53
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Oh, I know what the problem is...
    I'm trying to use the map paramaters as the multimap parameters, which obviously wont work, because apparently the compiler can't convert them to that.
    I should be able to fix that in a sec.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  9. #54
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    It's just as easy to create a second map that maps values to a vector of iterators that point into the first map. As long as you correctly maintain both maps during removes and inserts it works fine and it's less confusing and if you do it correctly there is hardly any additional overhead until you want to remove a value which might mean you need to remove one or more entries in the original map.

    However, that being said if you need key off of values instead of keys or you need to do both and I would say there is a serious flaw in your design. Multimaps were designed to map unique keys to one or more values and maps were designed to map unique keys to one unique value. That is the intent of the data structure. Altering that design is not good and points to a flaw in your own design or to the idea that maps may not be what you need.

    Most of these types of problems can easily be solved by re-design and/or by making use of multiple STL containers. If you understand the STL you can build the system so it adds minimal overhead at the cost of a bit of memory. However the memory that would be saved in another approach does not justify the convoluted code and logic it requires to accomplish. When you run into situations like this it is often best to use the approach that makes the code the clearest.
    Last edited by VirtualAce; 06-19-2010 at 03:23 PM.

  10. #55
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Ok, I did it:

    http://codepad.org/OdGVPiEW

    Side note: I hate maps and multimaps. The syntax sucks. I guess the inserting part is easy enough, but its a real pain to iterate through a map, and retrieve stuff. Why can't they just provide a getKeyValue(index) and a getMappedValue(index) function, or something?
    Maybe I'll write my own...
    Last edited by Programmer_P; 06-19-2010 at 04:37 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  11. #56
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Maybe I'll write my own...
    No you shouldn't. STL code is well tested, standard, maintained by professionals, and widely known and used. IE: If you use it almost any C++ programmer in the world will understand your code. If you use it you can be assured the code works and is, for the most part, free of bugs. Re-implementing this would cost you unnecessary time and effort and you would be fixing bugs in it from here till eternity. Just use STL. That is what it is there for. There are times when it may be necessary for time critical code to code your own container but those cases are the exception and not the rule.

    Once you get used to the iterator paradigm of the STL you will learn to love it and will wonder how you ever programmed without it. It really is your best friend. I highly recommend after using it for a bit you purchase Effective STL by Scott Meyers. I would also recommend the gang of four Design Patterns book by Erich Gamma, Richard Helm, Raph Johnson, and John Vlissides. Neither of these books leaves my sight when programming.
    Last edited by VirtualAce; 06-19-2010 at 04:39 PM.

  12. #57
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    So you have made "some assumptions about the comparator type and allocator type of the multimap" and also of the map

    Quote Originally Posted by Programmer_P
    I guess the inserting part is easy enough, but its a real pain to iterate through a map, and retrieve stuff. Why can't they just provide a getKeyValue(index) and a getMappedValue(index) function, or something?
    Iterating through a map to retrieve stuff and asking for getKeyValue() sounds like you are not using the appropriate container. getMappedValue() already exists as the find() member function coupled with iterator dereference, or as the overloaded operator[].
    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

  13. #58
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    It's just as easy to create a second map that maps values to a vector of iterators that point into the first map.
    I have no idea what you mean by that. Could you post some example code for that?
    As long as you correctly maintain both maps during removes and inserts it works fine and it's less confusing and if you do it correctly there is hardly any additional overhead until you want to remove a value which might mean you need to remove one or more entries in the original map.
    Ok...
    However, that being said if you need key off of values instead of keys or you need to do both and I would say there is a serious flaw in your design.
    Interesting English. I think you meant:

    However, that being said, if you need to get a key value from a mapped value, instead of a mapped value from a key value, or you need to do both (?; I think we can remove that part completely...), I would say there is a serious flaw in your design.
    In response to how I translated what you said, and not to what you actually technically said, I'd say that is a matter of opinion. I think there are times when you may have a map with some content, but what you really need is a map with the same content (of sorts), only the key values are the mapped values, and the mapped values are the key values. That's where my swap() function comes in handy.
    Multimaps were designed to map unique keys to one or more values and maps were designed to map unique keys to one unique value.
    That is true, yet what we're talking about here, the container storing stuff doesn't start out as a multimap. It starts out as a map, hence each key will be mapped to just one value. It is only after using swap that it becomes a multimap. And now that I think of it, I don't think multimaps will be useful in this scenario at all. I'll go ahead and change it to a standard map.
    That is the intent of the data structure. Altering that design is not good and points to a flaw in your own design or to the idea that maps may not be what you need.
    Technically, I wasn't altering any design at all. I was only taking the content of one map, and putting it another map, only with the key values as the mapped values, and the mapped values as the key values in the new map.
    That is not changing the underlying design of a map at all. It is only changing what is what in what, or something to that effect.
    Most of these types of problems can easily be solved by re-design and/or by making use of multiple STL containers.
    Maybe. But I'd need to see some of these "easy" solutions to this problem in action first before I decide whether that is really the best idea or not.
    If you understand the STL you can build the system so it adds minimal overhead at the cost of a bit of memory. However the memory that would be saved in another approach does not justify the convoluted code and logic it requires to accomplish. When you run into situations like this it is often best to use the approach that makes the code the clearest.
    I'd say the code is pretty clear...
    Code:
    CnameofenumToStrings classObject;
    map <string, unsigned int> enumerationsMap = classObject.getEnumerationsMap();
    multimap <unsigned int, string> swappedMap = swap(enumerationsMap);
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  14. #59
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    So you have made "some assumptions about the comparator type and allocator type of the multimap" and also of the map
    Not really. I decided to do away with the custom compare and allocator types altogether in the swap function, since it proved to be too difficult to get them into the function. I figure you can always add them in later after you get the returned map from swap(). As it is now, the returned map will end up with the default comparator and default allocator.
    Iterating through a map to retrieve stuff and asking for getKeyValue() sounds like you are not using the appropriate container.
    Why?
    I figure you need to look at it like this:

    You create a map.
    You insert stuff into the map.
    Now you want to retrieve stuff from the map.
    So you call getMappedValue(getKeyValue(i)), or something like that, the basic idea being that you want to get the current key value you're at in the map, then use it to get the mapped value.

    getMappedValue() already exists as the find() member function coupled with iterator dereference, or as the overloaded operator[].
    Yeah, but find() is such a pain since it returns an iterator for the map type instead of the mapped value itself, then you have to dereference the iterator to get at the current mapped element, creating problems because then you have to have an iterator iterator in a loop, then increment the iterator. And you have to pass it the key value you want to retrieve, meaning you will most of the time have to know what's actually stored in the key side of the map at the current index. Plus, when you create an iterator, you have to create one specifically for that map type. There is not a generic one for any map.
    As for the [] operator, I already tried outputting nameOfMap[i] in a for loop, but it wouldn't compile for some reason.

    Maybe I'm griping, but I don't know...
    I think the vector type is a lot more friendly than multimap (and possibly map) for the whole process of iterating through it and retrieving values.
    Last edited by Programmer_P; 06-19-2010 at 05:47 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  15. #60
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Whether you use a map of vectors or a multi-map is up to you. The multi-map for the reverse look-up does indeed fit the bill. I guess my thinking here is to step back and think seriously about why it is you need to do this? What part of your design is forcing you to need to look for values instead of keys?

    I think there are times when you may have a map with some content, but what you really need is a map with the same content (of sorts), only the key values are the mapped values, and the mapped values are the key values.
    This is simply a reverse lookup. But normally you use a map b/c you want to assign some key or some type of ID to a value. If the same value is being placed into a map then theoretically it should have the same ID. That is where the confusion comes in. Two instances of a class usually means two unique keys or IDs in the map that point to two different instances. If you want to share the instance of an object then one unique ID or key is needed.

    For instance:

    Objects A B C D of type IMyObject
    Container: std::map<unsigned int, IMyObject *>

    key, value
    0,A
    1,B
    2,C
    3,D
    4,E
    5,A
    6,B
    7,C
    8,D
    9,E

    I would argue here that 5,6,7,8 and 9 all point to different instances of A,B,C,D,E and therefore should have unique keys. If you want to share the instances of A,B,C,D,E then you need some way of either sharing their keys or making them available. A reverse lookup map or multi-map would work or you could return the ID from the function that did the insertion and then make that available to those objects that need it. I'm not used to seeing identical values stored in a map under a different key - that is, when the values are pointers.

    I guess my reasoning is that if key 0 and key 5 have the same exact value you have now wasted memory by storing a shared object twice. Of course this only applies if you are storing pointers to objects in the map. But even if you map from int to int the key determines the uniqueness not the value.

    1,1
    2,3
    4,1
    5,2
    6,2

    So in this map from int to int if you want to get the value with a key of 1, it is 1. If you want the value with a key of 4, it is 1. Why would you ever care about all the values that were 1? Yes they both have a value of 1 but that really doesn't mean anything in the context of this map. Obviously some other object thought it was necessary to store a 1 with a key of 4 or it would not have inserted it into the map.
    Last edited by VirtualAce; 06-19-2010 at 05:17 PM.

Popular pages Recent additions subscribe to a feed