This lesson contains approximately 16 minutes of video content.


Ordered and unordered maps

C++ provides the ordered map std::map in <map> and unordered map std::unordered_map in <unordered_map>. In today's lesson, we've introduced the former, though it is important to acknowledge the latter.

The ordered std::map and unordered <unordered_map> differ in their underlying implementation. An ordered map is implemented using a tree structure, while an unordered map is implemented with a hash table. At this point, it is reasonable to ask which one you should use. Well, understanding the internal workings of these data structures (tree vs. hash table) is required to make an informed decision in a given application. Since we will not discuss trees or hashing in great detail, we will defer the explanation to your data structures course. With that said, it is essential to emphasize a considerable difference between maps and unordered maps exists. This class will use the ordered std::map from <map>.

On std::map behaviors expecting an std::pair

Some std::map behaviors take an std::pair as an argument. For instance, we can insert a key-value pair to our map using as follows:

std::map<std::string, int> frequency;
frequency.insert(std::pair<std::string, int>("Howdy",1));
The statement performing the insertion to the map is rather lengthy. To shorten things up, you can rely on C++'s uniform initialization to compose the argument:
std::map<std::string, int> frequency;
  frequency.insert({"Howdy", 1});
However, keep in mind that uniform initialization prevents narrowing conversions.

Iterating through a map's key-value pairs

You may find it might be beneficial to inspect the contents of your map from time to time. You can do this by iterating over its [key, value] pairs as follows:

for (auto const& [key, value] : your_map) {
  std::cout << key    << ':'    << value    << std::endl;

Does an element with a specific key exist?

C++ 20 introduces contains for std::map to answer the question: does an element with a specific key exist in the map? To answer that question, simply ask the map object of interest whether it contains a specific key. If an element with the key exists in the map, contains returns true is returned; false otherwise. Here's an example:

std::map<int, std::string> example = {{1, "Cat"}, {2, "Panda"}};
int check_key = 1;
if (example.contains(check_key)) {
  std::cout << check_key << ": Found a " << << std::endl;
} else {
  std::cout << check_key << ": Not found" << std::endl;

Activity: Frequency of each word in an std::string

Graded Playground Autograder

Activity Prompt: In this activity, you will implement std::map<std::string,unsigned int> WordFrequencyCounter(std::string str). This function will return an std::map mapping the individual words (case insensitive) to their frequency count. WordFrequencyCounter must implement the following behavior (be sure to leverage helper functions):
  • Given a single std::string str as its argument,
  • convert the contents of str to lower case using tolower (from <cctype>),
  • remove all occurrences of the punctuation {!, ?, ., ,} from str,
  • determine the individual words comprising the str, and
  • return an std::map<std::string,unsigned int> mapping the case-insensitive words to their frequency.
You do not need to modify str in place. Instead, you can (and should) create additional std::strings while processing str. Consider the following examples (std::string --> std::map<std::string, unsigned int>)
  • "Howdy, World!" --> { {"howdy" --> 1}, {"world" --> 1} }
  • "You must be the change you wish to see in the world." --> { {"you" --> 2}, {"must" --> 1}, {"be" --> 1}, {"the" --> 2}, {"change" --> 1}, {"wish" --> 1}, {"to" --> 1}, {"see" --> 1}, {"in" --> 1}, {"world" --> 1} }
Recommended process

Do not overcomplicate this problem by attempting to use language facilities that we have not taught. You can solve this problem using a combination of selection, iteration, and string concatenation. That's all you need! Don't try to implement your solution to the whole problem at once!

#include <iostream> #include <string> #include <map> #include "utilities.hpp" int main() { std::string str = "Howdy, Ags! Whoop!"; // std::map<std::string,unsigned int> result = WordFrequencyCounter(str); // for (auto const& [key, value] : result) { // std::cout << key << ':' << value << std::endl; // } }
#ifndef UTILITIES_HPP #define UTILITIES_HPP #include <map> #include <string> std::map<std::string,unsigned int> WordFrequencyCounter(std::string str); #endif
#include <cctype> #include "utilities.hpp" // write your definition of WordFrequencyCounter in this source file.