How to implement an associative array/map/hash table data structure (in general and in C++)

Well I'm making a small phone book application and I've decided that using maps would be the best data structure to use but I don't know where to start. (Gotta implement the data structure from scratch - scho开发者_StackOverflowol work)

Tries are quite efficient for implementing maps where the keys are short strings. The wikipedia article explains it pretty well.

To deal with duplicates, just make each node of the tree store a linked list of duplicate matches

Here's a basic structure for a trie

struct Trie {
   struct Trie* letter;
   struct List *matches;
};

malloc(26*sizeof(struct Trie)) for letter and you have an array. if you want to support punctuations, add them at the end of the letter array.

matches can be a linked list of matches, implemented however you like, I won't define struct List for you.

Simplest solution: use a vector which contains your address entries and loop over the vector to search.

A map is usually implemented either as a binary tree (look for red/black trees for balancing) or as a hash map. Both of them are not trivial: Trees have some overhead for organisation, memory management and balancing, hash maps need good hash functions, which are also not trivial. But both structures are fun and you'll get a lot of insight understanding by implementing one of them (or better, both :-)).

Also consider to keep the data in the vector list and let the map contain indices to the vector (or pointers to the entries): then you can easily have multiple indices, say one for the name and one for the phone number, so you can look up entries by both.

That said I just want to strongly recommend using the data structures provided by the standard library for real-world-tasks :-)

A simple approach to get you started would be to create a map class that uses two vectors - one for the key and one for the value. To add an item, you insert a key in one and a value in another. To find a value, you just loop over all the keys. Once you have this working, you can think about using a more complex data structure.