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

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

Originally Posted by Bubba

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.

Originally Posted by Bubba

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.

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.

Originally Posted by Bubba

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.

Originally Posted by Bubba

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

Originally Posted by Bubba

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.

Ok, I added that in:

C++ code - 37 lines - codepad

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

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.

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.

Originally Posted by laserlight

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

Originally Posted by Bubba

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.

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.

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))
    {
        // ...
    }
}