Maps
std::map
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));std::map<std::string, int> frequency;
frequency.insert({"Howdy", 1});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 " << example.at(check_key) << std::endl;
} else {
std::cout << check_key << ": Not found" << std::endl;
}
Activity: Frequency of each word in an std::string
Graded Playground Autograder
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 stras its argument, - convert the contents of
strto lower case usingtolower(from<cctype>), - remove all occurrences of the punctuation {
!,?,.,,} fromstr, - determine the individual words comprising the
str, and - return an
std::map<std::string,unsigned int>mapping the case-insensitive words to their frequency.
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!