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

  1. #1
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827

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

    Hey, I was wondering if its possible to swap the key values and the mapped values of a std::map around? I had hopes that the map::swap() function would do this, but it turns out it just swaps the content of two different maps with the same type.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    As in given a value you want to find the corresponding key(s)? That is certainly possible, but it is slow as you basically have to perform a linear search of the values to obtain the corresponding keys.

    As such, what you can do is to maintain another map (or multimap) that maps in the other direction, or use something like Boost.Bimap.
    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

  3. #3
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    As in given a value you want to find the corresponding key(s)? That is certainly possible, but it is slow as you basically have to perform a linear search of the values to obtain the corresponding keys.

    As such, what you can do is to maintain another map (or multimap) that maps in the other direction, or use something like Boost.Bimap.
    Not really. My idea is to call a function to retrieve a map containing the same content as another map, only the key values and the mapped values have been swapped. I don't think that's the same thing you're saying, but I could be wrong...

    I suppose I could write my own, if there's not something already available for that.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Yeah, it is not quite what I thought you were talking about, but Boost.Bimap effectively solves your problem.
    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. #5
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Thanks, I'll check it out.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  6. #6
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    On second thought, a non-STL library function is probably not the best idea under the circumstances, seeing as the method needs to be in a generated file of my program.
    I guess I'll just write a global templated function called swap() expecting any type of map, and returning any type of map, to file. The code should be easy enough...
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Programmer_P View Post
    On second thought, a non-STL library function is probably not the best idea under the circumstances, seeing as the method needs to be in a generated file of my program.
    What?
    What difference does it make if it's boost or STL?
    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.

  8. #8
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Elysia View Post
    What?
    What difference does it make if it's boost or STL?
    Because if its STL, then I can just include the header containing the STL function inside the generated header by my program, then the user can include the generated header in his program and everything will work without having to download a 3rd party library.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Well, it's your prerogative, but I urge everyone to download and, at the very least, try boost.
    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.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    I guess I'll just write a global templated function called swap() expecting any type of map, and returning any type of map, to file. The code should be easy enough...
    You should be aware that std::map has four template parameters: the key type, the mapped type, the key comparator type, and the allocator type. A given standard library implementation might add more, though I am not absolutely sure if that is allowed. Furthermore, a std::map has unique keys, but duplicate values are allowed. If you want to reverse a map with duplicate values, you then have the problem where one of the entries must be discarded unless you return a std::multimap instead.

    Quote Originally Posted by Programmer_P
    Because if its STL, then I can just include the header containing the STL function inside the generated header by my program, then the user can include the generated header in his program and everything will work without having to download a 3rd party library.
    Boost.Bimap is a header-only library. You can use bcp to extract a portion of Boost to distribute with your program.
    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

  11. #11
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Would this function declaration work:

    Code:
    template <typename map aMapType> aMapType swap(aMapType& aMap);
    ?
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    It is not even syntactically valid. You should address the duplicate value problem that I talked about first. Furthermore, swap may be a poor name for this.
    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. #13
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Oh well...
    Nevermind the templated function then.
    I wrote one for a specific map type instead.
    And I have no idea what you mean by a "duplicate value problem", btw.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Programmer_P
    And I have no idea what you mean by a "duplicate value problem", btw.
    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.
    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

  15. #15
    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.
    Oh, right. I see what you mean.
    Fortunately, though, my function will only (theoretically, assuming of course it is used correctly) swap a specific map (one that does not have any duplicate values, every value will be unique).
    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.
    Interesting. I will look over your code when I get the time.
    Have to go do something in the real world right now...
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

Popular pages Recent additions subscribe to a feed