std::map key usage

[shrini]

Hi,
Can we use a structure as a key of a map? If yes how will I search for a particular key.
here goes the example:

typedef struct radioCardInfo
{
 uint32 radioCardId;
 uint8 radioPathId;
} radioCardInfo;
 
typedef struct msgInfo
{
 uint32 magId;
 enum msg;
} msgInfo;
 
typedef map< radioCardInfo, msgInfo> radioCardMapType;
radioCardMapType  radioCardMap;
 

How will I search radioCardInfo.radioPathId(this should be the key) using map.?

regards
Srini

[AdrianH]

Hi,
Can we use a structure as a key of a map? If yes how will I search for a particular key.
here goes the example:

typedef struct radioCardInfo
{
 uint32 radioCardId;
 uint8 radioPathId;
} radioCardInfo;
 
typedef struct msgInfo
{
 uint32 magId;
 enum msg;
} msgInfo;
 
typedef map< radioCardInfo, msgInfo> radioCardMapType;
radioCardMapType  radioCardMap;
 

How will I search radioCardInfo.radioPathId(this should be the key) using map.?

regards
Srini

Use an iterator. You can find a good example of it here.

Hope this helps.


Adrian

[shrini]

Use an iterator. You can find a good example of it here.

Hope this helps.


Adrian

Hi... I hope iterator is used incase the key is of a basic datatype.
what about when the key is of the user defined data type like a structure..??
ie, when i need to find (search ) any one of the element of the structure.
here goes the example code that im loking for to search
:typedef mp<struct radioInfo, msgId> radioInfoMaptype;
radioInfoMaptype radioInfoMap

now if I need to search the element of radioInfo (ie radioInfo.radioCardId), how will I do it using the iterator operator ?
radioInfoMap.find(xxxx) xxxx is the element of the structure which is defined as the key of the map

Warm regards
Shrini

[AdrianH]

Hi... I hope iterator is used incase the key is of a basic datatype.
what about when the key is of the user defined data type like a structure..??
ie, when i need to find (search ) any one of the element of the structure.
here goes the example code that im loking for to search
:typedef mp<struct radioInfo, msgId> radioInfoMaptype;
radioInfoMaptype radioInfoMap

now if I need to search the element of radioInfo (ie radioInfo.radioCardId), how will I do it using the iterator operator ?
radioInfoMap.find(xxxx) xxxx is the element of the structure which is defined as the key of the map

Warm regards
Shrini

Iterator is not an operator, but a class that acts like a pointer. So when invoking find(xxxx), the class that xxxx object is part of must have the operators < and == overloaded, this is so that the pair can be inserted into the map and so that find() can find the object in question. Not overloading these may still work, but it may be slower than what you really wanted.

If you dereference a map's iterator, you get a pair<key, item> object which in your case would be pair<radioInfo, msgId> (you don't need the struct prefix in C++). To access the second item you would do something like this:

radioCardMapType::iterator myIterator = radioInfoMap(<your structure or reference to structure here>);
msgInfo& myMsgInfo = myIterator->second;
 

Feel free to ask more questions if you still don't understand.


Adrian

[shrini]

Iterator is not an operator, but a class that acts like a pointer. So when invoking find(xxxx), the class that xxxx object is part of must have the operators < and == overloaded, this is so that the pair can be inserted into the map and so that find() can find the object in question. Not overloading these may still work, but it may be slower than what you really wanted.

If you dereference a map's iterator, you get a pair<key, item> object which in your case would be pair<radioInfo, msgId> (you don't need the struct prefix in C++). To access the second item you would do something like this:

radioCardMapType::iterator myIterator = radioInfoMap(<your structure or reference to structure here>);
msgInfo& myMsgInfo = myIterator->second;
 

Feel free to ask more questions if you still don't understand.


Adrian

Hi Adrian,

I think I still didnt get the solution you said.
My requirement is to have a structure as a key and then, using an iterator I will have to find for the key elements.
say if my structure(key) has 3 elements and each iterator::find(xxxx) I need to search for different elements of the structure.

In first iterator::find(xxxx) I need to find for the key radioCardInfo.radioCardId.
in my second invokation immediately iterator::find(xxxx), I need to find for radioCardInfo.radioCardValue.
How can the iterator class find for a different key this time.
thats why I thought of using a structure as a key element of a map and ecah time I will search for different elements of that structure.

Is that the iterator::find(xxxx) can find for different elements of the structure(key) ??

regards
Srini

[AdrianH]

Hi Srini,

Ok, I think I understand what you are asking, the key has two (or more) elements in it, and you want to search for a (key, value) pair based on one of the sub-keys, and then search for a (key, value) pair based on the other sub-key. If this is the case then unfortunately, what you are asking for cannot be done with a single map efficiently, though it can be done, but if done it cannot be done exclusively with the map::find() function. The reason is this:

A map is based on a key that has an “order”, this means that a key A and a key B can be compared and one can be said to precede the other. When inserting into the map, the map structure sorts by the (key, value) pair. If that pair already exists in the map, then the old value is overwritten, otherwise it is inserted into the map.

Now, if you were to use map::find() to find a (key, value) pair based on the key, the map will do a lookup that will basically split all of the inserted pairs in half to determine which half the key that is being looked for is in. It will then split that half into half again to determine which quarter the pair would be in. This keeps going till it either finds the key or it doesn’t.

Consider this: if you were to insert and find a key based on sub-key A, and then using the same map, try to find a key based on sub-key B, what would happen if the order of all the values in sub-key A were not the same order as the values in sub-key B. Then finding a key based on sub-key B could conceivably not find the matching key even if one exists since it would be looking in the wrong place for it.

The iterator is not an operation, but a structure that keeps track of where it is in the set of pairs. It acts like a pointer. Say you have an array of 2 elements, and you have a variable that points to the first element. Now you increment that variable and it will now point at the next element. Decrement it and it points back at the first element again. Increment it twice and it will fall off the end (will point to a position that is past the end of the array). This is exactly how an iterator works. If you point at the first element in the map, vector, set, or any other container that supports an iterator that has 2 elements and you do the same thing as I had explained with the array example, you will get the same logical result.

The function map::find() however will find an item in O(log n) time (means that in the worst case if there are n elements it will not have to search every element to find the appropriate element or find that the element does not exist in the map).

If you wanted to find a key based on two separate sub keys, then you would either have two different maps, each one being ordered on different sub-keys or you can have one map that orders on one of the sub-keys and if you want to find on a second sub-key, you would have to find it in O(n) time (means in the worst case you will have to search each and every element to determine if it is there or not). If time is not an issue or n is a small number or space is an issue (or if it is an assignment that your teacher/prof has told you to do), using one map may be what you are looking for.

Iterators are fairly easy to use because they are based on how pointers are used. To get to the beginning of a container, use the <container>.begin() position, you can then search each pair returned by dereferencing the iterator for the second criteria that you are looking for till you reach the <container>.end() position. Do not search that position as it is off the end of the container (just like in the array example).

There are already algorithms in the STL that will do this second search, namely find_if(), but it requires another class to be made, and I want to make sure that you have understood everything that I have said so far, and if going further is necessary for you to do your assignment.

Let me know.



Adrian