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; Oh, and does std::map actually have an at() function? It appears to because I've managed to compile my ConvertEnumToStrings program ...

  1. #61
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Oh, and does std::map actually have an at() function? It appears to because I've managed to compile my ConvertEnumToStrings program using it, but I can't find it documented anywhere on the web. And I know for sure std::multimap doesn't, because it wouldn't compile using at().
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  2. #62
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    From MSDN for std::map:
    Reference
    Constructors
    map
    Constructs a list of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other map.

    Typedefs
    allocator_type
    A type that represents the allocator class for the map object.

    const_iterator
    A type that provides a bidirectional iterator that can read a const element in the map.

    const_pointer
    A type that provides a pointer to a const element in a map.

    const_reference
    A type that provides a reference to a const element stored in a map for reading and performing const operations.

    const_reverse_iterator
    A type that provides a bidirectional iterator that can read any const element in the map.

    difference_type
    A signed integer type that can be used to represent the number of elements of a map in a range between elements pointed to by iterators.

    iterator
    A type that provides a bidirectional iterator that can read or modify any element in a map.

    key_compare
    A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the map.

    key_type
    A type that describes the sort key object which constitutes each element of the map.

    mapped_type
    A type that represents the data type stored in a map.

    pointer
    A type that provides a pointer to a const element in a map.

    reference
    A type that provides a reference to an element stored in a map.

    reverse_iterator
    A type that provides a bidirectional iterator that can read or modify an element in a reversed map.

    size_type
    An unsigned integer type that can represent the number of elements in a map

    value_type
    A type that provides a function object that can compare two elements as sort keys to determine their relative order in the map.

    Member Functions
    begin
    Returns an iterator addressing the first element in the map.

    clear
    Erases all the elements of a map.

    count
    Returns the number of elements in a map whose key matches a parameter-specified key.

    empty
    Tests if a map is empty.

    end
    Returns an iterator that addresses the location succeeding the last element in a map.

    equal_range
    Returns an iterator that addresses the location succeeding the last element in a map.

    erase
    Removes an element or a range of elements in a map from specified positions

    find
    Returns an iterator addressing the location of an element in a map that has a key equivalent to a specified key.

    get_allocator
    Returns a copy of the allocator object used to construct the map.

    insert
    Inserts an element or a range of elements into the map at a specified position.

    key_comp
    Retrieves a copy of the comparison object used to order keys in a map.

    lower_bound
    Returns an iterator to the first element in a map that with a key value that is equal to or greater than that of a specified key.

    max_size
    Returns the maximum length of the map.

    rbegin
    Returns an iterator addressing the first element in a reversed map.

    rend
    Returns an iterator that addresses the location succeeding the last element in a reversed map.

    size
    Returns the number of elements in the map.

    swap
    Exchanges the elements of two maps.

    upper_bound
    Returns an iterator to the first element in a map that with a key value that is greater than that of a specified key.

    value_comp
    Retrieves a copy of the comparison object used to order element values in a map.

    Operators
    operator[]
    Inserts an element into a map with a specified key value.

  3. #63
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    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?


    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.
    Ok, so I think what you're basically saying is this:

    std::maps may or may not have duplicate mapped values. Each one of those mapped values with the same value will all be "mapped" to the same key, correct?
    So when we flip it around, so that the key values become the mapped values, and vice versa, we're now looking at a map (assuming of course it had duplicate mapped values) which has duplicate keys. I guess that is why laserlight used multimap instead of map in her example (I switched it back to use multimaps instead of maps). But I'm not even sure if multimaps even support duplicate keys or not or if they just support multiple mapped values to a single key.
    So I guess that is a problem...
    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.
    Right, I get what you're saying here. Though technically, they will be unique keys I think, just with the same values. The only way you would be able to tell duplicate keys apart is if you check the indexes. But is it even possible for a multimap to store duplicate key values? I see in the multimap reference, it mentions that it allows "different elements to have the same key value", but I think that means that it only allows different mapped values to have the same key value, and it doesn't mention if it also allows different keys with the same name to be mapped to the same mapped value.
    Maybe I could add some functionality in the swap() (or flip(), whatever name I end up finally using) function to check for duplicates in the map that was passed before inserting into the multimap.
    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.
    AFAIK, no one posted in this thread any identical mapped values that were 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.
    I guess here you're referring to the map and not the multimap, since all keys are unique, only there are duplicate mapped values, each one mapped to a different key.
    However, after swapping that around, it would look like this:

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

    which brings us to the case where there are duplicate key values (though each one is mapped to a different mapped value), instead of duplicate mapped values. Can multimap handle this scenario? Also, what if the resulting multimap ended up something like this:

    1, 1
    3, 2
    1, 1
    2, 2
    1, 1

    Now there are both duplicate key values, and duplicate mapped values. And each one of the duplicate key values points at an identical mapped value which also has duplicates. What happens now?
    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.
    If by "values" you mean "mapped values", then you might care about all the mapped values that are 1 if you were storing multiple instances of 1 in the mapped side of the map, for some reason.
    But anyway, I think this is all irrevelant. All I need to know is if multimap will support all cases of maps with duplicate mapped values. If so, then I will keep using it.
    Last edited by Programmer_P; 06-19-2010 at 07:02 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  4. #64
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    From MSDN for std::map:
    That doesn't show any map::at() function there, but it obviously exists, at least in the STL library version used by my compiler, since it compiles with it.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  5. #65
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    If by "values" you mean "mapped values", then you might care about all the mapped values that are 1 if you were storing multiple instances of 1 in the mapped side of the map, for some reason.
    For this you would need a multi-map. I still do not understand why one would care about all the instances of a particular value in the map.

    Right, I get what you're saying here. Though technically, they will be unique keys I think, just with the same values. The only way you would be able to tell duplicate keys apart is if you check the indexes.
    There is a misunderstanding here. A map requires 1 unique key per value. This does not mean you cannot store the exact same value with a different key. From the perspective of a map object this is perfectly valid. However, when you move to storing pointers to objects on the heap in the map you could run into problems. So let's say you were storing pointers to objects on the heap in the map.

    Given the following code:

    Code:
    typedef std::map<unsigned int,Object *> theMap;
    typedef theMap::iterator theMapIter;
    
    theMap m_theMap;
    ...
    ...
    Object *pObject = new Object();
    m_theMap.insert(theMap::value_type(0,pObject));
    m_theMap.insert(theMap::value_type(1,pObject));
    You now have this:
    0, pointer to same pObject as pObject with key 1
    1, pointer to same pObject as pObject with key 0

    Perfectly valid from a map standpoint but dangerous. Essentially the same exact object can be accessed via two map keys or you have assigned two IDs to the same object. So if one object has a stored ID of 1 for pObject and one has a 0 for pObject now you have a mess. This could also potentially load the same object twice into memory if the map did any resource loading or other operations if the ID was not in the map. Also if you remove the object with key 1 and cleanup the object and remove it from the map the pointer with key 0 now points to garbage. For non-pointer maps this is not an issue but when you start storing pointers in your containers you could run into some ugly issues if you continue with this line of thinking.
    Last edited by VirtualAce; 06-19-2010 at 07:27 PM.

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

    Talking

    Quote Originally Posted by Bubba View Post
    For this you would need a multi-map. I still do not understand why one would care about all the instances of a particular value in the map.
    Honestly, I don't really care either.
    In fact, you were the one that brought that up first...
    I said that only in response to you mentioning it, and I was really talking about storing the instances of 1 found in the mapped values side of the map in something outside the map.

    I don't really give a damn at this current time, as a matter of fact, though.
    Last edited by Programmer_P; 06-19-2010 at 07:31 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #67
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    Laserlight brought up the legit problem that if you do this you will have to remove all instances of value from the original map. This is where the 'all instances of values' comes from.

  8. #68
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    There is a misunderstanding here. A map requires 1 unique key per value.
    Yeah, a std::map does, but I thought you were talking about a std::multimap. A lot of the rest of that post was based off of that assumption...
    This does not mean you cannot store the exact same value with a different key.
    Yeah, I understand the whole concept of duplicate mapped values (i.e. values with the same name) inside an std::map, each one of those mapped values having a different key.
    From the perspective of a map object this is perfectly valid. However, when you move to storing pointers to objects on the heap in the map you could run into problems. So let's say you were storing pointers to objects on the heap in the map.

    Given the following code:

    Code:
    typedef std::map<unsigned int,Object *> theMap;
    typedef theMap::iterator theMapIter;
    I think you meant:

    Code:
    typedef theMap<unsigned int, Object*>::iterator theMapIter;
    That last couple of hours I've been fooling around with maps, and learned that you need to specify the type of the map when you access the "iterator" member of the map class. That is one of the annoyances I expressed in an earlier post.
    Code:
    theMap m_theMap;
    ...
    ...
    Object *pObject = new Object();
    m_theMap.insert(theMap::value_type(0,pObject));
    m_theMap.insert(theMap::value_type(1,pObject));
    You now have this:
    0, pointer to same pObject as pObject with key 1
    1, pointer to same pObject as pObject with key 0


    Perfectly valid from a map standpoint but dangerous. Essentially the same exact object can be accessed via two map keys or you have assigned two IDs to the same object.
    So if one object has a stored ID of 1 for pObject and one has a 0 for pObject now you have a mess.

    This could also potentially load the same object twice into memory if the map did any resource loading or other operations if the ID was not in the map. Also if you remove the object with key 1 and cleanup the object and remove it from the map the pointer with key 0 now points to garbage. For non-pointer maps this is not an issue but when you start storing pointers in your containers you could run into some ugly issues if you continue with this line of thinking.
    I can't imagine a scenario where you would want to swap a map having pointers as the mapped values around in the first place. That makes no sense at all. You're going to get unsigned int values by using a pointer key??
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  9. #69
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    Laserlight brought up the legit problem that if you do this you will have to remove all instances of value from the original map. This is where the 'all instances of values' comes from.
    No, I think a better approach for this is to not touch the original map at all, but only insert a mapped value into a key value of another map if the same mapped value doesn't already exist in the other map, i.e. so I would call find() or something on the current mapped value to see if it already exists in the new map. If it does, I wont insert it. Otherwise, I will.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  10. #70
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Ok, I added that in:

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

  11. #71
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    Quote Originally Posted by Programmer_P
    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.
    That means that you have assumed that the default comparator and default allocator will be used. This is pretty much what I said

    Quote Originally Posted by Programmer_P
    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.
    Oh, now I understand. i is an index, as in a vector. Therefore, you are using maps wrongly.

    Quote Originally Posted by Programmer_P
    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.
    That is true, yet it is not true: one can generically declare an iterator.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #72
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by laserlight View Post
    That means that you have assumed that the default comparator and default allocator will be used. This is pretty much what I said
    Yes, and they will be used, since the map parameter of the function is expecting a map with only two explicit parameters (namely the key value and the mapped value). You would not be able to pass a map with a non-default comparator and/or a non-default allocator. Like I was saying though, if you needed a custom comparator and a custom allocator, for whatever reason, for that map, I think you could always just make another multimap, using the same key and mapped value types, and specifying the comparator and allocator you want to use, then iterating through the 2-parameter multimap, and copying the current elements into the 4-parameter multimap, so you end up with a nearly identical multimap as the swapped map, only it has a non-default comparator and a non-default allocator.
    Oh, now I understand. i is an index, as in a vector. Therefore, you are using maps wrongly.
    Who's using maps wrongly?
    It was an example, and an example alone. I was really only trying to demonstrate other possible ways of getting mapped values and key values than those already provided, my point being that I thought the current methods kind of sucked.
    That is true, yet it is not true: one can generically declare an iterator.
    Show the code then...
    Last edited by Programmer_P; 06-20-2010 at 08:38 AM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  13. #73
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    Well I'm out of this discussion. We have gone from maps to multi-maps to vectors to maps and back to vectors. I'm so lost I don't even know what it is you are trying to do. Your posts contradict themselves and I'm not sure we are helping you correctly use any of the containers.

    I guess do what you think works and when you run into the problems that many of us have re-iterated several times then come back and ask more questions.

    Somehow it feels like we've rattled on for 3 pages and have ended up back where we started.

  14. #74
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Bubba View Post
    Well I'm out of this discussion. We have gone from maps to multi-maps to vectors to maps and back to vectors. I'm so lost I don't even know what it is you are trying to do.
    No, we haven't. We're still at multimaps...
    Your posts contradict themselves and I'm not sure we are helping you correctly use any of the containers.
    Show me at least two posts which actually contradict themselves, and I might just admit I was wrong (otherwise I wont...).
    I guess do what you think works and when you run into the problems that many of us have re-iterated several times then come back and ask more questions.

    Somehow it feels like we've rattled on for 3 pages and have ended up back where we started.
    Not really. The topic of this thread is still what it was originally: swapping the key values and the mapped values of one map around and putting them in a new map (now changed to a multimap, so it can support duplicates).
    I'd say we have actually advanced far into the night, with the moonlight light enough to be day, since I now have a working swap() function (which I'll probably rename to flipAMap() so it will more descriptive) which can swap any map with two parameters around.
    That is more than could be said when I first started this thread...

    I understand perfectly all of what has been said in this thread, and have applied a lot of the advice to my function. Perhaps it is other people (possible one of them you?) who are not really seeing clearly.

    Hahaha. Anyway, I'm off to bed now. Its already 3:12 AM here.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  15. #75
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    Quote Originally Posted by Programmer_P
    Who's using maps wrongly?
    It was an example, and an example alone. I was really only trying to demonstrate other possible ways of getting mapped values and key values than those already provided, my point being that I thought the current methods kind of sucked.
    You, if you truly intend to use a map like that. Saying that the current methods "kind of sucked" is bogus when the map is simply not designed to do that. You are using the wrong container for the job, then blaming the container. That sucks, on your part.

    Maps and multimaps are not designed for efficient access by sequential index. They are associative containers designed for efficient access by key value. They are not designed for efficient access by mapped value.

    Quote Originally Posted by Programmer_P
    Show the code then...
    For example:
    Code:
    template<typename IT, typename T>
    bool value_exists(IT begin, IT end, const T& value)
    {
        for (; begin != end; ++begin)
        {
            if (begin->second == value)
            {
                return true;
            }
        }
        return false;
    }
    
    #include <map>
    #include <string>
    
    int main()
    {
        std::map<std::string, int> x;
        // ...
        if (value_exists(x.begin(), x.end(), 123))
        {
            // ...
        }
    }
    That said, instead of implementing an algorithm, I could have implemented a predicate and used std::find_if, e.g.,
    Code:
    template<typename Pair>
    class CompareSecond
    {
    public:
        explicit CompareSecond(const typename Pair::second_type& x) : x_(x) {}
    
        bool operator()(const Pair& y) const
        {
            return y.second == x_;
        }
    private:
        typename Pair::second_type x_;
    };
    
    #include <algorithm>
    
    template<typename IT, typename T>
    bool value_exists(IT begin, IT end, const T& value)
    {
        return std::find_if(begin, end,
            CompareSecond<typename IT::value_type>(value)) != end;
    }
    
    #include <map>
    #include <string>
    
    int main()
    {
        std::map<std::string, int> x;
        // ...
        if (value_exists(x.begin(), x.end(), 123))
        {
            // ...
        }
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 5 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