COMS W4995 C++ for C Programmers

Index of 2025-1/code/09

Parent directory
Makefile
words.cpp

Makefile

CC  = g++
CXX = g++

CFLAGS   = -g -Wall
CXXFLAGS = -g -Wall -std=c++17

executables = words

.PHONY: default
default: $(executables)

words: words.o

.PHONY: clean
clean:
	rm -f *~ a.out core *.o $(executables)

.PHONY: all
all: clean default

words.cpp

#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    map<string,int> m;

    for (string s; cin >> s; ) {
        ++m[s];
    }

    for (auto i = m.begin(); i != m.end(); ++i) {
        cout << setw(4) << (*i).second << '|';
        cout << i->first << '\n';
    }
}

/*  Lecture outline:

1.  std::map

    - std::map is a sorted associative container
    - contains key-value pairs with unique keys
    - balanced binary tree (usually Red–black tree) of pair<key,value>

2.  Code walk-through

    - m[s]
    - iterating through a map using map::iterator

3.  More convenient loops:

    // Range-for loop
    for (auto& e : m) {
        cout << setw(4) << e.second << '|' << e.first << '\n';
    }

    // Structured binding
    for (auto& [s, n] : m) {
        cout << setw(4) << n << '|' << s << '\n';
    }

4.  Looking up an entry:

    auto it = m.find("#include"s);
    if (it != m.end()) {
        auto& [s, n] = *it;
        cout << "\nThe program " << s << " " << n << " headers." << '\n';
    } 

5.  std::unordered_map

    - Hash table instead of binary tree
    - Replacing map with unordered_map works without any other change:

        unordered_map<string,int> m;

6.  std::multimap

    - Same as map, except you can have multiple entries with the same key
    - Replacing map with multimap requires some other changes:

        multimap<string,int>  m;

        // ++m[s];
        m.insert( {s, m.count(s) + 1} );

        // If a key matches multiple entries, find() can return any of them;
        // Call equal_range() to find all elements in multimaps
        auto range = m.equal_range("#include"s);
        if (range.first != range.second) {
            auto& s = range.first->first;
            //auto n = range.second - range.first;
            auto n = distance(range.first, range.second);
            cout << "\nThe program " << s << " " << n << " headers." << '\n';
        } 

7.  unordered_multimap

    - Same as multimap, except it's a hash table instead of a binary tree
    - Replacing multimap with unordered_multimap requires no other change:

        unordered_multimap<string,int> m;

    - Judging from the output where the same-key elements are grouped
      and ordered in reverse, we can guess that a single element in
      unordered_map is replaced by a forward_list of elements.

*/