hash_map: insert and its order

[h9uest]

Hi, I've got 4 questions about C++ hash_map in "ext/hash_map":

1. Trying to access a non-existent key will introduce insertion, won't it?
For example, I know that:

hash_map<char* key, char* value> hm1; //hm1 is empty
hm1["wed"]= "The day after Tuesday";//now, hm1 contains one entry: "wed" ---> "The day after Tuesday" 

The code piece above will actually insert the pair into hm1, an originally empty hash map. Based on the hash_map we have now (containing one pair), My question is: if

// I intend to check whether some key exists in the hm1; if not, print "no such key"
if(hm1["Tues"]==NULL)
{
   cout << "No such key\n";
}

Is the code piece going to do what I intend to do? Will the code piece introduce a new pair <"Tues", NULL> into hm1?



2. How can I have hm1 sorted on key? I want to access pairs sequentially from smaller key to greater key, with an iterator.



3. Is there any way to guarantee the order of access with iterator? For example, I want to use an iterator to access/update <key, value> pairs with the SAME order I inserted them into hm1. How do I do this?



4. Theoretically, hash_map has O(1) time complexity for access. In real application, if my c string key is very long, say 4kb, will it significantly affect the time to access pairs <key, value>?



Any inputs are greatly appreciated!

[m4ster r0shi]

(Q1)

To check wether or not an entry of a specific key exists,
you can use the find member function of your hash_map.

If there is such an entry, the function returns an iterator to it.
If not, it (probably) returns an iterator pointing past the last element (end()).

(Q2)

The short answer is that you can't.

A long useful answer is that you have to copy your
elements to another container and sort them there.

A short useful answer is that you should check out Boost.MultiIndex
( http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/index.html )

(Q3)

Check out Boost.MultiIndex -> http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/index.html

(Q4)

My guess is that the access time will be affected significantly.
It may even become slower than a binary tree based map,
since a good hash function is supposed to use all the bytes
of the key to generate the hash value, while a < operator
most of the time doesn't have to check the whole string.

Useful link -> http://www.sgi.com/tech/stl/hash_map.html

[h9uest]

@m4ster r0shi:
Thanks for the reply. It's very helpful.