Wednesday, April 2, 2014

Placeholdered Maps

Placeholdered map is able to associate keys with values. User can add key value pairs into it and ask for data associated with keys. It works exactly as it would work in an ordinary map.

The additional feature is ability to use placeholders. Placeholder knows when it was created and is useful to cheat on order in which data were added into the map. If the user adds data into placeholder, the datastructure behaves as if the data were added when the placeholder was created.

We will create two such structures. First keeps key value pairs and can return last value associated with the key. Value added into placeholder is returned only if user did not added the same key after the placeholder was created. Second returns all values associated with the key in order they were put in. Placeholders can be used to add data in the middle of those lists.