stl hash_map - modifying key

Question

I have a hash map defined as

class KeyType {
    int key;
    mutable bool flag;
    KeyType(int key) : key(key), flag(false) {}
    void setFlag() const { flag = true; }
};

struct KeyType_hasher {
    size_t operator()(const KeyType& s) const {
        return static_cast<size_t> key;
    }
};

struct KeyType_equal {
    size_t operator()(const KeyType& s1, const KeyType& s2) const {
        return s1.key == s2.key;
    }
};

typedef hash_map<KeyType , ValueType, KeyType_hasher, KeyType_equal > KeyValueMap;

Later on in the code I have a place where I have to loop though the map and apply a function to each value I find. Based on the function's outcome, I have to modify the key at the iterator as well.

KeyValueMap theMap;
// theMap[key1] = value1;
// theMap[key2] = value2;
// theMap[key3] = value3;
for(KeyValueMap::iterator i = theMap.begin(); i != theMap.end(); ++i) {
    if(true == ValueFunction(i->second))
        i->first.setFlag();
}

My question is, would that be the right way of modifying the key, if I have to? Does it have any bad side effects?

Answer 1

You'd have to remove the element from the container and re-add it with the new key.

None of the C++ associative containers support changing the key in a significant way (where significant means the change alters the results of the hash in a hashed container or the comparrsion in an ordered container).

If you did modify the key (by circumventing the const correctness system in some way) you'd get unpredictable results from lookups.

Answer 2

Not only can you not change the key since it's a const member of the pair, you can't erase or insert members into the hash_map without invalidating the iterator, i, you have. When i is invalidated, you can't increment it to get the next item from the container.

There might be (and probably is) a better algorithm, but what I think you'll need to do is store copies of the elements (or just the keys) of the elements you want to have the keys changed for in some other temporary container in your for loop. Then walk the temportary container and use the information in it to:

• get the element you want to change the key for in the original hash_map container
• erase() that element from the original container
• insert() a new element with the new key and original value back into the hash_map

Then you can dump the temporary container.