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

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?

Originally Posted by Bubba

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.

Originally Posted by laserlight

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

Nevermind. I see why you used the multimap. Because it allows duplicate values in the map.

Originally Posted by MK27

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.

@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.

Originally Posted by Programmer_P

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.

Originally Posted by MK27

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.

Originally Posted by Programmer_P

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).

Originally Posted by MK27

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.

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;
}

Originally Posted by Programmer_P

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.

Originally Posted by MK27

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.

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.