0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you seen it stated that you can? Or are you interested in developing a method to do so? $\endgroup$ – Luke Mathieson Jul 24 '13 at 0:59
  • 1
    $\begingroup$ It's unclear whether you are interested in the insertion points of the keys or the values corresponding to the keys. This might make a difference if you want to make an auxiliary data structure handling this. $\endgroup$ – Pål GD Jul 30 '13 at 8:05
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.