Let's say I want to model a phonebook.
I would like a phonebook to be maintained in sorted order by name of the person that the phonebook entry is created for. However, since it is quite possible that there are two people with the same name, I cannot use any of the sorted collections, because they require the use of keys (which, by definition, must be unique). On the other hand, I must have some sort of unique identifier for each entry, should I desire to implement the phonebook as a service, otherwise, I would have no way to identify the entry that I would like to update or delete.
I would like to hear suggestions and ideas on how to organize the data and the process of adding and updating it, so it is ordered in a desired way, and yet maintain the possibility of quick lookup of a single entry based on a unique id.
The idea that is closest to me goes something like this.
Phonebooks are organized alphabetically, so one of the approaches might be something like this:
SortedDictionary<char, List<PhonebookEntry>> phonebook = new SortedDictionary<char, List<PhonebookEntry>>();
The key would be the first character of the PhonebookEntry primary identifier (name).
The list would be maintained in sorted order on insert and update. The insert would search for the index in the list where the entry should be added, and then insert the entry at that index. Alternative would be a brute force approach: to simply sort the list after each insert. Update would check whether the name of the entry was updated. If so, it would sort the list accordingly if the entry remains in the same list, or it would remove it from that list and insert it in the appropriate list of the dictionary.
Now, the problem is how to find the entry based on some sort of unique identifier that would be assigned to each entry (some GUID, for instance). I am closest to the idea to have another dictionary, like this:
Dictionary<Guid, Tuple<char, long>> phonebookEntryMap = new Dictionary<Guid, Tuple<char, long>>();
The key would be the unique ID of the entry, the value would be a Tuple that contains the first character of the entry (to identify it in the main structure) and the index in the list. The obvious downside to this approach is that this structure needs to be carefully maintained. The upside is that it is a minimal memory overhead, while providing all the information required for a quick access to the desired entry.
An alternative would be to keep a reference to PhonebookEntry in the mapping dictionary instead of the Tuple. It would require more memory, but no mapping overhead.
Are there any other suggestions on how to elegantly resolve this problem?
