Skip to Content

COMP225 : Algorithms and Data Structures

Practical Week 9
Objectives: To understand more about maps and multimaps.
  1. Simple Exercise : To become more proficient at programming and using STL containers (i.e. more employable). Maps are so useful in a wide range of contexts.

    trymap.cpp is a simple-minded program which creates a map for studentids (string) and associated marks (int) with the studentid as the key. Read and understand the program. Compile and run the program and enter some data. Now write a loop to display the map in descending order of studids. Investigate using a reverse iterator (you also want to become proficient in extending your knowledge readily = independent learning).

    Continue with above program ensuring that you understand how it can retrieve a studentid which exists in the map and display the associated mark and how it indicates that a studentid does not exist in the map.

  2. (*)

    Submitted Program

    A concordance is a program which counts and reports the frequency of words in a text. This program will read in some text, record the word and its frequency in a map and then display an alphabetical list of words and their frequency.

    As each word is read in it is converted to lower case and checked if it exists in map. If word does exist then its frequency is increased else word is inserted into map with a frequency of 1. (When we increase frequency can we just change the entry in the map? Or do we need to remove it add one and then insert a new entry?)

    Any punctuation other than a hyphen mid-word is ignored.

    This will be automarked so do check that output is the same as indicated.

  3. Help with Assignment 3

    For assignment 3 we wish to associate a city with an integer. The first city read in should be assigned the integer 0, the next different city should be assigned the integer 1 and so on. The cities are read in two per line delimited by tabs followed by a value (which can be ignored for now). For example if the input data is : 
    Sydney	Perth	400
Sydney	Paris	900
Perth	Paris	1000
    then Sydney should be assigned 0, Perth 1, and Paris 2.

    To do this we can use a map where the key is the city and the assigned int is the associated value. We will need a variable (say count) which is initially 0. As we read in a city we check if city is in the map and if it isn't then we assign current value of count to city and insert into map and increment count.

    This is quite easy but a little error-prone. It is worth spending the time now perfecting the code to do this correctly and elegantly. Display the map to test that you have done so.

    Note that the cities are separated by tabs to allow cities such as New York which contains a space. You will therefore need to use cin.get(c) (or could use strtok if you are a c programmer)

    Now extend this code to create an additional inverse look-up map i.e. so that given key 0 you can retrieve Sydney, and given key 1 you can retrieve Perth etc Display this map.