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

This is a discussion on Is it possible to swap the key values and the mapped values around in a map? within the C++ Programming forums, part of the General Programming Boards category; A map of vectors would fix the problem laserlight mentioned. Code: class DontDoThis { public: typedef std::map<std::string,IWhatever *> objectMap; typedef ...

  1. #16
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    A map of vectors would fix the problem laserlight mentioned.

    Code:
    class DontDoThis
    {
        public:
            typedef std::map<std::string,IWhatever *> objectMap;
            typedef objectMap::iterator objectMapIter;
    
            typedef std::vector<objectMapIter> mapIterVector;
            typedef keyVector::iterator mapIterVectorIter;
    
            typedef std::map<IWhatever *,mapIterVector> reverseLookupMap;
            typedef reverseLookupMap::iterator reverseLookupMapIter;
            ...
            ...
        private:
            objectMap m_objectMap;
            reverseLookUpMap m_reverseLookupMap;
            ...
            ...
    };
    A map or multimap is designed to be accessed via keys and not by values. Why would you ever need to key off of a value in a map?
    Last edited by VirtualAce; 06-19-2010 at 12:52 AM.

  2. #17
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    Why would you ever need to key off of a value in a map?
    There are some cases where it would be useful to swap a map around, so you can get the values which were originally the keys with the values which were originally the mapped values.
    For example, I added a map to the generated file produced by ConvertEnumToStrings which has a type like this:

    Code:
    map <string, unsigned int> enumerationsMap;
    This map stores the string names of the enumerations found in an enum, as well as their corresponding numerical values.
    Normally you would want to retrieve the numerical values of the enumerations by using their string names, but sometimes you might want to retrieve the string names of the enumerations by their corresponding numerical values instead.
    I wanted to provide both methods for convenience, though I still have the function for retrieving a string name of an enumeration by passing in an enumeration name or its numerical value as well.
    That way my generated class for an enum found is far more flexible and lets you do more stuff. I started coding more on my web coder program, and realized I needed a map generated by ConvertEnumToStrings to retrieve a unsigned int value based on the string name of an enumeration. So I now have produced a new version of ConvertEnumToStrings which does just that.

    EDIT: And I realize I could always create a different map for that as a class member like the other map, but thought, what the heck. A function for swapping maps around would be useful, I think, though I guess if I'm going to write such a function, I might as well write it so it works with any map which doesn't have duplicates values in it.
    Last edited by Programmer_P; 06-19-2010 at 09:14 AM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  3. #18
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    Consider a map where you map 1 -> 3 and 2 -> 3. Now, you want to turn the keys into the mapped values and the mapped values into the keys. You apply your function, and thus obtain 3 -> 1 and 3 -> 2. But a map can only have unique keys, thus one of these two mappings must be discarded, unless you use a multimap instead.

    Anyway, this is what I tried:
    Code:
    #include <map>
    #include <utility>
    
    template<typename Key, typename T,
             typename SourceCompare, typename SourceAllocator,
             typename ResultCompare, typename ResultAllocator>
    void flip(const std::map<Key, T, SourceCompare, SourceAllocator>& source,
              std::multimap<T, Key, ResultCompare, ResultAllocator>& result)
    {
        typedef std::map<Key, T, SourceCompare, SourceAllocator> source_type;
        typedef typename source_type::const_iterator source_iterator;
    
        const source_iterator end = source.end();
        for (source_iterator i = source.begin(); i != end; ++i)
        {
            result.insert(std::make_pair(i->second, i->first));
        }
    }
    
    int main()
    {
        std::map<int, long> x;
        std::multimap<long, int> y;
        flip(x, y);
    }
    Note that it will not work if the standard library implementation introduces more template parameters than those outlined in the C++ standard.
    That's some interesting code. But why not just insert into another map (only with the types reversed) and return the other map?
    What advantage does the multimap give you?
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  4. #19
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I don't think it's weird to want to key off a value, altho in years of using map like structures I can't recall doing it very often.

    There are apparently some data structures for doing this, such as the UB tree, but I've never written one.

    WRT to retrieving a string with a number, you can just use a vector<string> in the same order as the enum, and use the index to look up the string.
    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

  5. #20
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Nevermind. I see why you used the multimap. Because it allows duplicate values in the map.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  6. #21
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by MK27 View Post
    WRT to retrieving a string with a number, you can just use a vector<string> in the same order as the enum, and use the index to look up the string.
    That would work, except the objective here is to get the corresponding numerical value (in the form of an unsigned int) of an enumeration.
    That is why I'm using a map.
    Last edited by Programmer_P; 06-19-2010 at 09:28 AM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #22
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    @laserlight: 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?
    This way there is no risk of someone passing in a multimap that already contains stuff. Remember the objective is to get an exact copy of one map, only the key values and the mapped values have been swapped.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Programmer_P View Post
    That would work, except the objective here is to get the corresponding numerical value (in the form of an unsigned int) of an enumeration.
    That is why I'm using a map.
    Yes, but you cannot get the string with the number that way (well, you can, see below). I'm just saying, you might as well use a parallel vector in this case since the numbers are from an enum (0,1,2,3,4...). Generally, you would need another map, as laserlight recommends, or to write some specialized data structure.

    Of course, if you do not want to duplicate the data that way (which may not be a good idea) and the enums are only a few hundred items you might as well just write a function to iterate thru the map and find them -- you are looking for a number, which is a pretty cheap compare, the look up is not efficient but in this case it will be very quick anyway.
    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

  9. #24
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by MK27 View Post
    Yes, but you cannot get the string with the number that way (well, you can, see below). I'm just saying, you might as well use a parallel vector in this case since the numbers are from an enum (0,1,2,3,4...). Generally, you would need another map, as laserlight recommends, or to write some specialized data structure.
    Not all enums have values going from 0 - lastEnumerationValue, incrementing by 1 each enumeration. I wanted to handle all cases of enums (or at least those with explicit numbers assigned to the enumerations, and not using variable names).
    Of course, if you do not want to duplicate the data that way (which may not be a good idea) and the enums are only a few hundred items you might as well just write a function to iterate thru the map and find them -- you are looking for a number, which is a pretty cheap compare, the look up is not efficient but in this case it will be very quick anyway.
    There is no need to write a function to iterate through a map to find a number. All you have to do to access a specific enumeration number will be:

    Code:
    #include "results.h" //include the generated file created by ConvertEnumToStrings
    
    using namespace std;
    
    enum {
      aEnumeration1 = 0,
      aEnumeration2 = 1,
      aEnumeration3 = 3
      //etc...
    };
    
    int main() {
        CnameofenumToStrings object; //create an object of the generated class for the enum
        map <string, unsigned int> enumerationsMap = object.getEnumerationsMap();
        unsigned int valueOfAEnumeration1 = enumerationsMap.at("aEnumeration1");
        multimap <unsigned int, string> swappedMap = swap(enumerationsMap);
        cout<< "The numerical value of the enumeration with the string name of \"" << swappedMap.at(0) << "\"is:\n"
               << valueOfAEnumeration1 <<endl;
        cout<< "\nPress Enter to end this program." <<endl;
        cin.get();
        return 0;
    }
    The above of course assumes you have already ran ConvertEnumToStrings on whatever file that has that code in it. The result of that would be:

    The numerical value of the enumeration with the string name of "aEnumeration1" is:
    0

    Or you could do any number of things with it. That was just a small example.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  10. #25
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Programmer_P View Post
    There is no need to write a function to iterate through a map to find a number.
    Sigh. If the number is the value and not the key, yes you do. What would you call all that code you just posted? Is swap a function, or what? What does "iterating through the map" mean? Some code, ie. probably a function?* Or does it occur by magic?

    My point was that you could do it in a simpler way if the values were sequential, but as you indicate that may not always be the case, so you would need a function to generate a second map, which is what you have now.

    * its a basic principle of programming that you put sections of code you are going to reuse into a function (instead of say, cutting and pasting them all over the place).
    Last edited by MK27; 06-19-2010 at 10:18 AM.
    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

  11. #26
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by MK27 View Post
    Sigh. If the number is the value and not the key, yes you do.
    I just demonstrated swapping the key values and the mapped values around, which is what the topic of this thread is all about.
    What would you call all that code you just posted? Is swap a function, or what? My point was that you could do it in a simpler way if the values were sequential, but as you indicate that may not always be the case, so you would need a function to generate a second map, which is what you have now.
    Yes, swap() will be a function in the generated file created by ConvertEnumToStrings once I post the new version here. Basically, it will use a map reference parameter and you can pass any kind of map to it. The function will then iterate through the map, inserting the key values into the map values of a new map, and vice versa. It will then return the new map.

    But I'm still not iterating through the map to find a number (at least not in the sense that I will have to code for this). That is the point I'm trying to make.
    You can just use the at() function to retrieve an enumeration's number.
    Last edited by Programmer_P; 06-19-2010 at 10:44 AM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  12. #27
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Here is the code for the swap() function (based off of laserlight's example, and untested so far):

    Code:
    template<typename Key, typename T, typename SourceCompare, typename SourceAllocator>
    multimap<Key, T, ResultCompare, ResultAllocator> 
    swap(map<Key, T, SourceCompare, SourceAllocator>& sourceMap) {
         typedef map<Key, T, SourceCompare, SourceAllocator> sourceType;
         typedef typename sourceType::const_iterator sourceIterator;
         const sourceIterator end = sourceMap.end();
         multimap<Key, T, SourceCompare, SourceAllocator> newMap;
         for (sourceIterator i = sourceMap.begin(); i != end; i++) {
              newMap.insert(make_pair(i->second, i->first));
         }
         return newMap;
    }
    Last edited by Programmer_P; 06-19-2010 at 10:46 AM. Reason: fixed formatting
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  13. #28
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Programmer_P View Post
    But I'm still not iterating through the map to find a number
    No, but if you generate that second map with swap every time you do a look up, it is very inefficient. You should only do it once.

    However, that's not possible if the first map is bound to change (I don't think it is in your case tho) -- you would have to keep regenerating the second map, again a big waste of time. In that case, considering again that these maps are quite small (a few hundred or a thousand items), you might as well just do the iteration. IMO, since they are small, that's what you might as well do anyway, there really is not much need for a second map here.

    But that's just an opinion. The way you have it now is fine as long as you don't have to do that more than once.
    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

  14. #29
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by MK27 View Post
    No, but if you generate that second map with swap every time you do a look up, it is very inefficient. You should only do it once.
    What would be the point of calling the swap function more than once for a single map?
    Of course I would only do it once...
    However, that's not possible if the first map is bound to change (I don't think it is in your case tho) -- you would have to keep regenerating the second map, again a big waste of time.
    The map wont change, unless you do some screwing around with the contents of the map (which is HIGHLY unrecommended ). The map will be generated once for every enum in a file you pass to ConvertEnumToStrings. A separate class with functions for the whole works will be created for each enum in a single file, so there's no problem there.
    In that case, considering again that these maps are quite small (a few hundred or a thousand items), you might as well just do the iteration. IMO, since they are small, that's what you might as well do anyway, there really is not much need for a second map here.
    One line of code versus several lines of code is definitely the way to go, IMO...
    But that's just an opinion. The way you have it now is fine as long as you don't have to do that more than once.
    Yep, like already mentioned, you will only have to do it once for a single enum.
    Then you can retrieve any enumeration's string name using the same swapped map.
    Last edited by Programmer_P; 06-19-2010 at 10:54 AM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  15. #30
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Oh, and I need to mention that the swap() function will be global and not a member function, and will be created only once for a single file, regardless of whether or not there are multiple enums in the file passed to ConvertEnumToStrings.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

Page 2 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

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