Implementing Dictionary in C++

Working with C#, I loved the feature of the data-type : Dictionary. I was wondering how we can implement a Dictionary in C++.

Heres what could be a way out...

1. Following the C# implementation as the model, we create a class having two elements : key and value, and implement it as a doubly linked-list. This will optimize structure parsing of the dictionary.

2. We can use Templates to make it a case with generic key and value types.

3. Another internal optimization would be to use hash.

4. Sort the dictionary based on the key values.

5. Provide functions to set and unset key-value pair.
--As I noticed that dictionary is immutable during access, provide a stack say _keys_to_delete on top of which we can push the keys of entries to be deleted. Implement a garbage collection of sorts that runs a loop to delete the entries based on the keys found in the stack _keys_to_delete after the dictionary has finished iterative access (so that it again becomes mutable)...