Key_value, std::map

[Valdamire]

I have a problem with searching the value of the std::map. I had a key value std::string and I'm definetly sure that this map has the value with such key. But it can't be found.

I've thought about the issue that I've made to make universal key value - I transformed all the keys to the lowercase using the const_cast. But event without transfomation it don't want to find the key. I'm using the std::map::find and std::map::at. Both of them can't do what I want.

When I'm doing my own lamba class with the operator () to compare to keys, it finds the key with no problems.

May be someone can help with this issue? Thanks a lot.

[Disch]

I'm not sure how const_cast would help in any way. =/


Anyway, it sounds like you are overcomplicating this. If std::map doesn't find the key, then the key either isn't in your map... or the method you're using for comparing keys is broken.

I would not recommend changing the compare function, and instead... if you want to remove case as an issue, simply convert all your keys to lowercase before using them.

[Valdamire]

Disch:

Anyway, it sounds like you are overcomplicating this. If std::map doesn't find the key, then the key either isn't in your map... or the method you're using for comparing keys is broken.

I would not recommend changing the compare function, and instead... if you want to remove case as an issue, simply convert all your keys to lowercase before using them.

Thaks for answer.

I convers all the keys right away after putting it to the map. And I rechecked this issue several times, the necessary key is in the map, but standart methods can't find this key value. I tried find() method and at().

I'm now trying to debug this issue and I found out that standarts methods can't find the node where the pair placed. It trys to find the nearest node and goes even to the wrong subtree. So, I think my question changed now: is there a checksum may be in the key_value that works in the comp functions of the find methods?

Thanks.

[Peter87]

Make sure the strings are exactly the same. Same length, no "invisible" characters, no variations of the same character (e.g. 'é' != 'è') ...

[Valdamire]

Peter87, thank you for answer.

I've already done this.
I have the value :
[5] ("achievement for 4th Star", "k_3069125507")

and I'm comparing it to the:
str "achievement for 4th star"

These values I copied from the veriables watch in the Visual Studio.

I tried to compare the letters codes, they are the same. I've created the check sum by my self on UNIX copying the strings - same result. So, I do not think the issue is in the values of strings.

I was thinking about transformation of the key value. May it be that for example some value for the tree node to put in the tree, is not changing? Check sum may be. It is used quite often. So, I transformed key value but some value is not changed. And when I'm trying to find it, it takes the wrong way.

Thank you for your feedback.

[Peter87]

Valdamire wrote:

I have the value :
[5] ("achievement for 4th Star", "k_3069125507")

and I'm comparing it to the:
str "achievement for 4th star"

The S doesn’t have the same case in both strings.

[Valdamire]

Peter87,

Sory for that. It is a misstake in the example. I made it when i was taking the example. This example goes right before the std::transform. Now I actualy can't provide the right examlple from the VS, I don't have my programm now.

But it takes values like:
("achievement for 4th star","k_....").

I'm using:

std::string& key_value = const_cast< std::string& >( it->first );
std::transform( key_value.begin(), key_vlue.end(), key_value.begin(), ::tolower );

I think that the problem is in the std::transform( ... ). But I'm not sure.

[Peter87]

Oh, you shouldn't be doing that. The map keys are const for a reason. If you change the key you mess up the sorting.

If you want the key to be all lower case you should change the string before adding it to the map.

[Valdamire]

Ok. But its quite difficult cause the file, where the insertion to the map is taking place is ganerated.

Is there any methods to do this?
Actualy I cannt understand this, I'm changine the value, why the comparison and sorting become broken in that case?

Thanks.

[Peter87]

Actualy I cannt understand this, I'm changine the value, why the comparison and sorting become broken in that case?

std::map is usually implemented as a binary search tree.
http://en.wikipedia.org/wiki/Binary_search_tree

This is an example of a binary search tree. I'm using numbers instead of strings to make the ordering more obvious but the principle is the same for strings. Notice how the numbers (keys) are sorted.

            8
           / \
          3   10
         / \
        1   6

If we want to search for number 6 we start at the top.

            8      6 is less than 8 so we keep searching in the left subtree.
           / \    
          3   10   6 is greater than 3 so we keep searching in the right subtree.
         / \
        1   6      6 is equal to 6 so we have found what we searched for

Now if you change number 3 in the tree to a 7 you get the following tree. Notice how the tree is no longer sorted correctly.

            8
           / \
          7   10
         / \
        1   6

If we search for number 6 again it does not work.

            8      6 is less than 8 so we keep searching in the left subtree.
           / \    
          7   10   6 is less than 7 so we keep searching in the left subtree.
         / \
        1   6      6 is not equal to 1, and there are no subtrees to search,
                   so that means we have failed to find what we were looking for.

[Valdamire]

Ok. I understand how it works. I don't know if it possible to update the map may be. I realize that changine of the key is cause the misstake in the structure of the tree. But I want to solve it without the pretransformation.

Or may be I can use unordered map to avoid the tree structure. I that case it will be usual hash table and any dependencies will appear on the keys value.

Any way thank you for help. Tommorow I will write about result.

[cire]

I don't know if it possible to update the map may be.

The usual method is to remove the old key/value and insert a new one. That is true of an ordered or unordered map. The keys are not mutable in either.

But I want to solve it without the pretransformation.

Changing the comparison criteria would be one way to do so.

[Valdamire]

cire,

Remove and insert values are quite expensive operations. I don't think I want to use this methos.

If the key_comp would be changed the structure of the tree would not be changed, so it would stay broken, as I understands. But with the case of unorederd map, its not depend on where the node is placed actualy, after which node. Every node is independent. There just grouped toghether. And method at( key_value ) will not change its result if I would change the key. Correct me please if I misstaken.

Thank you a lot for help.

[cire]

Remove and insert values are quite expensive operations. I don't think I want to use this methos.

Not particularly expensive with an unordered map, whereas your chosen method just doesn't work. I think I'd prefer a method that worked, foremost.

If the key_comp would be changed the structure of the tree would not be changed, so it would stay broken, as I understands.

I don't think you understand. If the comparison function ignores case, the structure of the tree doesn't need to change.

But with the case of unorederd map, its not depend on where the node is placed actualy, after which node. Every node is independent.

In the case of an unordered map, you still encounter undefined behavior (and, no, it is unlikely to behave as you expect.)

http://ideone.com/tJzatN

[Valdamire]

cire,

Yeh, I've tried it already. And now I'm clear with it.

So problem now solved. I changed the script that generates the file with insertion to the map. And now every value is transfoms to lower before the inserting. It took some time actualy, but know it works... as expected. :)

I still not sure that solution with reinserting the pair is best. There was another solution: to store all the pairs in the std::vector, not in the map. But in this case searching speed is falling. And I need it to be quite fast on getting the value.

So, final version looks like this:

lower_str = "achievement for 4th Star";
std::transform( lower_str.begin(), lower_str.end(), lower_str.begin(), ::tolower );
m_constants.insert( std::pair< std::string, std::string >( lower_str, "k_3069125507" ) );

The const char* string actualy is the parameter in the script function. And this function calls a lot time. In case of that file have a lot of such code part. It makes the script more difficult, but the resulting createon and get speed are stay the same it was, with the needed searching result.

Thaks everyone for help.