Retrieving data from hash table ordered by insertion time

Problem Detail: 

By default, a hash table is unordered. I have a simple question on the retrieval of elements in a hash table

Can we retrieve elements from a hash table in the same order as they are put inside?

Asked By : Jayram Singh

Answered By : Wandering Logic

Once you've put an element in any kind of container data structure like map or set, ordered or unordered, the data structure no longer remembers the order in which you called insert(). (The "ordered/unordered" distinction is whether the data structure keeps the elements in order by their key with respect to the less-than operator.)

If you want to know the order in which some events happened you will need to keep another container data structure, or some auxiliary information in the objects you are storing. For example if you want to be able to iterate through in the order in which you inserted: keep both an unordered_map and a vector of references to the objects you inserted. Every time you do an insertion you also push_back a reference to what you just inserted. (But be careful, if you are doing this in C++, that you aren't also removing objects from the unordered map, because then the references in the vector will become invalid.)

If you want a number associated with each element stored in the map ("this was the 42nd inserted"), then you should augment your map datatype with, (a) a global counter and (b) a way to store both an object and a number (e.g., store struct {T the_object; int insert_order;} instead of objects of type T), and (c) wrap the insert operators so that they increment the counter and insert the new number along with the new object.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12562