COMS W4995 C++ for C Programmers

Index of 2023-5/code/0608

Parent directory
Makefile
stl1.cpp
stl2.cpp
words.cpp

Makefile

CC  = g++
CXX = g++

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

executables = stl1 stl2 words

.PHONY: default
default: $(executables)

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

.PHONY: all
all: clean default

stl1.cpp

#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>

using namespace std;

template <typename T, int N>
struct Array {
    // typedef T value_type;
    using value_type = T;
    // The type "T(&)[N]" is reference to array of N elements of T
    typedef T (&TA)[N];

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }

    constexpr int size() const { return N; }
    TA underlying() { return a; }

    T a[N];
};

void print_int(int x)  { cout << x << ' '; }

int main()
{
    int a[5] = { 100, 101, 102, 103, 104 };

    size_t n = sizeof(a) / sizeof(a[0]);

    for (size_t i = 0; i < n; ++i)  { print_int(a[i]); }

    cout << '\n';
}

/*
Code to use in lecture:

    int a[5] { 100, 101, 102, 103, 104 };
    Array<int,5> v { 100, 101, 102, 103, 104 };
    std::array<int,5> v { 100, 101, 102, 103, 104 };
    vector<int> v { 100, 101, 102, 103, 104 };
    deque<int> v { 100, 101, 102, 103, 104 };
    list<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    v.push_back(205);
    forward_list<int> v { 100, 101, 102, 103, 104 };
    cout << sizeof(v) << '\n';

    for (int x : a)  { print_int(x); }
    for (int x : v.a)  { print_int(x); }
    for (int x : v.underlying())  { print_int(x); }
    for (int x : v)  { print_int(x); }

Lecture outline:

1. arrays in C++

    - direct-list-initialization and range-for loop for C arrays
    - Array template class
    - std::array template class

2. STL containers

    - vector
        - elements are always contiguous
        - push_back() in O(1), but may invalidate pointers and refs
    - deque
        - push_back() & push_front() in O(1), and preserve ptrs and refs
        - elements are not contiguous though
    - list
        - doubly linked list
        - push_back(), push_front(), insert() all in O(1)
        - but probably slower than vector in many situations
    - forward_list
        - minimal singly linked list
        - push_front()
    - all STL containers contain elements by value
        - recall the memory diagram of vector<MyString>
*/

stl2.cpp

#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
#include <iterator>

using namespace std;

// Pretty much the same as std::for_each
template <typename I, typename F>
void For_Each(I b, I e, F f)
{
    while (b != e) {
        f(*b);
        ++b;
    }
}

void print_int(int x)  { cout << x << ' '; }

int main()
{
    int a[5] = { 100, 101, 102, 103, 104 };

    For_Each(a, a + 5, &print_int);

    cout << '\n';
}

/*
Code to use in lecture:

    vector<int> v { 100, 101, 102, 103, 104 };
    vector v { 100, 101, 102, 103, 104 };
    list v { 100, 101, 102, 103, 104 };
    const list v { 100, 101, 102, 103, 104 };

    For_Each(&v[0], &v[0] + 5, &print_int);
    For_Each(v.begin(), v.end(), &print_int);

    for (list<int>::iterator i = v.begin(); i != v.end(); ++i) {
        *i += 200; 
        cout << *i << ' ';
    }
    for (list<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
        cout << *i << ' ';
    }
    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i << ' ';
    }
    for (auto& x : v) {
        cout << x << ' ';
    }

Lecture outline:

1. For_Each using pointers

    - array
    - vector

2. For_Each using begin() & end()

    - also works for list & deque, so ++b can't just be pointer arithmetic

3. Iterators

    - end() points to one past the last element
    - half-open element range: [ b, e )
    - dereferencing iterator gives you "T&"
    - dereferecning const_iterator gives you "const T&"
    - use auto to deduce iterator type
    - range-for loop uses begin() & end()
    - why not (b < e)?
    - why not b++?

4. Template compilation model
*/

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];
        //m.insert( {s, m.count(s) + 1} );
    }

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

/*
Code to use in the lecture:

    unordered_map<string,int>  m;
    multimap<string,int>  m;
    unordered_multimap<string,int>  m;

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

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

    // This compiles & runs for multimaps, but probably not what you want!
    auto it = m.find("#include"s);
    if (it != m.end()) {
        auto& [s, n] = *it;
        cout << "\nThe program " << s << " " << n << " headers." << '\n';
    } 

    // 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';
    } 

*/