Comparison with Vector
Example
map.put (key, value)
map[key] = value;
map.get(key)
map[key] : this alternate syntax will create a key with the default value in the map if it did not already exist.
map.remove(key)
m.put(key, value) |
m[key] = value |
O(log N) | Inserts the key-value pair if the key does not already exist; else (if key already exists), overwrites |
m[key] = value |
m[key] = value |
O(log N) | Inserts the key-value pair if the key does not already exist; else (if key already exists), overwrites |
m.get(key) |
m.at(key) |
O(log N) | If key already exists, returns the corresponding value; raises exception if key was not present. |
m[key] |
m[key] |
O(log N) | If key already exists, returns the corresponding value; if key was not present, adds a default value for the key to m and returns it. |
m.remove(key) |
m.erase(key) |
O(log N) | If key exists, removes the key and associated value. Else, no effect. |
m.containsKey(key) |
m.find(key) != m.end() |
O(log N) | Returns true if key exists in m. |
Map Example: Dictionary
ifstream file;
promptUserForFile(file, "Where is your dictionary?");
Map<string, string> dictionary;
string word;
while (getline(file, word)) {
string definition;
getline(file, definition);
dictionary[word] = definition;
}
while (true) {
string query = getLine("Word to look up?");
if (dictionary.containsKey(query)) {
cout << "The definition is " << dictionary[query] << endl;
} else {
cout << "I don't know that word!" << endl;
}
}
Question: what if the user was also interested in the list of words for a given meaning? One option is to loop over maps; another option is to maintain a reverse map; we will look at both options one by one.
Looping over Maps
Map<string, int> phonebook;
phonebook["Director"] = 12345678;
phonebook["Dean"] = 98765432;
...
//prints in alphabetical order
for (string name : phonebook) {
int phoneNumber = phonebook[name];
cout << "I’m going to call " << name;
cout << " at " << phoneNumber << endl;
}
For C++ STL, the for-each loop iterates using key-value; access key using .first, access value using .second. example:
Map<string, int> phonebook;
phonebook["Director"] = 12345678;
phonebook["Dean"] = 98765432;
...
//prints in alphabetical order
for (pair<string, int> name_phone : phonebook) {
string name = name_phone.first;
int phoneNumber = name_phone.second;
cout << "I’m going to call " << name;
cout << " at " << phoneNumber << endl;
}
Input in.txt:
to be or not to be hello world the world is not enough i think therefore i am
Output:
am: 1 be: 2 enough: 1 hello: 1 i: 2 is: 1 not: 2 or: 1 the: 1 therefore: 1 think: 1 to: 2 world: 2
Program:
int main()
{
ifstream infile("in.txt");
string word;
Map<string, int> wc;
while (infile >> word) {
if (!wc.containsKey(word)) {
wc[word] = 0;
}
wc[word]++;
}
for (string w : wc) {
cout << w << ": " << wc[w] << endl;
}
}
Input in.txt:
to be or not to be hello world the world is not enough i think therefore i am
Output:
be: 2 i: 2 not: 2 to: 2 world: 2 am: 1 enough: 1 hello: 1 is: 1 or: 1 the: 1 therefore: 1 think: 1
Need to devise a solution where the frequency is the key. One solution: after constructing wc, create another map where the frequency is the key. But now, multiple words can have the same frequency, so what should be the value of this map? e.g., set<string>.
Map<int, Set<string>>Could you use a
Vector instead of Set. How about using a Queue or Stack?
int main()
{
ifstream infile("in.txt");
string word;
Map<string, int> wc;
while (infile >> word) {
if (!wc.containsKey(word)) {
wc[word] = 0;
}
wc[word]++;
}
Map<int, set<string>> wc_sorted;
for (string w : wc) {
int wfreq = wc[w];
if (!wc_sorted.containsKey(wfreq)) {
wc_sorted[wfreq] = Set<string>();
}
wc_sorted[wfreq].add(w);
}
for (int wfreq : wc_sorted) {
Set<string> words = wc_sorted[wfreq];
for (string word : words) {
cout << word << ": " << wfreq << endl;
}
}
}
ram Staff Canteen Rainbows shyam Rajdhani Chatkare Govardhan Rainbows geeta Govardhan Rainbows